問題一覧 > 通常問題

No.1001 The Permutation of Many Orders

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 77
作問者 : tempura_pp / テスター : tsutaj
お気に入りにしたユーザー ProblemId : 3978 / 自分の提出
問題文最終更新日: 2020-02-27 22:21:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 239 (順位表) の他の問題:

Problem Statement

Find the number, modulo $10^9+7$, of permutations $p_1, p_2, \ldots , p_N$ of the integers between $1$ and $N$, inclusive, that satisfy the following condition.

  • For every integer $i$ ($1\leq i\leq N$), the following holds:
    • if $t_i = 1$, then $p_i\geq X_i$
    • if $t_i = 0$, then $p_i\leq X_i$

Input

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

  • All inputs are integers.
  • $1\leq N\leq 3000$
  • $t_i = 0,\ 1 $
  • $1\leq X_i\leq N$

Output

Output the number of permutations satisfying the condition, modulo $10^9+7$. Print a newline at the end.

Sample

Sample 1
Input
3
1 2
0 1
1 1
Output
2

There are $2$ such permutations: $(2,1,3)$ and $(3,1,2)$.

Sample 2
Input
4
1 4
1 4
1 4
1 4
Output
0

Sample 3
Input
10
1 3
1 1
0 4
1 1
0 5
0 9
1 2
0 6
1 5
0 3
Output
37314

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