D - Determinant 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MB

配点 : 100

巨大な行列の行列式を求めることに成功したうさぎは,うれしくなって問題にしてしまいました.

問題文

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

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

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

制約

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

部分点

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

入力

入力は以下の形式で標準入力から与えられる.

N C

出力

\det A998244353 で割った余り (0 以上 998244353 未満) を出力せよ.


入力例 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