A - お菓子 解説 /

実行時間制限: 2 sec / メモリ制限: 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

出力

答えを出力せよ。

入力例 1

2 7

出力例 1

4

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

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

入力例 2

200000 1000000

出力例 2

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 1

2 7

Sample Output 1

4

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 2

200000 1000000

Sample Output 2

688682037