波奇酱有一张有 $n$个点，$m$ 条边，每条边的长度为 $1$ 的有向无环图。她还有一个常数 $p$。 设 $l_i$ 为初始点 $s$ 到第 $i$ 条边所指向的点 的最短路，那么第 $i$ 条边的价值就为 $p-l_i$ 。你需要玩一个游戏，游戏步骤是这样的：

一开始，波奇酱会指定一个节点 $s$ ，然后系统会从所有节点中（包括 ）随机选择一个节点 $t$ 。然后，你需要从所有边中选择一条边 $e$ 。

选择完毕，如果存在一条从 $s$ 到 $t$ 的路径 $P$ 不经过 $e$ ，那么的得分为 $0$ ；否则，你的得分为 $p-l_i$ 的价值。

你希望得到尽可能多的分数。请问你的得分期望是多少。结果对 998244353$ 取模。

输入格式

第一行四个整数 $n、m、s、p$ ，分别代表有向图点数，边数，初始点 ，以及常数 接下来 行每行两个整数 $u_i,v_i$ 描述一条边。

输出格式

一行一个整数代表答案。

样例输入 1:

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

样例输出 1

6

样例输入 2

3 2 1 3
1 2
1 3

样例输出2

332748119

对于所有数据，$1\le n\le m \le 10^6$ ，$1\le s\le n$ ，$1\le u_i,v_i \le n$ ，$u_i\neq v_i$ ，$n\le p\le 10^9$ 。保证对于所有$t$ ，都存在至少一条从$s$ 到$t$ 的路径。