← 返回题目列表

AtCoder · codefestival_2016_qualC_e

E. 排列百科全书

中文机器翻译题面 查看原题

分数: 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