J. Gensokyo Autobahn
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Mystia's Izakaya has $$$n$$$ branches in Gensokyo, numbered from $$$1$$$ to $$$n$$$. There are $$$m$$$ one-way roads of length $$$1$$$ between these $$$n$$$ branches, with the $$$i$$$-th road leading from branch $$$u_i$$$ to branch $$$v_i$$$.

To strengthen the connections between the branches, Mystia decided to build some more roads, so she hired $$$k$$$ construction teams. For the $$$i$$$-th team, Mystia will uniformly randomly select an integer $$$j$$$ from $$$[1, m] \cap \mathbb{Z}$$$ and assign the $$$i$$$-th construction team to build $$$a_i$$$ one-way roads of length $$$1$$$ from branch $$$u_j$$$ to branch $$$v_j$$$. The integers $$$j$$$ selected for the construction teams are independent of each other.

The two largest branches of the Izakaya are branch $$$1$$$ and branch $$$n$$$. Your task is to help Mystia calculate the expected number of shortest paths from branch $$$1$$$ to branch $$$n$$$ after the road construction is completed. The answer should be modulo $$$998244353$$$.

Input

The first line contains three integers $$$n, m, k$$$ ($$$2 \le n \le 2 \times 10^5, 1 \le m \le 2 \times 10^5, 1 \le k \le 2 \times 10^5$$$).

The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$), representing a one-way road from branch $$$u_i$$$ to branch $$$v_i$$$.

The next line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le 10^9$$$), representing the number of roads each construction team will build.

It is guaranteed that there is at least one path from branch $$$1$$$ to branch $$$n$$$.

There may be multiple edges and self-loops in the graph.

Output

Output a single integer, the expected number of shortest paths from branch $$$1$$$ to branch $$$n$$$ modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Examples
Input
4 4 1
1 2
1 3
2 4
3 4
2
Output
4
Input
3 5 2
1 1
1 2
1 2
2 1
2 3
5 3
Output
399297752
Input
9 8 5
1 3
3 2
1 4
4 2
4 5
2 9
5 9
7 8
1 2 3 4 5
Output
308052020