AT_codefestival_2016_qualC_e 順列辞書

有一天，高桥君捡到了一本包含所有 $1$ 到 $N$ 的 $N!$ 个排列的字典。这本字典共有 $N!$ 页，第 $i$ 页（$1 \leq i \leq N!$）上记载着按字典序排列的第 $i$ 个排列。高桥君想用这本字典查找一个长度为 $N$ 的排列，但他忘记了排列中的部分数字。因此，他打算查找所有可能的排列在字典中的页码，并计算这些页码的总和。请你求出高桥君需要查找的所有页码之和对 $10^9+7$ 取模的结果。 排列的信息由 $P_1, P_2, ..., P_N$ 给出。当 $P_i=0$ 时，表示高桥君忘记了排列第 $i$ 个数，否则 $P_i$ 表示排列第 $i$ 个数就是 $P_i$。

输入通过标准输入给出，格式如下： > $N\ P_1\ P_2\ ...\ P_N$

输出高桥君需要查找的所有页码之和对 $10^9+7$ 取模的结果。

## 限制条件 - $1 \leq N \leq 500000$ - $0 \leq P_i \leq N$ - 若 $i \neq j$ 且 $P_i \neq 0$ 且 $P_j \neq 0$，则 $P_i \neq P_j$ ## 部分得分 - 若能正确解决 $1 \leq N \leq 3000$ 的数据集，可获得 $500$ 分。 ## 样例解释 1 可能的排列为 $[1,2,3,4]$ 和 $[4,2,3,1]$。前者在第 $1$ 页，后者在第 $22$ 页，因此答案为 $23$。 ## 样例解释 2 所有长度为 $3$ 的排列都是可能的，因此答案为 $1+2+3+4+5+6=21$。 ## 样例解释 3 高桥君完全记得这个排列。 ## 样例解释 4 字典只有 $1$ 页。 由 ChatGPT 4.1 翻译