小 Q 是一位大魔法师，他最近发明了三种作用于数字的魔法。对于一个数字 $x$，这三种魔法的效果分别是：

1. 将 $x$ 增加 1，即 $x$ 变为 $x + 1$。
2. 将 $x$ 减少 1，即 $x$ 变为 $x - 1$，该操作只能在 $x > 1$ 时使用。
3. 选择一个正整数 $k > 1$，将 $x$ 变为 $x \times k$。

现在，小 Q 拥有数字 $x = 1$，并且他可以在不超过 $B$ 次魔法操作内将数字进行变化。

小 Q 想知道，对于每个整数 $n (l \leq n \leq r)$，他有多少种长度不超过 $B$ 的魔法操作序列，使得 $x$ 经过这个操作序列后会变为 $n$，你只需要输出答案对 $998244353$ 取模后的结果。

两个魔法被认为不同当且仅当它们类型不同或者都为第 $3$ 类魔法且选取的 $k$ 不同。

魔法操作序列是由一些（可以为 0）个魔法构成的序列，长度为它所包含的魔法个数。两个魔法序列不同当且仅当它们长度不同或者存在某个对应位置的魔法不同。

输入格式

一行三个正整数 $l, r, B$ ($1 \leq l \leq r \leq 3\times 10^{9}, r - l \leq 30000, B \leq 100$)。

输出格式

一行 $r - l + 1$ 个整数表示答案，第 $i$ 个整数表示得到 $l+i-1$ 的方案数，你只需要输出答案对 $998244353$ 取模后的结果。

样例数据

input

1 10 3

output

4 10 11 13 14 16 15 18 19 16

explanation

在样例中，$1$ 变换到 $1$ 长度不超过 $3$ 的魔法序列有 $4$ 种，它们分别是：

1. 空序列
2. +1, -1
3. ×2, -1
4. ×3, -1, -1

子任务

对于 $100\%$ 的数据，$1 \leq l \leq r \leq 3 \times 10^9, r - l \leq 30000, 1 \leq B \leq 100$

Subtask1($6\%$) : $r, B \le 10$

Subtask2($18\%$) : $r \leq 10^6, B \leq 40$

Subtask3($8\%$) : $r \leq 5 \times 10^6, B \leq 40$

Subtask4($12\%$) : $l = r, B \le 4$

Subtask5($15\%$) : $r \leq 10^{8}$

Subtask6($23\%$) : $r \leq 10^{9}$

Subtask7($18\%$) : 无特殊限制。