#P17697. SPOJ MOON4加强版

SPOJ MOON4加强版

题目描述

给定 n,a,kn,a,k,求:

∑i=1nikai\sum_{i=1}^n i^k a^i

答案对 998244353998244353 取模。

输入格式

输入一行三个正整数 n,a,kn,a,k。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

6 4 3

输出 #1

1030980

输入输出样例 #2

输入 #2

233333333 114514 1919810

输出 #2

3191086

说明/提示

【数据范围】
对于 20%20\% 的数据,1≤n,k≤1051\le n,k \le 10^5。
对于 100%100\% 的数据,1≤k≤1071\le k \le 10^7,1≤n,a≤9982443521\le n,a \le 998244352。