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