Background

It is time to say goodbye again... The time we spent together was short. I wonder if it brought you a good experience.

I held this contest because I wanted to leave myself some precious memories. Although my own skill is not high, it still means a lot to me.

After a long time of preparation, since this is a farewell, it should have been more grand—yet I do not have that ability. Otherwise, I would not have been able to make only a problem of this level as the finale.

Since so, do not let this parting become a forever goodbye... I will do my best, for our next meeting. This is my selfish request, but please wait for me to come back.

My poor words cannot express the feelings in my heart. Then let us just do this—quietly enjoy this time before we part.

Problem Description

Rin arrived at a wonderful planet called Gnilrits, where a wonderful kind of Gnilrits people lives.

In this species, except for $k$ individuals who have infinite lifespan but cannot reproduce, let the total number of other people in year $i$ be $a_i$. She learned that they follow the rule $a_i=qa_{i-1}-a_{i-2}$, where $a_0=0$ and $a_1=1$.

In year $i$, if $a_i > k$, then the following events will happen in order on the planet:

1. All $a_i+k$ people are assigned into $a_i$ identical houses, with no empty house (each person is distinct).

2. From each house, build one directed road to another house (possibly itself). Also, for every house, there must be a road pointing to it. In the end, there will be $a_i-k$ directed cycles, including self-loops.

Note that after step 1, since different people live in the houses, the houses become different from each other.

Rin thought of a question: let the total number of ways to assign houses and build roads in year $i$ be $b_i$ (if $a_i \leq k$ then $b_i=0$). What is the sum of all $b_i$ for $i\in [0,n]$?

While thinking about this, she suddenly woke up—it turned out it was only a dream. She wanted to share what she saw in the dream with Mio, but then she remembered that Mio, who used to be by her side, has now left.

There is no way, but Rin still wants to know the answer. Please help compute it. The result may be very large; you only need to output it modulo $998244353$.

Input Format

The first line contains three positive integers $n,q,k$.

Output Format

Output one integer on one line, representing the answer.

4 2 2

765

233 2 99

161697303

7 4 5

322237710

10 3 17

146281933

1919810 114514 2333

426283611

Hint

[Sample 1 Explanation]

When $i \leq 2$, $b_i=0$.

For $i=3$, $a_i=3$. First, assign $5$ distinct people into $3$ identical houses, which has $25$ ways. Then connect the $3$ now-distinct houses with directed roads to form $1$ cycle, which has only $2$ ways, so $b_3 = 25 \times 2 = 50$.
(For a more detailed explanation, see here.)

For $i=4$, $a_i=4$. Assign $6$ people into $4$ houses, which has $65$ ways. Building roads among the $4$ houses to form $2$ cycles has $11$ ways, so the total number of ways is $65\times 11 = 715$.

Therefore the answer is $50+715=765$.

[Constraints]

This problem uses bundled testdata.

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$.
Subtask 6 (27 pts): no special constraints.

For $100\%$ of the data, $1\le n \le 10^9$, $1\le k \le 64000$, $2\le q \le 10^9$.

[Hint]
This problem is not hard, but it may require some constant-factor optimizations.

Translated by ChatGPT 5