Score : 1200 points
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.
The input is given from Standard Input in the following format:
N P_1 P_2 ... P_N
Print the sum of the page numbers of the pages he has to check, as modulo 10^9 + 7.
4 0 2 3 0
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.
3 0 0 0
21
Since all permutations of length 3 are possible, the answer is 1 + 2 + 3 + 4 + 5 + 6 = 21.
5 1 2 3 5 4
2
Mr. Takahashi remembered all the elements of the permutation.
1 0
1
The dictionary consists of one page.
10 0 3 0 0 1 0 4 0 0 0
953330050