問題文

以下の条件を満たす整数列 $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$ を満たす数列は存在しない。