← 返回题目列表

AtCoder · xmascon20_d

D. 行列式

中文机器翻译题面 查看原题

配点 : 100 点

当兔子成功找到了一个巨大矩阵的行列式时,他很高兴,把它变成了一个问题。 定义

問題文

正整数 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 点。

入力

输入是按以下格式从标准输入给出的。

N C

出力

\det A 输出为 998244353 时的余数 ( (小于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