{"raw_statement":[{"iden":"problem statement","content":"We have a directed graph with $N$ vertices numbered $1$ to $N$. The graph has no multi-edges but can have self-loops. Also, every edge in the graph satisfies the following condition.\n\n*   If the edge goes from vertex $s$ to vertex $t$, then $s$ and $t$ satisfy at least one of $0 \\leq t - s\\leq 2$ and $t = 1$.\n\nThe presence or absence of an edge in the graph is represented by sequences $A, B, C, D$, each of length $N$. Each element of $A, B, C, D$ has the following meaning. (Let $A_n$ denote the $n$\\-th element of $A$; the same applies to $B_n, C_n, D_n$.)\n\n*   $A_n$ is $1$ if there is an edge from vertex $n$ to vertex $n$, and $0$ otherwise.\n*   $B_n$ is $1$ if there is an edge from vertex $n$ to vertex $n+1$, and $0$ otherwise. (Here, $B_N = 0$.)\n*   $C_n$ is $1$ if there is an edge from vertex $n$ to vertex $n+2$, and $0$ otherwise. (Here, $C_{N-1} = C_N = 0$.)\n*   $D_n$ is $1$ if there is an edge from vertex $n$ to vertex $1$, and $0$ otherwise. (Here, $D_1 = A_1$.)\n\nIn the given graph, find the number, modulo $998244353$, of walks with $K$ edges starting at vertex $1$ and ending at vertex $N$.\nHere, a walk with $K$ edges starting at vertex $1$ and ending at vertex $N$ is a sequence of vertices $v_0 = 1, v_1, \\dots, v_K = N$ such that for each $i$ $(0 \\leq i \\lt K)$ there is an edge from vertex $v_i$ to vertex $v_{i + 1}$. Two walks are distinguished when they differ as sequences."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5 \\times 10^4$\n*   $1 \\leq K \\leq 5 \\times 10^5$\n*   $A_i, B_i, C_i, D_i \\in \\lbrace 0, 1 \\rbrace$\n*   $A_1 = D_1$\n*   $B_N = C_{N-1} = C_N = 0$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$B_1$ $B_2$ $\\dots$ $B_N$\n$C_1$ $C_2$ $\\dots$ $C_N$\n$D_1$ $D_2$ $\\dots$ $D_N$"},{"iden":"sample input 1","content":"3 3\n1 0 1\n1 1 0\n1 0 0\n1 0 1"},{"iden":"sample output 1","content":"6\n\nThe following figure shows the graph.\n![image](https://img.atcoder.jp/abc317/2106e1b4faaa87d208ed3e3a275cda1b.jpg)\nThe following six walks satisfy the conditions.\n\n*   $1, 1, 1, 3$\n*   $1, 1, 2, 3$\n*   $1, 1, 3, 3$\n*   $1, 2, 3, 3$\n*   $1, 3, 1, 3$\n*   $1, 3, 3, 3$"},{"iden":"sample input 2","content":"4 6\n1 1 1 1\n1 1 1 0\n1 1 0 0\n1 0 0 0"},{"iden":"sample output 2","content":"50"},{"iden":"sample input 3","content":"10 500000\n0 1 0 1 0 0 0 0 1 1\n1 1 1 0 1 1 1 0 1 0\n0 0 1 1 0 0 1 1 0 0\n0 1 1 1 1 1 0 1 1 0"},{"iden":"sample output 3","content":"866263864"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}