#P18300. Product

Product

Product

对于一个长度为 mkmk 的整数序列

a0,a1,…,amk−1,a_0,a_1,\ldots,a_{mk-1},

定义它的权值为

∏i=0m−1aik.\prod_{i=0}^{m-1}a_{ik}.

也就是说,从下标 00 开始,每隔 kk 个位置取出一个元素,将这 mm 个元素相乘。

对于每个 n0=1,2,…,nn_0=1,2,\ldots,n,求所有满足

1≤a0≤a1≤⋯≤amk−1≤n01\le a_0\le a_1\le\cdots\le a_{mk-1}\le n_0

的整数序列的权值之和,并将结果对 998244353998244353 取模。

输入格式

唯一一行包含三个整数 n,m,kn,m,k,满足

  • 1≤n,k≤2500001\le n,k\le250000;
  • 1≤m≤10181\le m\le10^{18}。

本题只有一组输入,没有测试组数 TT。

输出格式

输出 nn 行。第 n0n_0 行输出上界为 n0n_0 时所求的权值和对 998244353998244353 取模的结果。

样例

2 2 2
1
10

样例说明

当 n0=1n_0=1 时,只有序列 (1,1,1,1)(1,1,1,1),权值为 11。

当 n0=2n_0=2 时,合法序列为

$$(1,1,1,1),\ (1,1,1,2),\ (1,1,2,2),\ (1,2,2,2),\ (2,2,2,2).$$

取下标 0,20,2 的元素相乘,权值依次为 1,1,2,2,41,1,2,2,4,总和为 1010。