{"problem":{"name":"King Bombee","description":{"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$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc244_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   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)$.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc244_e","tags":[],"sample_group":[["4 4 4 1 3 2\n1 2\n2 3\n3 4\n1 4","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$."],["6 5 10 1 2 3\n2 3\n2 4\n4 6\n3 6\n1 5","0\n\nThe graph is not necessarily connected."],["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","952504739\n\nFind the answer modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}