/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 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