P5591 Peppa Pig Learns Math

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 $$

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

One positive integer, representing the answer.

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