Bad Frog 不愿意为编程竞赛投入太多，他只会提供 $n$ 个脑细胞来记忆编程竞赛的知识点。

早晨，Bad Frog 的队友发现 Bad Frog 的脑海中有 $k$ 个知识点，它们分别消耗 $a_1, a_2, \dots, a_k$ 个脑细胞。

由于 Bad Frog 几乎不练习，记忆每个知识点所需的脑细胞数量每天会减少 1，当数量变为 0 时，Bad Frog 就会忘记该知识点。

每天晚上，队友发现 Bad Frog 没有进行任何练习，记忆知识点的脑细胞消耗量减少了，于是他们会督促 Bad Frog 用所有剩余的脑细胞去学习一个新的知识点。

例如，如果 Bad Frog 提供了 22 个脑细胞，且早晨记忆知识点分别消耗 1, 4, 7, 1, 5, 4 个脑细胞，那么晚上脑细胞消耗量将分别变为 0, 3, 6, 0, 4, 3，随后 Bad Frog 会忘记那 2 个消耗为零的知识点。最后，在队友的压力下，Bad Frog 会学习一个新的知识点，并用所有剩余的 6 个脑细胞来记忆它，使得脑细胞消耗量变为 3, 6, 4, 3, 6。

记 $A = \{a_1, a_2, \dots, a_k\}$ 为记忆知识点所需脑细胞数量的多重集。现在距离比赛还有 $t$ 天。为了保持稳定的表现，队友希望比赛当天（$t$ 天后）的多重集 $A$ 与今天相同。请确定满足此条件的数组 $(a_1, a_2, \dots, a_k)$ 的数量，结果对 998244353 取模。

输入格式

输入包含三个整数 $n, k, t$。

数据范围

• $1 \le k \le n \le 10^{12}$
• $1 \le t \le 10^{12}$

输出格式

输出答案对 998244353 取模后的结果。

样例

输入 1

2 1 2

输出 1

1

输入 2

8 4 2

输出 2

6

输入 3

29 7 154

输出 3

0

输入 4

50 10 10

输出 4

77225400

说明

• 对于第一个样例，唯一的数组是 $[2]$ ($[2] \to [1, 1] \to [2]$)。
• 对于第二个样例，这 6 个数组分别是 $[1, 1, 3, 3], [1, 3, 1, 3], [1, 3, 3, 1], [3, 1, 1, 3], [3, 1, 3, 1], [3, 3, 1, 1]$。