Problem Description

One day, Takahashi found a dictionary that contains all $ N! $ permutations of numbers from $ 1 $ to $ N $. The dictionary consists of $ N! $ pages, and the $i\ (1≦i≦N!)$ page contains the $ i $ -th permutation in lexicographical order. Takahashi tried to look up a certain permutation of length $ N $ in this dictionary, but he forgot some of the numbers in the permutation. Therefore, he is trying to look up all possible permutations in the dictionary. Find the sum of the page numbers that Takahashi needs to check, modulo $ 10^9+7 $.

The information about the permutation is given as $ P_1 $, $ P_2 $, ..., $ P_N $. When $ P_i=0 $, it means that the $ i $ -th number in the permutation is forgotten; otherwise, the $ i $ -th number in the permutation is $ P_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ P_1 $ $ P_2 $ $ ... $ $ P_N $

Output Format

Output the sum of the page numbers that Takahashi needs to check, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4
0 2 3 0

Sample Output #1

23

Sample Input #2

3
0 0 0

Sample Output #2

21

Sample Input #3

5
1 2 3 5 4

Sample Output #3

2

Sample Input #4

1
0

Sample Output #4

1

Sample Input #5

10
0 3 0 0 1 0 4 0 0 0

Sample Output #5

953330050

Notes/Hints

Constraints

• $ 1≦N≦500000 $
• $ 0≦P_i≦N $
• If $i≠j\ (1≦i,j≦N)$ and $ P_i≠0 $ and $ P_j≠0 $, then $ P_i≠P_j $

Partial Points

• Correctly solving the dataset where $ 1≦N≦3000 $ will award $ 500 $ points.

Sample Explanation 1

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

Sample Explanation 2

All permutations of length $ 3 $ are possible, so the answer is $1+2+3+4+5+6\ =\ 21$.

Sample Explanation 3

Takahashi remembers the permutation perfectly.

Sample Explanation 4

The dictionary consists of only $ 1 $ page.

见题面 Input 部分

见题面 Output 部分