给定一个包含 $n$ 个节点和 $m$ 条边的有向无环图（DAG）。图中恰好有一个节点 $x$ 没有出边。第 $i$ 个节点上有一个整数值 $a_i$。

每一秒钟，会发生以下过程： 对于每个节点 $i$，令 $b_i = a_i$。 对于每个节点 $i$，令 $a_i = 0$。 对于每个节点 $i$ 以及所有满足存在从 $i$ 到 $j$ 的边的节点 $j$，将 $b_i$ 加到 $a_j$ 上。 将值 $\lfloor \frac{b_x}{2} \rfloor$ 加到 $a_x$ 上。

求所有 $a_i$ 变为 0 的第一个时刻。由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^4$; $1 \le m \le 10^5$)，表示图中的顶点数和边数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示各顶点上的初始值。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示一条从 $u$ 到 $v$ 的有向边。

保证该图是一个没有重边的 DAG，且恰好有一个节点没有出边。

输出格式

输出一行，包含一个整数：所有 $a_i$ 变为 0 的第一个时刻，对 $998\,244\,353$ 取模。

样例

样例输入 1

3 2
1 1 1
1 2
2 3

样例输出 1

3

样例输入 2

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

样例输出 2

8

样例输入 3

5 6
7 2 3 6 6
1 2
1 4
2 3
3 4
3 5
4 5

样例输出 3

9

说明

嗨，这对我来说似乎是一个著名的巧合。（Codeforces 1704E）