题目背景

还是到了离别的时候呢...... 相聚的时间很短暂，不知是否给了你一次美好的经历呢？

我举办这场比赛，还是想给自己留下一些珍贵的回忆。虽然自己的水平并不高，但这对我还是很有纪念意义。

经过长时间的准备，在这送别之际，应当更隆重一些的 —— 可惜我并没有那样的能力。若不然，也不会只能以这种程度的题目来压轴。

既然如此，就不要让此次分别成为永别...... 我将全力以赴，为了我们下次再会。这是我自私的请求，但请你等着我回来！

我这贫乏的语言，难以表述心中的情感。不如我们就这样，在离别前静静地享受这段时光吧。

题目描述

铃来到了一个奇妙的 Gnilrits 星球，上面生活着一种奇妙的 Gnilrits 人。

这种生物有除了 $k$ 个寿命无限但不能繁殖的个体以外，设其它人的总数在第 $i$ 年为 $a_i$，她得知有规律 $a_i=qa_{i-1}-a_{i-2}$，其中 $a_0=0$，$a_1=1$。

在第 $i$ 年，若 $a_i > k$，则星球上都会依次发生如下事件：

1. 全部 $a_i+k$ 个人被分配到 $a_i$ 个相同的住房内，不能有空房（每个人都是不同的）。

2. 每个房屋都修建一条单向道路，连接另一个房屋（可以是自己）；且对任意房屋，都要有一条连向它的道路。最终形成 $a_i-k$ 个环，包括自环。

需要注意的是，在第一步后因为房屋有不同的人居住，它们之间也就是不同的了。

铃想到了一个问题：设第 $i$ 年分配房屋并修建道路的总方案数为 $b_i$（若 $a_i \leq k$ 则 $b_i=0$），则 $i\in [0,n]$ 的所有 $b_i$ 之和是多少呢？

铃在思考这个问题时，她突然惊醒了过来 —— 原来刚才的只是一场梦。她正想和澪分享梦中的见闻，才想起以往在她身边的澪，如今已经离开了。

没有办法，但铃还是想知道问题的答案，请你帮忙求出来吧。结果可能很大，你只需要告诉她答案对 $998244353$ 取模的结果即可。

输入格式

第一行三个正整数 $n,q,k$。

输出格式

输出一行一个整数表示答案。

4 2 2

765

233 2 99

161697303

7 4 5

322237710

10 3 17

146281933

1919810 114514 2333

426283611

提示

【样例 $1$ 解释】

在 $i \leq 2$ 时 $b_i=0$。

对于 $i=3$ 的情况，$a_i=3$。首先要将 $5$ 个不同的人分配入 $3$ 个相同的房屋，有 $25$ 种方案；再把 $3$ 个变得不同的房屋用环路连接，形成 $1$ 个环，只有 $2$ 种方案，故 $b_3 = 25 \times 2 = 50$。
（更具体的解释见此处）

对于 $i=4$，$a_i=4$，将 $6$ 个人分入 $4$ 个房屋有 $65$ 种方案；在 $4$ 个房屋间修路形成 $2$ 个环有 $11$ 种方案，总方案数为 $65\times 11 = 715$。

故答案为 $50+715=765$。

【数据范围】

本题采用捆绑测试。

Subtask 1（7 pts）：$1\le n\le 1000$，$1\le k \le 3$；
Subtask 2（11 pts）：$1\le n,k \le 100$；
Subtask 3（13 pts）：$1 \le k \le 1000$；
Subtask 4（19 pts）：$1\le k \le 32000$，$q=2$；
Subtask 5（23 pts）：$1\le k \le 16000$，$q \neq 2$；
Subtsak 6（27 pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n \le 10^9$，$1\le k \le 64000$，$2\le q \le 10^9$。

【提示】
此题并不难，但可能需要一定程度的常数优化。