P8561 送别（Farewell）

还是到了离别的时候呢...... 相聚的时间很短暂，不知是否给了你一次美好的经历呢？ 我举办这场比赛，还是想给自己留下一些珍贵的回忆。虽然自己的水平并不高，但这对我还是很有纪念意义。 经过长时间的准备，在这送别之际，应当更隆重一些的 —— 可惜我并没有那样的能力。若不然，也不会只能以这种程度的题目来压轴。 既然如此，就不要让此次分别成为永别...... 我将全力以赴，为了我们下次再会。这是我自私的请求，但请你等着我回来！ 我这贫乏的语言，难以表述心中的情感。不如我们就这样，在离别前静静地享受这段时光吧。

铃来到了一个奇妙的 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$ 取模的结果即可。

无

无

【样例 $1$ 解释】 在 $i \leq 2$ 时 $b_i=0$。 对于 $i=3$ 的情况，$a_i=3$。首先要将 $5$ 个不同的人分配入 $3$ 个相同的房屋，有 $25$ 种方案；再把 $3$ 个变得不同的房屋用环路连接，形成 $1$ 个环，只有 $2$ 种方案，故 $b_3 = 25 \times 2 = 50$。 （更具体的解释见[此处](https://www.luogu.com.cn/paste/usa2ggb4)） 对于 $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$。 【提示】 此题并不难，但可能需要一定程度的常数优化。