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\ne S,X\ne 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$\ >$\cdots$\ >$U_M$ $V_M$ #### Constraints - All values in input are integers. - $2\le N\le 2000$ - $1\le M\le 2000$ - $1\le K\le 2000$ - $1\le S, T, X\le N$ - $X\ne S$ - $X\ne T$ - $1\le U_i\lt V_i\le N$ - If $i\ne j$, then $(U_i,V_i)\ne (U_j,V_j)$.

Print the answer modulo $998244353$.

***For Sample #1:*** 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$. ***For Sample #2:*** The graph is not necessarily connected.

AtCoder [ABC244E]