(cache)A - Snack

Contest Duration: 2025-11-03(Mon) 13:00 - 2025-11-03(Mon) 18:00 (local time) (300 minutes) Back to Home

A - Snack Editorial

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : $2$ 点

問題文

あなたは $D$ 日の間、毎日次の $4$ つの行動のうちどれか $1$ つを行います。

$1$ 円払ってガムを買う。
$3$ 円払って飴を買う。
$4$ 円払ってチョコを買う。
$6$ 円払って麩菓子を買う。

あなたは $D$ 日間で合計 $N$ 円を払いました。条件を満たす $D$ 日間の行動は何通りありますか？答えを $998244353$ で割った余りを求めてください。
ただし、 $2$ つの行動は、買ったものが $2$ つの行動の間で異なる日が存在する時に別々に数えます。

制約

$1 \leq D \leq 2 \times 10^5$
$1 \leq N \leq 10^6$
$D, N$ は整数

入力

入力は以下の形式で標準入力から与えられる。

 $D$   $N$

出力

答えを出力せよ。

入力例 1Copy

Copy

2 7

出力例 1Copy

Copy

条件を満たす $2$ 日間の行動は次の $4$ 通りです。

$1$ 日目に $1$ 円払ってガムを買い、 $2$ 日目に $6$ 円払って麩菓子を買う。
$1$ 日目に $3$ 円払って飴を買い、 $2$ 日目に $4$ 円払ってチョコを買う。
$1$ 日目に $4$ 円払ってチョコを買い、 $2$ 日目に $3$ 円払って飴を買う。
$1$ 日目に $6$ 円払って麩菓子を買い、 $2$ 日目に $1$ 円払ってガムを買う。

入力例 2Copy

Copy

200000 1000000

出力例 2Copy

Copy

688682037

Score: $2$ points

Problem Statement

For $D$ days, each day you choose exactly one of the following four actions:

Pay $1$ yen and buy gum.
Pay $3$ yen and buy candy.
Pay $4$ yen and buy chocolate.
Pay $6$ yen and buy wheat gluten snack.

After $D$ days, you have paid a total of $N$ yen.
How many possible sequences of $D$ days satisfy this condition? Output the answer modulo $998244353$ .

Two sequences are considered different if there exists at least one day on which the purchased item is different.

Constraints

$1 \leq D \leq 2 \times 10^5$
$1 \leq N \leq 10^6$
$D, N$ are integers

Input

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

 $D$   $N$

Output

Print the answer.

Sample Input 1Copy

Copy

2 7

Sample Output 1Copy

Copy

There are $4$ valid action sequences for $2$ days:

On day $1$ , pay $1$ yen for gum; on day $2$ , pay $6$ yen for wheat gluten snack.
On day $1$ , pay $3$ yen for candy; on day $2$ , pay $4$ yen for chocolate.
On day $1$ , pay $4$ yen for chocolate; on day $2$ , pay $3$ yen for candy.
On day $1$ , pay $6$ yen for wheat gluten snack; on day $2$ , pay $1$ yen for gum.

Sample Input 2Copy

Copy

200000 1000000

Sample Output 2Copy

Copy

688682037