CODE FESTIVAL 2016 qual C

E - 順列辞書 / Encyclopedia of Permutations


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 1200

問題文

ある日高橋君は、1~N からなる N! 個の順列全てが載っている辞書を拾いました。辞書は N! ページからなり、 i (1≦i≦N!) ページ目には辞書順 i 番目の順列が載っています。高橋君はこの辞書で長さ N のある順列を調べようとしましたが、順列の一部の数は忘れてしまいました。そのため、可能性のある順列全てをこの辞書で調べようとしています。高橋くんが調べる必要のあるページ番号の総和を 10^9+7 で割ったあまりを求めてください。

順列の情報は P_1,P_2,...,P_N で与えられます。P_i=0 の時は順列の i 番目の数を忘れてしまったことを、そうでない場合は順列の i 番目の数が P_i であることを意味します。

制約

  • 1≦N≦500000
  • 0≦P_i≦N
  • i≠j (1≦i,j≦N) かつ P_i≠0 かつ P_j≠0 ならば、 P_i≠P_j

部分点

  • 1≦N≦3000 を満たすデータセットに正解すると、500 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

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

辞書は1ページからなります。


入力例 5

10
0 3 0 0 1 0 4 0 0 0

出力例 5

953330050

Score : 1200 points

Problem Statement

One day Mr. Takahashi picked up a dictionary containing all of the N! permutations of integers 1 through N. The dictionary has N! pages, and page i (1 ≤ i ≤ N!) contains the i-th permutation in the lexicographical order.

Mr. Takahashi wanted to look up a certain permutation of length N in this dictionary, but he forgot some part of it.

His memory of the permutation is described by a sequence P_1, P_2, ..., P_N. If P_i = 0, it means that he forgot the i-th element of the permutation; otherwise, it means that he remembered the i-th element of the permutation and it is P_i.

He decided to look up all the possible permutations in the dictionary. Compute the sum of the page numbers of the pages he has to check, modulo 10^9 + 7.

Constraints

  • 1 ≤ N ≤ 500000
  • 0 ≤ P_i ≤ N
  • P_i ≠ P_j if i ≠ j (1 ≤ i, j ≤ N), P_i ≠ 0 and P_j ≠ 0.

Partial Score

  • In test cases worth 500 points, 1 ≤ N ≤ 3000.

Input

The input is given from Standard Input in the following format:

N
P_1 P_2 ... P_N

Output

Print the sum of the page numbers of the pages he has to check, as modulo 10^9 + 7.


Sample Input 1

4
0 2 3 0

Sample Output 1

23

The possible permutations are [1, 2, 3, 4] and [4, 2, 3, 1]. Since the former is on page 1 and the latter is on page 22, the answer is 23.


Sample Input 2

3
0 0 0

Sample Output 2

21

Since all permutations of length 3 are possible, the answer is 1 + 2 + 3 + 4 + 5 + 6 = 21.


Sample Input 3

5
1 2 3 5 4

Sample Output 3

2

Mr. Takahashi remembered all the elements of the permutation.


Sample Input 4

1
0

Sample Output 4

1

The dictionary consists of one page.


Sample Input 5

10
0 3 0 0 1 0 4 0 0 0

Sample Output 5

953330050

Submit提出する