No.1001 注文の多い順列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : tempura_pptempura_pp / テスター : tsutajtsutaj
21 ProblemId : 3978 / 出題時の順位表
問題文最終更新日: 2020-02-27 22:21:14

問題文

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

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

入力

$N$
$t_1\ X_1$
$t_2\ X_2$
$\vdots$
$t_N\ X_N$

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

出力

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

サンプル

サンプル1
入力
3
1 2
0 1
1 1
出力
2

$(2,1,3)$ と $(3,1,2)$ の $2$ つです。

サンプル2
入力
4
1 4
1 4
1 4
1 4
出力
0

サンプル3
入力
10
1 3
1 1
0 4
1 1
0 5
0 9
1 2
0 6
1 5
0 3
出力
37314

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。