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