← 返回题目列表

AtCoder · abc317_h

Ex. 步行

中文机器翻译题面 查看原题

分数: 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

下图显示了该图。

image

以下六次行走满足条件。

  • 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