問題文

$1$ 以上 $N$ 以下の整数の順列 $p_1,p_2,\dots ,p_N$ であって、 以下の条件をみたす順列の個数を ${10}^9+7$ でわった余りを計算してください。

• すべての整数 $i$ ($1\le i\le N$) について以下をみたす。
  • $t_i=1$ ならば $p_i\ge X_i$
  • $t_i=0$ ならば $p_i\le X_i$

入力

$N$
$t_1{X}_1$
$t_2{X}_2$
$⋮$
$t_N{X}_N$

• 入力はすべて整数
• $1\le N\le 3000$
• $t_i=0,1$
• $1\le X_i\le N$

出力

条件をみたす順列の個数を ${10}^9+7$ で割った余りを出力してください。 最後に改行してください。

サンプル

3
1 2
0 1
1 1

2

4
1 4
1 4
1 4
1 4

0

10
1 3
1 1
0 4
1 1
0 5
0 9
1 2
0 6
1 5
0 3

37314