{"raw_statement":[{"iden":"problem statement","content":"We have a grid with $N$ rows and $M$ columns. We denote by $(i,j)$ the cell in the $i$\\-th row from the top and $j$\\-th column from the left.\nYou are given integer sequences $A=(A_1,A_2,\\dots,A_K)$ and $B=(B_1,B_2,\\dots,B_L)$ of lengths $K$ and $L$, respectively.\nFind the sum, modulo $998244353$, of the answers to the following question over all integer pairs $(i,j)$ such that $1 \\le i \\le K$ and $1 \\le j \\le L$.\n\n*   A piece is initially placed at $(1,A_i)$. How many paths are there to take it to $(N,B_j)$ by repeating the following move $(N-1)$ times?\n    *   Let $(p,q)$ be the piece's current cell. Move it to $(p+1,q-1),(p+1,q)$, or $(p+1,q+1)$, without moving it outside the grid."},{"iden":"constraints","content":"*   $1 \\le N \\le 10^9$\n*   $1 \\le M,K,L \\le 10^5$\n*   $1 \\le A_i,B_j \\le M$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$ $K$ $L$\n$A_1$ $A_2$ $\\dots$ $A_K$\n$B_1$ $B_2$ $\\dots$ $B_L$"},{"iden":"sample input 1","content":"3 4 1 2\n1\n1 2"},{"iden":"sample output 1","content":"4\n\nFor $(i,j)=(1,1)$, the following two paths are possible:\n\n*   $(1,1) \\rightarrow (2,1) \\rightarrow (3,1)$\n*   $(1,1) \\rightarrow (2,2) \\rightarrow (3,1)$\n\nFor $(i,j)=(1,2)$, the following two paths are possible:\n\n*   $(1,1) \\rightarrow (2,1) \\rightarrow (3,2)$\n*   $(1,1) \\rightarrow (2,2) \\rightarrow (3,2)$\n\nThus, the answer is $2 + 2 =4$."},{"iden":"sample input 2","content":"5 8 4 5\n3 1 4 1\n2 7 1 8 2"},{"iden":"sample output 2","content":"137"},{"iden":"sample input 3","content":"883671387 87719 10 12\n86879 64174 47274 41688 17713 50897 53989 7210 30894 5714\n60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721"},{"iden":"sample output 3","content":"941873621"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}