#L6818. Nishikata

    ID: 4661 传统题 5000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>生成函数法数论变换倍增法算子演算法

Nishikata

题目描述
给你一个 nnmm 列的方阵,你有 1n1 \sim nnn 个数各 mm 个,要放进方阵中使得数 ii 不在第 ii 行,令方案数为 F(n,m)F(n,m)

[ \bigoplus _{i=1}^{n} \big( F(i,m) \bmod 998244353 \big)。 ]


输入格式
一行两个正整数 n,mn,m


输出格式
一行一个整数表示答案。


样例
输入

3 2

输出

11

解释:
F(2,2)F(2,2) 对应矩阵如 [2211]\begin{bmatrix}2&2\\1&1\end{bmatrix} 等。
F(3,2)F(3,2) 对应矩阵如 $\begin{bmatrix}2&2\\3&3\\1&1\end{bmatrix}, \begin{bmatrix}3&3\\1&1\\2&2\end{bmatrix}, \begin{bmatrix}2&3\\1&3\\1&2\end{bmatrix}, \begin{bmatrix}2&3\\1&3\\2&1\end{bmatrix}, \begin{bmatrix}2&3\\3&1\\1&2\end{bmatrix}, \begin{bmatrix}2&3\\3&1\\2&1\end{bmatrix}, \begin{bmatrix}3&2\\1&3\\1&2\end{bmatrix}, \begin{bmatrix}3&2\\1&3\\2&1\end{bmatrix}, \begin{bmatrix}3&2\\3&1\\1&2\end{bmatrix}, \begin{bmatrix}3&2\\3&1\\1&1\end{bmatrix}$ 等。


数据范围与提示

子任务编号 分值 nmnm 范围 特殊性质
1 10 106\leq 10^6 m=1m=1
2 5000\leq 5000
3 40 105\leq 10^5
4 106\leq 10^6