No.35 Queue

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

$N$ 枚のカードからなる山があります。
それぞれのカードには $1$ 以上 $N$ 以下の数字が書かれていて、山の上から $i$ 番目のカードに書かれた数字を $A_i$ とすると、数列 $A$ は $(1,2,\dots ,N)$ の順列になっています。MAK君は $1$ 以上 $N$ 以下の数 $k$ を決めた後、カードの山に対して次の 操作を何回か行おうと考えています。なお、$k$ の値は変更することができません。

操作：山の上から $k$ 番目までのカードに書かれている数字の最小値を求めて、その値が書かれたカードを新たに山の一番下に置く 。
　　　この時、山は $N+1$ 枚のカードからなる。その後、山の一番上にあるカードを捨てる。

MAK君は実際にこの操作を行う前に、この操作とカードの山の関係性について調べました。その結果、山の一番上にあるカードに書か れた数字が $i(1\le i\le N)$ になるには、$k$ の値を $K_i$ にして操作を $T_i$ 回行えばよいことがわかりました。その翌日、なぜかカードの山が消えていて、MAK君が調べた $K_i,T_i$ の値も一部消えていました。ただし、$1\le i\le N$ を満たす $i$ につい て$K_i,T_i$ の値は、どちらも消えていないかどちらも消えているのいずれかでした。また、$K_i,T_i$ の値が消えているとき、$K_i,T_i$ の値は $-1$ とします。MAK君は消えていない $K_i,T_i$ の値をもとにカードの山を復元しようと思いました。考えられるカードの山の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので、$1{,}000{,}000{,}007=10^9+7$ で割った時 の余りを出力してください。なお、MAK君の計算ミスにより、考えられるカードの山が存在しない場合があります。その場合は $-1$ を出力してください。

制約

• $1\le N\le 10^5$
• $-1\le K_i\le N,K_i\neq 0$
• $-1\le T_i\le 10^{18}$
• $K_i=-1$ ならば $T_i=-1$
• $T_i=-1$ ならば $K_i=-1$

入力形式

入力は以下の形式で標準入力から与えられる。

N
K_1 T_1
K_2 T_2
   .
   .
   .
K_N T_N

出力

考えられるカードの山の通り数を $1{,}000{,}000{,}007$ で割った時の余りを出力してください。ただし、考えられるカードが存在 しない場合、$-1$ 出力してください。

入出力例

4
3 4
-1 -1
1 7
4 1

2

考えられるカードの山の一つとして $\begin{pmatrix} 1 \\ 4 \\ 2 \\ 3 \end{pmatrix}$ があります。
この場合、$k=3$ として操作を繰り返すと次のようになります。

$\begin{pmatrix} 1 \\ 4 \\ 2 \\ 3 \end{pmatrix}\rightarrow \begin{pmatrix} 4 \\ 2 \\ 3 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 2 \\ 3 \\ 1 \\ 2 \end{pmatrix}\rightarrow \begin{pmatrix} 3 \\ 1 \\ 2 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 1 \\ 2 \\ 1 \\ 1 \end{pmatrix}\rightarrow \dots$

$k=1$ の場合、次のようになります。

$\begin{pmatrix} 1 \\ 4 \\ 2 \\ 3 \end{pmatrix}\rightarrow \begin{pmatrix} 4 \\ 2 \\ 3 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 2 \\ 3 \\ 1 \\ 4 \end{pmatrix}\rightarrow \begin{pmatrix} 3 \\ 1 \\ 4 \\ 2 \end{pmatrix}\rightarrow \begin{pmatrix} 1 \\ 4 \\ 2 \\ 3 \end{pmatrix}\rightarrow \dots$

$k=4$ の場合、次のようになります。

$\begin{pmatrix} 1 \\ 4 \\ 2 \\ 3 \end{pmatrix}\rightarrow \begin{pmatrix} 4 \\ 2 \\ 3 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 2 \\ 3 \\ 1 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 3 \\ 1 \\ 2 \\ 1 \end{pmatrix}\rightarrow \begin{pmatrix} 1 \\ 2 \\ 1 \\ 1 \end{pmatrix}\rightarrow \dots$

2
2 5
2 5

-1

明らかに矛盾しています。

3
3 1000000000000000000
1 0
-1 -1

2

$T_i$ の値が $0$ の時もあります。

6
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1

720

考えられるカードの山は $(1,2,3,4,5,6)$ の順列です。