Gnilrits Housing and Road Problem

On the mysterious planet Gnilrits, there lives a peculiar species. In addition to exactly \(k\) individuals with infinite lifespans (but who cannot reproduce), the number of the remaining inhabitants in the \(i\)-th year is given by \(a_i\). It is known that the sequence \(\{a_i\}\) satisfies

\(a_0=0, \quad a_1=1, \quad a_i = q\,a_{i-1} - a_{i-2}\) for \(i\ge2\).

In the \(i\)-th year, if \(a_i > k\) then the following two events take place in order:

1. All \(a_i+k\) distinct persons are assigned to \(a_i\u00a0identical houses such that each house gets at least one person. (After assignment, because different individuals reside in each house, the houses become distinguishable.)
2. For each house, one directed road is built connecting it to some house (possibly itself), with the condition that every house receives at least one incoming road. As a result, the functional digraph formed on \(a_i\) houses has exactly \(a_i - k\) cycles (a cycle may be a self‐loop).

Let \(b_i\) be the total number of valid arrangements (assignments and road constructions) in the \(i\)-th year (and define \(b_i=0\) if \(a_i \le k\)). The task is to compute the sum

[ S = \sum_{i=0}^{n} b_i \mod 998244353. ]

You are given three integers \(n\), \(k\) and \(q\). Compute \(S\).

inputFormat

The input consists of a single line containing three integers: \(n\), \(k\) and \(q\). Here \(n\) (\(n\ge0\)) is the maximum year index, \(k\) is the parameter regarding the non‐reproducing individuals, and \(q\) is the coefficient in the recurrence relation.

outputFormat

Output one integer: the value of \(S=\sum_{i=0}^{n}b_i\) modulo \(998244353\).

sample

2 0 2

3