题目描述

佩奇和乔治在学数♂学。

给定 $n,p,k$,询问

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

输入格式

$3$ 个正整数,分别表示 $n,p,k$。

输出格式

$1$ 个正整数,表示答案。

3 3 2

54

提示

对于 $20\%$ 的数据，$1 \leq n \leq 10^6$

对于另外 $40\%$ 的数据，$k \in \{2^w|0 \leq w \leq 10\}$

对于 $100\%$ 的数据，$1 \leq n,p <998244353,k \in \{2^{w}|0 \leq w \leq 20\}$

出题人善意的提醒

请注意常数因子带来的程序效率上的影响。