Permutation

Time Limit : 1 sec, Memory Limit : 65536 KB

蕶

ȉ̏𖞂 $X_1, X_2, ..., X_N$ ̌߂B

1. Cӂ̐ $i$ ($1 \leq i \leq N$)ɑ΂āA$X_j=i$ ƂȂ $j$ ($1 \leq j \leq N$)݂B
2. $X_s = t$
3. $X_{a_i} < X_{b_i}$ ($1 \leq i \leq C$)

͈͂ȉ̌`ɏ]B^鐔͑SĐłB

$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$

o

𖞂̌ $10^9+7$ Ŋ]1sɏo͂(𖞂̌LȂƂ͊ȒPɎ)B

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𖞂B

4 2 1 1
2 3
3 2

Output for the Sample Input 2

0

$X_2<X_3$ $X_3<X_2$ 𖞂݂͑ȂB

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