AT_codefestival_2016_qualC_e 順列辞書

[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_e ある日高橋君は、$ 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 $ であることを意味します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ ... $ $ P_N $

高橋くんが調べる必要のあるページ番号の総和を $ 10^9+7 $ で割ったあまりを出力せよ。

### 制約 - $ 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 $ 点が与えられる。 ### Sample Explanation 1 ありうる順列は$ [1,2,3,4] $と$ [4,2,3,1] $です。前者は$ 1 $ページ目に、後者は$ 22 $ページ目に載っているため、答えは$ 23 $です。 ### Sample Explanation 2 長さ$ 3 $の全ての順列がありうるので、答えは$ 1+2+3+4+5+6\ =\ 21 $ になります。 ### Sample Explanation 3 高橋君は完全に順列を記憶しています。 ### Sample Explanation 4 辞書は$ 1 $ページからなります。