Problem Description

Given \( n, a, k \), compute:

\[ \sum_{i=1}^n i^k a^i \]
The answer should be modulo \( 998244353 \).

Input Format

A single line containing three positive integers \( n, a, k \).

Output Format

A single line containing an integer representing the answer.

Sample Input and Output

Sample Input #1

6 4 3

Sample Output #1

1030980

Sample Input #2

233333333 114514 1919810

Sample Output #2

3191086

Notes

Data Range

For 20% of the data, \( 1 \le n, k \le 10^5 \).
For 100% of the data, \( 1 \le k \le 10^7 \), \( 1 \le n, a \le 998244352 \).

见题面 Input 部分

见题面 Output 部分