AT_abc281_h [ABC281Ex] Alchemy

题目描述

高桥君拥有 $A$ 种“等级 $1$ 的宝石”，每种宝石各有 $10^{10^{100}}$ 个。 此外，对于任意整数 $n \geq 2$，如果将满足以下所有条件的 $n$ 个宝石放入锅中，可以合成 $1$ 个“等级 $n$ 的宝石”。

• 任意两颗宝石的种类都不同。
• 所有宝石的等级都小于 $n$。
• 对于任意整数 $x \geq 2$，锅中“等级 $x$ 的宝石”最多只有 $1$ 个。

请计算高桥君最多能获得多少种“等级 $N$ 的宝石”，并对 $998244353$ 取模。

此外，等级 $2$ 及以上的宝石，如果它们在合成时所用的宝石集合完全相同，则视为同一种。 这里，两个宝石集合只要存在某种宝石只属于其中一个集合，就认为这两个集合不同。

另外，任意“等级 $1$ 的宝石”与任意等级 $2$ 及以上的宝石都属于不同种类。

输入格式

输入从标准输入中给出，格式如下：

$N$ $A$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 3

输出 #1

10

输入输出样例 #2

输入 #2

1 100

输出 #2

100

输入输出样例 #3

输入 #3

200000 1000000000

输出 #3

797585162

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A \leq 10^9$
• $N, A$ 均为整数

样例解释 1

获得 $10$ 种“等级 $3$ 的宝石”的方法如下：

• 将 $3$ 种“等级 $1$ 的宝石”放入锅中。
  • 高桥君有 $3$ 种“等级 $1$ 的宝石”，选择 $3$ 种的方式有 $1$ 种。因此，这种方法能获得 $1$ 种“等级 $3$ 的宝石”。
• 将 $1$ 种“等级 $2$ 的宝石”和 $2$ 种“等级 $1$ 的宝石”放入锅中。
  • “等级 $2$ 的宝石”可以通过将 $2$ 种“等级 $1$ 的宝石”放入锅中获得。
  • 高桥君有 $3$ 种“等级 $1$ 的宝石”，选择 $2$ 种的方式有 $3$ 种。因此，作为“等级 $2$ 的宝石”有 $3$ 种。
  • 作为“等级 $2$ 的宝石”有 $3$ 种，选择 $2$ 种“等级 $1$ 的宝石”的方式有 $3$ 种，因此这种方法能获得 $3 \times 3 = 9$ 种“等级 $3$ 的宝石”。

由 ChatGPT 4.1 翻译