分数: 1200 点
问题陈述
有一天,高桥先生拿起一本字典,其中包含所有 N!整数的排列 1 通过 N。 字典里有 N!页面和页面 i (1 ≤ i ≤ N!) 包含 i按字典顺序排列。
高桥先生想查找某个长度的排列 这本词典中有 N ,但他忘记了其中的一部分。
他对排列的记忆是由序列描述的 P_1, P_2, ..., P_N。 如果 P_i = 0,这意味着他忘记了 i- 排列的第一个元素;否则,就说明他记住了 i排列的第一个元素,它是 P_i.
他决定在字典中查找所有可能的排列。 计算他必须检查的页面的页码总和,取模 10^9 + 7.
约束
- 1 ≤ N ≤ 500000
- 0 ≤ P_i ≤ N
- P_i ≠ P_j if i ≠ j (1 ≤ i, j ≤ N), P_i ≠ 0 和 P_j ≠ 0.
部分分数
- 在测试用例中值得 500 点, 1 ≤ N ≤ 3000.
输入
输入由标准输入按以下格式给出:
N P_1 P_2 ... P_N
输出
打印他必须检查的页码的总和,以模数形式 10^9 + 7.
示例输入 1
4 0 2 3 0
示例输出 1
23
可能的排列是 [1, 2, 3, 4] 和 [4, 2, 3, 1]。 由于前者在页面上 1 后者在页面上 22,答案是 23.
示例输入 2
3 0 0 0
示例输出 2
21
由于长度的所有排列 3 是可能的,答案是 1 + 2 + 3 + 4 + 5 + 6 = 21.
示例输入 3
5 1 2 3 5 4
示例输出 3
2
高桥先生记住了排列的所有元素。
示例输入 4
1 0
示例输出 4
1
该词典由一页组成。
示例输入 5
10 0 3 0 0 1 0 4 0 0 0
示例输出 5
953330050