You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ through $N$, and the edges are numbered from $1$ through $M$. Edge $i$ connects Vertex $U_i$ and Vertex $V_i$.

You are given integers $K, S, T$, and $X$. How many sequences $A = (A_0, A_1, \dots, A_K)$ are there satisfying the following conditions?

-   $A_i$ is an integer between $1$ and $N$ (inclusive).
-   $A_0 = S$
-   $A_K = T$
-   There is an edge that directly connects Vertex $A_i$ and Vertex $A_{i+1}$.
-   Integer $X\ (X≠S,X≠T)$ appears even number of times (possibly zero) in sequence $A$.

Since the answer can be very large, find the answer modulo $998244353$.

Input is given from Standard Input in the following format:

```
$N$ $M$ $K$ $S$ $T$ $X$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$
```

Print the answer modulo $998244353$.

-   All values in input are integers.
-   $2≤N≤2000$
-   $1≤M≤2000$
-   $1≤K≤2000$
-   $1≤S,T,X≤N$
-   $X≠S$
-   $X≠T$
-   $1≤U_i<V_i≤N$
-   If $i ≠ j$, then $(U_i, V_i) ≠ (U_j, V_j)$.

4

The following 4 sequences satisfy the conditions:

• (1,2,1,2,3)
• (1,2,3,2,3)
• (1,4,1,4,3)
• (1,4,3,4,3)

On the other hand, (1,2,3,4,3) and (1,4,1,2,3) do not, since there are odd number of occurrences of 2.

0

The graph is not necessarily connected.