分数: 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 (含)。
- A_0 = S
- A_K = T
- 有一条边直接连接Vertex A_i 和顶点 A_{i+1}.
- 整数 X\ (X≠S,X≠T) 按顺序出现偶数次(可能为零) A.
由于答案可能非常大,请对答案求模 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
- If 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.
示例输入 1
4 4 4 1 3 2 1 2 2 3 3 4 1 4
示例输出 1
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.
示例输入 2
6 5 10 1 2 3 2 3 2 4 4 6 3 6 1 5
示例输出 2
0
该图不一定相连。
示例输入 3
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
示例输出 3
952504739
求模答案 998244353.