题目描述

有一个有 $N$ 个顶点的有向图，顶点编号为 $1$ 到 $N$。图中不存在重边，但可能存在自环。此外，图中所有的边都满足以下条件：

• 假设有一条从顶点 $s$ 指向顶点 $t$ 的边，则 $s,\ t$ 至少满足 $0 \leq t - s \leq 2$ 或 $t = 1$ 之一。

图中边的存在情况由长度为 $N$ 的数列 $A,B,C,D$ 给出。$A,\ B,\ C,\ D$ 的每个元素含义如下（以下 $A$ 的第 $n$ 个元素记为 $A_n$，$B_n,\ C_n,\ D_n$ 同理）：

• $A_n$：如果存在从顶点 $n$ 到顶点 $n$ 的边，则 $A_n = 1$，否则 $A_n = 0$。
• $B_n$：如果存在从顶点 $n$ 到顶点 $n+1$ 的边，则 $B_n = 1$，否则 $B_n = 0$（其中 $B_N = 0$）。
• $C_n$：如果存在从顶点 $n$ 到顶点 $n+2$ 的边，则 $C_n = 1$，否则 $C_n = 0$（其中 $C_{N-1} = C_N = 0$）。
• $D_n$：如果存在从顶点 $n$ 到顶点 $1$ 的边，则 $D_n = 1$，否则 $D_n = 0$（其中 $D_1 = A_1$）。

请你求出，在给定的图中，从顶点 $1$ 出发，以顶点 $N$ 结束，且恰好经过 $K$ 条边的 walk 的数量，并对 $998244353$ 取模。

这里，“从顶点 $1$ 出发，以顶点 $N$ 结束，且恰好经过 $K$ 条边的 walk”指的是一个顶点序列 $v_0 = 1, v_1, \dots, v_K = N$，对于每个 $i$（$0 \leq i < K$），存在从 $v_i$ 到 $v_{i+1}$ 的有向边。两个 walk 只要顶点序列不同就视为不同。

输入格式

输入以如下格式从标准输入给出。

$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$

输出格式

请输出从顶点 $1$ 出发，以顶点 $N$ 结束，且恰好经过 $K$ 条边的 walk 的数量，对 $998244353$ 取模。

样例 1

输入

3 3
1 0 1
1 1 0
1 0 0
1 0 1

输出

6

样例 2

输入

4 6
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0

输出

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

输出

866263864

说明/提示

约束条件

• $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$

样例解释 1

将给定的图画出来如下所示。

满足条件的 walk 有如下 $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$

由 ChatGPT 4.1 翻译