問題文

正の整数 N と整数 C が与えられる．N \times N 行列 A を次のように定める： (i, j) 成分 (1 \le i \le N，1 \le j \le N) は

• i = j のとき 1，
• j が i で割り切れないとき C，
• 上のいずれでもない場合 0．

このとき，\det A を 998244353 で割った余り (0 以上 998244353 未満) を求めよ．

制約

• 1 \le N \le 10^9．
• 0 \le C < 998244353．

部分点

• N \le 10^5 を満たすデータセットに正解した場合は，20 点が与えられる．
• 追加制約のないデータセットに正解した場合は，上記とは別に 80 点が与えられる．

入力例 1

6 3

出力例 1

998244345

A = \begin{bmatrix}1&0&0&0&0&0\\3&1&3&0&3&0\\3&3&1&3&3&0\\3&3&3&1&3&3\\3&3&3&3&1&3\\3&3&3&3&3&1\end{bmatrix} であり，\det A = -8 となる．

入力例 2

2020 11

出力例 2

515894850

入力例 3

1000000000 2020

出力例 3

4909496