Score : $600$ points

问题陈述

Takahashi 拥有 $A$ 种类型的等级为 $1$ 的宝石，每种各有 $10^{10^{100}}$ 颗。
对于大于等于 $2$ 的整数 $n$，他可以将满足以下所有条件的 $n$ 颗宝石放入炼金釜中，以换取一颗等级为 $n$ 的宝石。

• 没有两颗宝石是同一种类。
• 每颗宝石的等级都小于 $n$。
• 对于每个大于等于 $2$ 的整数 $x$，最多只有一颗等级为 $x$ 的宝石。

求 Takahashi 可以获得的不同种类的等级为 $N$ 的宝石的数量，结果对 $998244353$ 取模。

这里，任意两颗等级为 $2$ 或更高的宝石被认为是同一种类，当且仅当它们是由同一组宝石生成的。

• 两组宝石被区分，当且仅当其中一组存在至少一颗宝石，而另一组不存在同类宝石。

任何等级为 $1$ 的宝石和任何等级为 $2$ 或更高的宝石都被认为是不同种类的。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:49:20