小猪佩奇学数学

题目描述

佩奇和乔治在学数♂学。 给定 $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$ 个正整数,表示答案。

输入输出样例

输入样例 #1

3 3 2

输出样例 #1

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\}$ ### 出题人善意的提醒 请注意常数因子带来的程序效率上的影响。