Problem Background

It's time to say goodbye... The time we spent together was brief, but I wonder if it was a pleasant experience for you.

I organized this competition to create some precious memories for myself. Although my skills are not advanced, this holds significant纪念意义 for me.

After long preparations, this farewell should be more grand—unfortunately, I lack the ability to do so. Otherwise, I wouldn't have to end with such modest problems.

Even so, let's not let this farewell become a permanent parting... I will do my best for our next meeting. This is my selfish request, but please wait for my return!

My poor words cannot express the emotions in my heart. Let's just enjoy this time quietly before parting.

Problem Description

Ling has arrived on the wondrous planet of Gnilrits, inhabited by peculiar Gnilrits people.

Apart from $k$ individuals with infinite lifespan but no reproductive ability, the total number of others in the $i$-th year is $a_i$, following the rule $a_i = qa_{i-1} - a_{i-2}$, where $a_0 = 0$ and $a_1 = 1$.

In the $i$-th year, if $a_i > k$, the following events occur sequentially:

1. All $a_i + k$ individuals are distributed into $a_i$ identical houses, with no empty houses (each person is unique).

2. Each house builds a one-way road connecting to another house (which can be itself); and for any house, there must be a road leading to it. Eventually, $a_i - k$ loops are formed, including self-loops.

It should be noted that after the first step, the houses become distinct due to different occupants.

Ling pondered a question: Let the total number of schemes for distributing houses and building roads in the $i$-th year 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, Ling suddenly woke up—it was just a dream. She wanted to share the dream's experiences with Mio, only to realize that Mio, who used to be by her side, has left.

There's no way, but Ling still wants to know the answer. Please help her find it. The result may be very large, so just tell her the answer modulo $998244353$.

Input Format

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

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

4 2 2

Sample Output #1

765

Sample Input #2

233 2 99

Sample Output #2

161697303

Sample Input #3

7 4 5

Sample Output #3

322237710

Sample Input #4

10 3 17

Sample Output #4

146281933

Sample Input #5

1919810 114514 2333

Sample Output #5

426283611

Notes

Sample 1 Explanation

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

For $i = 3$, $a_i = 3$. First, distribute 5 distinct individuals into 3 identical houses, which has 25 ways; then connect the 3 distinct houses into 1 loop, which has 2 ways. Thus, $b_3 = 25 \times 2 = 50$.

For $i = 4$, $a_i = 4$. Distribute 6 individuals into 4 houses in 65 ways; connect the 4 houses into 2 loops in 11 ways. The total number of schemes is $65 \times 11 = 715$.

Hence, the answer is $50 + 715 = 765$.

Data Range

This problem is group-tested.

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 restrictions.

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

Hints

This problem is not difficult but may require a certain level of constant optimization.

见题面 Input 部分

见题面 Output 部分