102817: [AtCoder]ABC281 Ex - Alchemy

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

高桥君有 $A$ 种等级 $1$ 的宝石,宝石数量充分多。 他可以利用 $n$ 个满足以下条件的宝石来合成一个等级 $n$ 的宝石($n\geq 2$)。 - 不存在相同种类的宝石。 - 每个宝石的等级严格小于 $n$。 - 对于 $\geq 2$ 的等级,每等级最多有 $1$ 个宝石。 求高桥君能获得等级 $N$ 宝石的种类数,对 $998244353$ 取模。 对于等级 $\geq 2$ 的宝石,种类相同当且仅当合成它们的宝石的种类完全相同。任意等级不同的宝石,种类一定不同。

Output

得分:600分

问题描述

高桥有$A$种等级为1的宝石,每种宝石有$10^{10^{100}}$个。

对于大于等于2的整数$n$,他可以将满足以下所有条件的$n$个宝石放入炼金锅中,以生成等级为$n$的宝石作为回报。

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

求高桥可以得到的等级为$N$的宝石种类数,对$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

这里有十种方法可以得到一个等级为3的宝石。

  • 将三种等级为1的宝石放入炼金锅中。
    • 高桥有三种等级为1的宝石,所以他有1种方法可以选择三种等级为1的宝石。因此,他可以通过这种方式得到一种等级为3的宝石。
  • 将一种等级为2的宝石和两种等级为1的宝石放入炼金锅中。
    • 一个等级为2的宝石可以通过将两种等级为1的宝石放入炼金锅中得到。
      • 高桥有三种等级为1的宝石,所以他有3种方法可以选择两种等级为1的宝石。因此,这里有三种等级为2的宝石可用。
    • 这里有三种等级为2的宝石,以及三种选择两种等级为1的宝石的方法,所以他可以通过这种方式得到$3 \times 3 = 9$种等级为3的宝石。

样例输入2

1 100

样例输出2

100

样例输入3

200000 1000000000

样例输出3

797585162

加入题单

上一题 下一题 算法标签: