Description

在经过 $99$ 次的 Replay 后，沙耶终于发现迷宫是一个有向无环图。为了保证最后一次 Replay 的趣味性，时风瞬给沙耶和理树安排了一个小游戏。

这张有向无环图 $G$ 有 $n$ 个点，$m$ 条边，每条边的长度为 $1$。设 $l_i$ 为初始点 $s$ 到第 $i$ 条边所指向的点 $u$ 的最短路，定义第 $i$ 条边的边权为 $p-l_i$。游戏步骤是这样的（所有选择都是按如下顺序进行，并且每个人的选择都是公开的）。

1. 理树站在点 $s$ 上。
2. 时风瞬会随机选取一个点作为 $t$（$t$ 可以等于 $s$）。
3. 如果无法从 $s$ 到达 $t$，游戏直接结束。
4. 沙耶需要选择一条边。
5. 理树需要找到一条从 $s$ 到 $t$ 的路径。
6. 若沙耶选择的边在理树所选择的路径上，则理树就会将这条边的边权的钱给沙耶。

理树希望能少输钱，沙耶希望能多拿钱。若两方都采取最优策略，请问沙耶期望能得到多少钱。

Input Format

第一行四个整数 $n,m,s,p$，分别代表有向图点数，边数与理树站在的位置，以及题目中出现的 $p$。

接下来 $m$ 行每行两个整数 $u_i,v_i$ 描述一条边。

Output Format

一行一个整数代表答案。

请对 $998244353$ 取模。

8 8 1 10
1 2
1 3
1 4
2 5
3 5
5 6
6 7
6 8

6

3 2 1 3
1 2
1 3

332748119

Hint

样例 1 解释

比如 $t=6$ 时，沙耶应该选择连接 $5,6$ 的那条边；$t=8$ 时，沙耶仍然应该选择连接 $5,6$ 的那条边；$t=4$ 时，应该选择连接 $1,4$ 的那条边；$t=5$ 时，沙耶无论选择什么边都不会得到钱。

设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,9,9,9,0,7,7,7\}$。

样例 2 解释

设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,2,2\}$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$n,m \le 5$；
• Subtask 2（20 pts）：$m=n-1$，$u_i<v_i$，$s=1$；
• Subtask 3（30 pts）：$n,m \le 10^3$；
• Subtask 4（40 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n,m \le 5 \times 10^6$，$1 \le s \le n$，$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$n\le p \le 10^9$。