Permutation

Time Limit : 1 sec, Memory Limit : 65536 KB

問題文

以下の条件を満たす整数列 X_1, X_2, ..., X_N の個数を求めよ。

  1. 任意の整数 i (1 \leq i \leq N)に対して、X_j=i となる j (1 \leq j \leq N)が存在する。
  2. X_s = t
  3. X_{a_i} < X_{b_i} (1 \leq i \leq C)

入力

入力は以下の形式に従う。与えられる数は全て整数である。

N C s t
a_1 b_1
a_2 b_2
...
a_C b_C

制約

  • 1 \leq N \leq 2000
  • 0 \leq C \leq N
  • 1 \leq s \leq N
  • 1 \leq t \leq N
  • 1 \leq a_i \leq N
  • 1 \leq b_i \leq N
  • a_i \neq b_i
  • i \neq j ならば a_i \neq a_j

出力

条件を満たす数列の個数を 10^9+7 で割った余りを1行に出力せよ(条件を満たす数列の個数がたかだか有限個しかないことは簡単に示される)。

Sample Input 1

3 1 1 1
1 3

Output for the Sample Input 1

2

\{X_1, X_2, X_3\} = \{1, 2, 3\}, \{1, 3, 2\} の2つが条件を満たす。

Sample Input 2

4 2 1 1
2 3
3 2

Output for the Sample Input 2

0

X_2<X_3 かつ X_3<X_2 を満たす数列は存在しない。


Source: Osaka University Programming Contest 2012 , Osaka, Japan, 2012-03-18