Description

不妨假设枫叶上有 $n$ 个穴位，穴位的编号为 $1\sim n$。有若干条有向的脉络连接着这些穴位。

穴位和脉络组成一个有向无环图——称之为脉络图（例如图 $1$），穴位的编号使得穴位 $1$ 没有从其他穴位连向它的脉络，即穴位 $1$ 只有连出去的脉络；由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 $1$ 为根的包含全部 $n$ 个穴位的一棵树——称之为脉络树（例如图 $2$ 和图 $3$ 给出的树都是图 $1$ 给出的脉络图的子图）。

值得注意的是，脉络图中的脉络树方案可能有多种可能性，例如图 $2$ 和图 $3$ 就是图 $1$ 给出的脉络图的两个脉络树方案。

脉络树的形式化定义为：以穴位 $r$ 为根的脉络树由枫叶上全部 $n$ 个穴位以及 $(n-1)$ 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于枫叶上的每个穴位 $s$，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位 $r$ 出发沿着这条路径可以到达穴位 $s$。

现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 $2$ 个穴位但方向不同的脉络是不同的脉络，例如从穴位 $3$ 到 $4$ 的脉络与从 $4$ 到 $3$ 的脉络是不同的脉络，因此，图 $1$ 中不能添加从 $3$ 到 $4$ 的脉络，但可添加从 $4$ 到 $3$ 的脉络）。这条新脉络可以是从一个穴位连向自身的（例如，图 1 中可添加从 $4$ 到 $4$ 的脉络）。

原脉络图添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。 请你求出添加了这一条脉络之后的新脉络图的以穴位 $1$ 为根的脉络树方案数。

由于方案可能有太多太多，请输出方案数对 $(10^9+7)$ 取模后得到的结果。

Input Format

输入文件的第一行包含四个整数 $n,m,x,y$，依次代表枫叶上的穴位数、脉络数，以及要添加的脉络是从穴位 $x$ 连向穴位 $y$ 的。

接下来 $m$ 行，每行两个整数，由空格隔开，代表一条脉络。

第 $i$ 行的两个整数为 $u_i$ 和 $v_i$，代表第 $i$ 条脉络是从穴位 $u_i$ 连向穴位 $v_i$ 的。

Output Format

输出一行，为添加了从穴位 $x$ 连向穴位 $y$ 的脉络后，枫叶上以穴位 $1$ 为根的脉络树的方案数对 $(10^9+7)$ 取模得到的结果。

4 4 4 3
1 2
1 3
2 4
3 2

3

Hint

对于所有测试数据，保证：

• $1 \leq n \leq 100000$；
• $n - 1 \leq m \leq \min(200000, n(n -1)/2)$；
• $1 \leq x, y, u_i, v_i \leq n$。

Fixed by Starrykiller.