当前没有测试数据。

E - 王牌塔炮

分数：500分

题目描述

给你一个简单的无向图，有$N$个顶点和$M$条边。顶点从$1$到$N$编号，边从$1$到$M$编号。第$i$条边连接顶点$U_i$和顶点$V_i$。

给你整数$K, S, T$和$X$。有多少个满足以下条件的序列$A = (A_0, A_1, \dots, A_K)$？

• $A_i$是一个从$1$到$N$之间的整数（包括$1$和$N$）
• $A_0 = S$
• $A_K = T$
• 有一条直接连接$A_i$和$A_{i+1}$的边
• 整数$X (X≠S, X≠T)$在序列$A$中出现的次数是偶数（包括$0$）

因为答案可能很大，所以需要对$998244353$取模。

限制

• 输入中的所有值为整数。
• $2≤N≤2000$
• $1≤M≤2000$
• $1≤K≤2000$
• $1≤S,T,X≤N$
• $X≠S$
• $X≠T$
• $1≤U_i<V_i≤N$
• 如果$i ≠ j$，那么$(U_i, V_i) ≠ (U_j, V_j)$。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $K$ $S$ $T$ $X$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

输出

在$998244353$下输出答案。

4 4 4 1 3 2
1 2
2 3
3 4
1 4

4

以下$4$个序列满足条件：

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

但是$(1, 2, 3, 4, 3)$和$(1, 4, 1, 2, 3)$不满足条件，因为$2$的出现次数是奇数。

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

0

图不一定连通。

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

952504739

计算结果对$998244353$取模。