Peppa and George's Math Puzzle

Peppa and George are studying mathematics. They are given three integers n, p, and k. Your task is to compute the following sum modulo 998244353:

$$ S = \sum_{i=0}^n \binom{n}{i} \times p^{i} \times \left\lfloor \frac{i}{k} \right\rfloor \bmod 998244353 $$

Here, \(\binom{n}{i}\) represents the binomial coefficient and \(\left\lfloor \frac{i}{k} \right\rfloor\) denotes the floor function.

Calculate and output the value of \(S\).

inputFormat

The input consists of a single line containing three space-separated integers: n p k.

outputFormat

Output a single integer, the value of the computed sum modulo 998244353.

sample

3 2 2

20