問題文

ある日高橋君は、$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