Product
对于一个长度为 mk 的整数序列
a0,a1,…,amk−1,
定义它的权值为
i=0∏m−1aik.
也就是说,从下标 0 开始,每隔 k 个位置取出一个元素,将这 m 个元素相乘。
对于每个 n0=1,2,…,n,求所有满足
1≤a0≤a1≤⋯≤amk−1≤n0
的整数序列的权值之和,并将结果对 998244353 取模。
输入格式
唯一一行包含三个整数 n,m,k,满足
- 1≤n,k≤250000;
- 1≤m≤1018。
本题只有一组输入,没有测试组数 T。
输出格式
输出 n 行。第 n0 行输出上界为 n0 时所求的权值和对 998244353 取模的结果。
样例
2 2 2
1
10
样例说明
当 n0=1 时,只有序列 (1,1,1,1),权值为 1。
当 n0=2 时,合法序列为
$$(1,1,1,1),\ (1,1,1,2),\ (1,1,2,2),\ (1,2,2,2),\ (2,2,2,2).$$
取下标 0,2 的元素相乘,权值依次为 1,1,2,2,4,总和为 10。