#P18440. Go go Baron Bunny!

Go go Baron Bunny!

Go go Baron Bunny!

原题中的安柏与兔兔伯爵配图

Bad Frog 不愿意为程序设计竞赛投入太多精力,只愿意提供 nn 个脑细胞来记忆竞赛知识点。

今天早上,队友发现他记得 kk 个知识点,它们分别占用 a1,a2,…,aka_1,a_2,\ldots,a_k 个脑细胞。每个仍记得的知识点占用正整数个脑细胞,总占用不超过 nn。

由于 Bad Frog 几乎不练习,白天每个知识点所占用的脑细胞数都会减少 11;减为 00 的知识点就会被遗忘。

每到晚上,队友发现他又没有练习、用于记忆知识点的脑细胞减少了,就会督促他使用全部剩余脑细胞学习一个新的知识点。

例如,若总共提供 2222 个脑细胞,早上各知识点分别占用

1,4,7,1,5,4,1,4,7,1,5,4,

那么晚上先变为

0,3,6,0,4,3.0,3,6,0,4,3.

其中两个占用 00 个脑细胞的知识点被遗忘。最后,在队友的督促下,他用剩余的全部 66 个脑细胞学习一个新知识点,于是各知识点的占用变为

3,6,4,3,6.3,6,4,3,6.

记多重集合 A={a1,a2,…,ak}A=\{a_1,a_2,\ldots,a_k\}。离比赛还有 tt 天。为了让他发挥稳定,队友希望 tt 天后比赛当天的这个多重集合与今天完全相同。

求满足要求的有序数组 (a1,a2,…,ak)(a_1,a_2,\ldots,a_k) 的数量,对 998244353998244353 取模。每天的演化条件比较的是多重集合;统计时,不同顺序的数组分别计数。

输入格式

输入一行三个整数 n,k,tn,k,t,满足

1≤k≤n≤1012,1≤t≤1012.1\le k\le n\le10^{12},\qquad1\le t\le10^{12}.

它们分别是脑细胞总数、今天早上的知识点数量,以及距离比赛的天数。

输入只有一个测试实例,不输入数组 aa。

输出格式

输出一个整数,表示满足要求的数组数量对 998244353998244353 取模的结果。

样例 1

2 1 2
1

样例 2

8 4 2
6

样例 3

29 7 154
0

样例 4

50 10 10
77225400

样例说明

第一个样例中,唯一的数组是 [2][2],其变化为

[2]⟶[1,1]⟶[2].[2]\longrightarrow[1,1]\longrightarrow[2].

第二个样例中,六个数组为

$$[1,1,3,3],\ [1,3,1,3],\ [1,3,3,1],\ [3,1,1,3],\ [3,1,3,1],\ [3,3,1,1].$$