配点 : $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$

出力

答えを出力せよ。

3 3

10

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

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

1 100

100

200000 1000000000

797585162