分数: 650 点
问题陈述
我们有一个有向图 N 顶点编号 1 to N。该图没有多边,但可以有自环。此外,图中的每条边都满足以下条件。
- 如果边从顶点出发 s 到顶点 t,然后 s 和 t 满足至少一项 0 \leq t - s\leq 2 和 t = 1.
图中是否存在边由序列表示 A, B, C, D,每个长度 N。的每个元素 A, B, C, D 具有以下含义。 (让 A_n 表示 n- 第一个元素 A;这同样适用于 B_n, C_n, D_n.)
- A_n is 1 如果有来自顶点的边 n 到顶点 n,和 0 否则。
- B_n is 1 如果有来自顶点的边 n 到顶点 n+1,和 0 否则。 (这里, B_N = 0.)
- C_n is 1 如果有来自顶点的边 n 到顶点 n+2,和 0 否则。 (这里, C_{N-1} = C_N = 0.)
- D_n is 1 如果有来自顶点的边 n 到顶点 1,和 0 否则。 (这里, D_1 = A_1.)
在给定的图中,找到数字,模 998244353,与 K 从顶点开始的边 1 并在顶点结束 N.
在这里,与 K 从顶点开始的边 1 并在顶点结束 N 是一系列顶点 v_0 = 1, v_1, \dots, v_K = N 这样对于每个 i (0 \leq i \lt K) 顶点有一条边 v_i 到顶点 v_{i + 1}。当两条步行的顺序不同时,它们就被区分开来。
约束
- 2 \leq N \leq 5 \times 10^4
- 1 \leq K \leq 5 \times 10^5
- A_i, B_i, C_i, D_i \in \lbrace 0, 1 \rbrace
- A_1 = D_1
- B_N = C_{N-1} = C_N = 0
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \dots A_N B_1 B_2 \dots B_N C_1 C_2 \dots C_N D_1 D_2 \dots D_N
输出
打印数字,模数 998244353,长距离步行 K 从顶点开始 1 并在顶点结束 N.
示例输入 1
3 3 1 0 1 1 1 0 1 0 0 1 0 1
示例输出 1
6
下图显示了该图。

以下六次行走满足条件。
- 1, 1, 1, 3
- 1, 1, 2, 3
- 1, 1, 3, 3
- 1, 2, 3, 3
- 1, 3, 1, 3
- 1, 3, 3, 3
示例输入 2
4 6 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0
示例输出 2
50
示例输入 3
10 500000 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 0
示例输出 3
866263864