Ex - Alchemy 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

高橋君は「レベル 1 の宝石」を A 種類、それぞれ 10^{10^{100}} 個ずつ持っています。
また、2 以上の整数 n に対し、以下の条件すべてを満たす n 個の宝石を鍋に入れることで代わりに「レベル n の宝石」を 1 個生成できます。

  • どの 2 個の宝石も種類が異なる。
  • どの宝石のレベルも n 未満である。
  • 2 以上の整数 x すべてについて、「レベル x の宝石」は高々 1 個である。

高橋君が手に入れられる可能性がある「レベル N の宝石」が何種類あるかを \text{mod } 998244353 で求めてください。

ただし、レベルが 2 以上の宝石同士は、それぞれを生成するときに用いた宝石の集合が一致しているときに同じ種類であるとみなします。

  • ここで、宝石の集合同士は、ある一方の集合に含まれる宝石であってもう一方の集合に同じ種類の宝石が含まれないようなものが存在するときに区別されます。

また、任意の「レベル 1 の宝石」と任意のレベルが 2 以上の宝石は種類が異なります。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A \leq 10^9
  • N,A は整数

入力

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

N A

出力

答えを出力せよ。

入力例 1

3 3

出力例 1

10

10 種類の「レベル 3 の宝石」を手に入れる方法を以下に示します。

  • 3 種類の「レベル 1 の宝石」を鍋に入れる。
    • 高橋君は「レベル 1 の宝石」を 3 種類持っているため、「レベル 1 の宝石」を 3 種類選ぶ方法は 1 通りです。このため、この方法で手に入れられる「レベル 3 の宝石」は 1 種類です。
  • 1 種類の「レベル 2 の宝石」と 2 種類の「レベル 1 の宝石」を鍋に入れる。
    • 「レベル 2 の宝石」は 2 種類の「レベル 1 の宝石」を鍋に入れることで手に入れられます。
      • 高橋君は「レベル 1 の宝石」を 3 種類持っているため、「レベル 1 の宝石」を 2 種類選ぶ方法は 3 通りです。このため、ここで使われる「レベル 2 の宝石」として考えられるものは 3 種類です。
    • 「レベル 2 の宝石」として考えられるものが 3 種類、2 種類の「レベル 1 の宝石」を選ぶ方法が 3 通りあるため、この方法で手に入れられる「レベル 3 の宝石」は 3 \times 3 = 9 種類です。

入力例 2

1 100

出力例 2

100

入力例 3

200000 1000000000

出力例 3

797585162

Score : 600 points

Problem Statement

Takahashi has A kinds of level-1 gems, and 10^{10^{100}} gems of each of those kinds.
For an integer n greater than or equal to 2, he can put n gems that satisfy all of the following conditions into a cauldron to generate a level-n gem in return.

  • No two gems are of the same kind.
  • Every gem's level is less than n.
  • For every integer x greater than or equal to 2, there is at most one level-x gem.

Find the number of kinds of level-N gems that Takahashi can obtain, modulo 998244353.

Here, two level-2 or higher gems are considered to be of the same kind if and only if they are generated from the same set of gems.

  • Two sets of gems are distinguished if and only if there is a gem in one of those sets such that the other set does not contain a gem of the same kind.

Any level-1 gem and any level-2 or higher gem are of different kinds.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A \leq 10^9
  • N and A are integers.

Input

The input is given from Standard Input in the following format:

N A

Output

Print the answer.

Sample Input 1

3 3

Sample Output 1

10

Here are ten ways to obtain a level-3 gem.

  • Put three kinds of level-1 gems into the cauldron.
    • Takahashi has three kinds of level-1 gems, so there is one way to choose three kinds of level-1 gems. Thus, he can obtain one kind of level-3 gem in this way.
  • Put one kind of level-2 gem and two kinds of level-1 gems into the cauldron.
    • A level-2 gem can be obtained by putting two kinds of level-1 gems into the cauldron.
      • Takahashi has three kinds of level-1 gems, so there are three ways to choose two kinds of level-1 gems. Thus, three kinds of level-2 gems are available here.
    • There are three kinds of level-2 gems, and three ways to choose two kinds of level-1 gems, so he can obtain 3 \times 3 = 9 kinds of level-3 gems in this way.

Sample Input 2

1 100

Sample Output 2

100

Sample Input 3

200000 1000000000

Sample Output 3

797585162