{"raw_statement":[{"iden":"problem statement","content":"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$.\nYou 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?\n\n*   $A_i$ is an integer between $1$ and $N$ (inclusive).\n*   $A_0 = S$\n*   $A_K = T$\n*   There is an edge that directly connects Vertex $A_i$ and Vertex $A_{i+1}$.\n*   Integer $X\\ (X≠S,X≠T)$ appears even number of times (possibly zero) in sequence $A$.\n\nSince the answer can be very large, find the answer modulo $998244353$."},{"iden":"constraints","content":"*   All values in input are integers.\n*   $2≤N≤2000$\n*   $1≤M≤2000$\n*   $1≤K≤2000$\n*   $1≤S,T,X≤N$\n*   $X≠S$\n*   $X≠T$\n*   $1≤U_i<V_i≤N$\n*   If $i ≠ j$, then $(U_i, V_i) ≠ (U_j, V_j)$."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$ $K$ $S$ $T$ $X$\n$U_1$ $V_1$\n$U_2$ $V_2$\n$\\vdots$\n$U_M$ $V_M$"},{"iden":"sample input 1","content":"4 4 4 1 3 2\n1 2\n2 3\n3 4\n1 4"},{"iden":"sample output 1","content":"4\n\nThe following $4$ sequences satisfy the conditions:\n\n*   $(1, 2, 1, 2, 3)$\n*   $(1, 2, 3, 2, 3)$\n*   $(1, 4, 1, 4, 3)$\n*   $(1, 4, 3, 4, 3)$\n\nOn 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$."},{"iden":"sample input 2","content":"6 5 10 1 2 3\n2 3\n2 4\n4 6\n3 6\n1 5"},{"iden":"sample output 2","content":"0\n\nThe graph is not necessarily connected."},{"iden":"sample input 3","content":"10 15 20 4 4 6\n2 6\n2 7\n5 7\n4 5\n2 4\n3 7\n1 7\n1 4\n2 9\n5 10\n1 3\n7 8\n7 9\n1 6\n1 2"},{"iden":"sample output 3","content":"952504739\n\nFind the answer modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}