{"raw_statement":[{"iden":"background","content":"还是到了离别的时候呢...... 相聚的时间很短暂，不知是否给了你一次美好的经历呢？\n\n我举办这场比赛，还是想给自己留下一些珍贵的回忆。虽然自己的水平并不高，但这对我还是很有纪念意义。\n\n经过长时间的准备，在这送别之际，应当更隆重一些的 —— 可惜我并没有那样的能力。若不然，也不会只能以这种程度的题目来压轴。\n\n既然如此，就不要让此次分别成为永别...... 我将全力以赴，为了我们下次再会。这是我自私的请求，但请你等着我回来！\n\n我这贫乏的语言，难以表述心中的情感。不如我们就这样，在离别前静静地享受这段时光吧。"},{"iden":"statement","content":"铃来到了一个奇妙的 Gnilrits 星球，上面生活着一种奇妙的 Gnilrits 人。\n\n这种生物有除了 $k$ 个寿命无限但不能繁殖的个体以外，设其它人的总数在第 $i$ 年为 $a_i$，她得知有规律 $a_i=qa_{i-1}-a_{i-2}$，其中 $a_0=0$，$a_1=1$。\n\n在第 $i$ 年，若 $a_i > k$，则星球上都会依次发生如下事件：\n\n1. 全部 $a_i+k$ 个人被分配到 $a_i$ 个**相同的**住房内，不能有空房（每个人都是不同的）。\n\n2. 每个房屋都修建一条单向道路，连接另一个房屋（可以是自己）；且对任意房屋，都要有一条连向它的道路。最终形成 $a_i-k$ 个环，包括自环。\n\n需要注意的是，在第一步后因为房屋有不同的人居住，它们之间也就是不同的了。\n\n铃想到了一个问题：设第 $i$ 年分配房屋并修建道路的总方案数为 $b_i$（若 $a_i \\leq k$ 则 $b_i=0$），则 $i\\in [0,n]$ 的所有 $b_i$ 之和是多少呢？\n\n铃在思考这个问题时，她突然惊醒了过来 —— 原来刚才的只是一场梦。她正想和澪分享梦中的见闻，才想起以往在她身边的澪，如今已经离开了。\n\n没有办法，但铃还是想知道问题的答案，请你帮忙求出来吧。结果可能很大，你只需要告诉她答案对 $998244353$ 取模的结果即可。\n\n"},{"iden":"input","content":"第一行三个正整数 $n,q,k$。 "},{"iden":"output","content":"输出一行一个整数表示答案。"},{"iden":"note","content":"【样例 $1$ 解释】  \n\n在 $i \\leq 2$ 时 $b_i=0$。\n\n对于 $i=3$ 的情况，$a_i=3$。首先要将 $5$ 个不同的人分配入 $3$ 个相同的房屋，有 $25$ 种方案；再把 $3$ 个变得不同的房屋用环路连接，形成 $1$ 个环，只有 $2$ 种方案，故 $b_3 = 25 \\times 2 = 50$。  \n（更具体的解释见[此处](https://www.luogu.com.cn/paste/usa2ggb4)）\n\n对于 $i=4$，$a_i=4$，将 $6$ 个人分入 $4$ 个房屋有 $65$ 种方案；在 $4$ 个房屋间修路形成 $2$ 个环有 $11$ 种方案，总方案数为 $65\\times 11 = 715$。\n\n故答案为 $50+715=765$。\n\n【数据范围】\n\n**本题采用捆绑测试。**\n\nSubtask 1（7 pts）：$1\\le n\\le 1000$，$1\\le k \\le 3$；   \nSubtask 2（11 pts）：$1\\le n,k \\le 100$；   \nSubtask 3（13 pts）：$1 \\le k \\le 1000$；  \nSubtask 4（19 pts）：$1\\le k \\le 32000$，$q=2$；  \nSubtask 5（23 pts）：$1\\le k \\le 16000$，$q \\neq 2$；   \nSubtsak 6（27 pts）：无特殊限制。\n\n对于 $100\\%$ 的数据，$1\\le n \\le 10^9$，$1\\le k \\le 64000$，$2\\le q \\le 10^9$。  \n\n\n【提示】  \n此题并不难，但可能需要一定程度的常数优化。\n\n"}],"translated_statement":null,"sample_group":[["4 2 2","765"],["233 2 99","161697303"],["7 4 5","322237710"],["10 3 17","146281933"],["1919810 114514 2333","426283611"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}