Problem Description

Peppa and George are learning math.

Given $n, p, k$, compute

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

Input Format

Three positive integers, representing $n, p, k$.

Output Format

One positive integer, representing the answer.

3 3 2

54

Hint

For $20\%$ of the testdata, $1 \leq n \leq 10^6$.

For another $40\%$ of the testdata, $k \in \{2^w|0 \leq w \leq 10\}$.

For $100\%$ of the testdata, $1 \leq n, p < 998244353$, and $k \in \{2^{w}|0 \leq w \leq 20\}$.

A Friendly Reminder from the Problem Setter

Please pay attention to the impact of constant factors on your program’s efficiency.

Translated by ChatGPT 5