問題一覧 > 通常問題

No.2503 Typical Path Counting Problem on a Grid

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : suisen / テスター : emthrm torisasami4 rniya
お気に入りにしたユーザー ProblemId : 9928 / 自分の提出
問題文最終更新日: 2023-07-25 00:32:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 408 (順位表) の他の問題:

Problem Statement

You are given non-negative integers $n,m$.

Define a rectangular region $R$ on the two-dimensional plane by $R\coloneqq\lbrace (x,y)\mid 0 \leq x\leq n,\ 0\leq y\leq m\rbrace$.

Initially, suisen is at the point $(0, 0)\in R$.

suisen repeats the following action any number of times (possibly $0$ times) until reaching the point $(n, m)\in R$.

  • Let $(x, y)\in R$ be the point where suisen currently is. Choose $1$ of the following and perform it:

    1. Move to the point $(x + 1, y - 1)$.
    2. Move to the point $(x + 1, y)$.
    3. Move to the point $(x + 1, y + 1)$.
    4. Move to the point $(x, y + 1)$.
    5. Move to the point $(x - 1, y + 1)$.

    However, moving to a point not contained in $R$ and moving to a point that has already been visited at least $1$ time are prohibited.

Find the number of ways suisen can act until reaching the point $(n, m)\in R$, and print it modulo $998244353$.

You are given $T$ test cases; solve the above problem for all of them.

Input

The input is given from standard input in the following format.

First, the number of test cases $T$ is given on line $1$ in the following format.

$T$

Line $i + 1\ (1\leq i\leq T)$ contains integers $n, m$ representing the $i$-th test case, in the following format.

$n\ m$
  • All input values are integers.
  • $1 \leq T\leq 2\times 10 ^ 4$
  • $0 \leq n\leq 10 ^ 7$
  • $0 \leq m\leq \textcolor{red}{10 ^ {18}}$

Output

Print $T$ lines. On line $i \ (1\leq i\leq T)$, print the answer to the $i$-th test case modulo $998244353$.

Print a newline after line $T$ of the output as well.

Sample

Sample 1
Input
4
1 1
0 0
10 20
10000000 1000000000000000000
Output
5
1
839227761
950133829
  • About test case 1

    This represents $n = 1, m = 1$. The possible ways for suisen to act are the following $5$ ways. Therefore, print $5$.

    • $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }4}{\longrightarrow} (1,1)$
    • $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }5}{\longrightarrow} (0,1) \overset{\text{Action }2}{\longrightarrow} (1,1)$
    • $(0, 0) \overset{\text{Action }3}{\longrightarrow} (1, 1)$
    • $(0, 0) \overset{\text{Action }4}{\longrightarrow} (0, 1)\overset{\text{Action }2}{\longrightarrow} (1, 1)$
    • $(0, 0) \overset{\text{Action }4}{\longrightarrow} (0, 1)\overset{\text{Action }1}{\longrightarrow} (1, 0) \overset{\text{Action }4}{\longrightarrow} (1, 1)$

    Here, a path such as $(0, 0) \overset{\text{Action }2}{\longrightarrow} (1, 0) \overset{\text{Action }5}{\longrightarrow} (0,1) \overset{\text{Action }1}{\longrightarrow} (1,0) \overset{\text{Action }4}{\longrightarrow} (1,1)$ is not allowed, because it visits the point $(1,0)$ multiple times.

    Also, a path such as $(0,0) \overset{\text{Action }1}{\longrightarrow} (1,-1) \overset{\text{Action }4}{\longrightarrow} (1,0) \overset{\text{Action }4}{\longrightarrow} (1,1)$ is not allowed, because it passes through the point $(1,-1)$, which is not contained in $R$.

  • About test case 2

    This represents $n = 0, m = 0$. Not acting even $1$ time is also allowed, so the answer for this case is $1$.

  • About test case 3

    Print the answer modulo $998244353$.

  • About test case 4

    $m$ may not be representable in a 32 bit integer type.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。