"A fight? Count me in!"

"Everyone, get in here!"

Xiao Y is an OIer who loves playing games. One day, she is playing a game where she has to defeat a boss.

Although this boss has $10^{100}$ health points, it only brings one minion—a "Grim Patron" with $m$ health points.

This "Grim Patron" has a special ability: whenever it takes damage but does not die (death means health $\leq 0$), and the number of the boss's minions is less than the limit $k$, it summons a new "Grim Patron" with $m$ health points.

Now, Xiao Y can perform $n$ attacks. Each time she attacks, she chooses one target uniformly at random from the boss and all of the boss's minions, and deals $1$ point of damage. She wants to know the expected total damage dealt to the boss after $n$ attacks. To avoid precision errors, your answer should be modulo $998244353$.

Input

The input is read from standard input.

The first line contains three positive integers $T, m, k$, where $T$ is the number of queries, and $m$ and $k$ are as described in the problem statement.

The next $T$ lines each contain a positive integer $n$, representing the query for the expected damage dealt to the boss after $n$ attacks.

Output

The output is written to standard output.

Output $T$ lines, each containing a non-negative integer representing the answer to the query modulo $998244353$.

It can be proven that the required expectation is always a rational number. Let it be $p / q$ (where $\mathrm{gcd}(p,q) = 1$). You should output an integer $x$ such that $p \equiv qx \pmod{998244353}$.

Examples

Input 1

3 2 6
1
2
3

Output 1

499122177
415935148
471393168

Note

For the first query, the first attack has a $1/2$ probability of dealing damage to the boss and a $1/2$ probability of dealing damage to the minion, so the answer is $1/2$. $1 \equiv 2 * 499122177 \pmod{998244353}$.

For the second query, if the first attack dealt damage to the boss, then there is a $1/2$ probability the second attack also deals damage to the boss, and a $1/2$ probability it deals damage to the minion; if the first attack dealt damage to the minion, a new minion ("Grim Patron") is summoned, so there is a $1/3$ probability the second attack deals damage to the boss, and a $2/3$ probability it deals damage to the minion. Thus, the answer is $1/2 * 1/2 * 2 + 1/2 * 1/2 * 1 + 1/2 * 1/3 * 1 + 1/2 * 2/3 * 0 = 11/12$. $11 \equiv 12 * 415935148 \pmod{998244353}$.

Input 2

(See the provided files)

Note

The data range for this set of examples (excluding the number of queries $T$) is the same as in test cases 7 and 8.

Note

The order of the problems may not correspond to their difficulty.

Constraints

For all test cases, $1 \leq T \leq 1000, 1 \leq n \leq {10}^{18}, 1 \leq m \leq 3, 1 \leq k \leq 8$.

The scores and data ranges for each test case are as follows: