既见君子

友情客串：wygz（无忧公主） wygz 每次从进校到机房，都要尽量避开“屠夫”老师。然而，有一天，她忽然发现一些门上居然贴了“请勿从此门进出”的标签！

校园可以抽象成一张 $n$ 个点 $m$ 条无向边（可能有重边，无自环）的**连通**无向图，点从 $1$ 标号到 $n$。校门在 $1$ 号点，而机房在 $n$ 号点，屠老师的办公室在点 $z$（$z\ne 1,n$）。 然而，工作人员（~~其实是樱初音~~）封锁了其中的 $m-n+1$ 条边，使得剩余的图（包括所有点以及剩余的边）仍然连通，此时任意两点之间有且仅有一条简单路径。工作人员会**等概率地**选择一种封锁方案。（若 $m=n-1$ 则不封锁任何边，保持不变） wygz 当然不希望屠老师的办公室出现在她的必经之路上。她希望你算出从校门到机房的路径**必须**经过屠老师的办公室的概率。答案对 $998244353$ 取模。

第一行三个正整数 $n$、$m$ 和 $z$，表示点数、边数和屠老师的办公室的位置。 以下 $m$ 行，每行两个正整数 $u$、$v$，表示一条连接 $u$ 和 $v$ 的无向边。

一行一个非负整数，表示答案对 $998244353$ 取模的结果。

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

374341633

6 8 4
1 2
1 3
2 3
2 4
2 5
4 5
4 6
5 6

374341633

#### 样例解释： 样例 #1：生成树共 $8$ 个，有 $5$ 个满足 $1$ 到 $4$ 经过 $2$。$\dfrac 5 8\equiv 374341633\pmod {998244353}$。 样例 #2：生成树共 $24$ 个，有 $15$ 个满足 $1$ 到 $6$ 经过 $4$。$\dfrac {15} {24}\equiv 374341633\pmod {998244353}$。 #### 数据范围： | 数据点编号 | $n$ | $m$ | | :----------: | :----------: | :----------: | | $1$ | $=3$ | $\le 5$ | | $2$ | $=3$ | $\le 10^5$ | | $3,4$ | $=7$ | $\le 15$ | | $5,6$ | $=7$ | $\le 10^5$ | | $7$ | $=20$ | $=n-1$ | | $8,9$ | $=20$ | $=n$ | | $10,11,12$ | $=18$ | $\le 10^5$ | | $13,14,15,16$ | $=19$ | $\le 10^5$ | | $17,18,19,20$ | $=20$ | $\le 10^5$ | 对 $100\%$ 的数据，$3\le n\le 20$，$n-1\le m\le 10^5$，$z\ne 1$ 且 $z\ne n$。 **数据保证输入的图的生成树个数模 $998244353$ 非零。**