Ex - Simple Path Counting Problem

AtCoder

IDabc309_h

Time10000ms

Memory256MB

Difficulty—

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. You 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. Find 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$. * 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? * 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. ## Constraints * $1 \le N \le 10^9$ * $1 \le M,K,L \le 10^5$ * $1 \le A_i,B_j \le M$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $K$ $L$ $A_1$ $A_2$ $\dots$ $A_K$ $B_1$ $B_2$ $\dots$ $B_L$ [samples]

Samples

Input #1

3 4 1 2
1
1 2

Output #1

4

For $(i,j)=(1,1)$, the following two paths are possible:

*   $(1,1) \rightarrow (2,1) \rightarrow (3,1)$
*   $(1,1) \rightarrow (2,2) \rightarrow (3,1)$

For $(i,j)=(1,2)$, the following two paths are possible:

*   $(1,1) \rightarrow (2,1) \rightarrow (3,2)$
*   $(1,1) \rightarrow (2,2) \rightarrow (3,2)$

Thus, the answer is $2 + 2 =4$.

Input #2

5 8 4 5
3 1 4 1
2 7 1 8 2

Output #2

Input #3

883671387 87719 10 12
86879 64174 47274 41688 17713 50897 53989 7210 30894 5714
60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721

Output #3

941873621

API Response (JSON)

{
  "problem": {
    "name": "Ex - Simple Path Counting Problem",
    "description": {
      "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. You are given integer sequences $A=(A_1,A_2,\\dots,A_K)$ an",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc309_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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)$ an...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments