P5907 Enhanced Sequence Sum / SPOJ MOON4

[Original link](https://www.luogu.com.cn/problem/P4948)

Given $n$, $a$, and $k$, compute: $$\sum_{i=1}^n i^k a^i$$ Output the answer modulo $998244353$.

Input one line with three positive integers $n$, $a$, and $k$.

Output one line with one integer representing the answer.

Constraints For $20\%$ of the testdata, $1\le n,k \le 10^5$. For $100\%$ of the testdata, $1\le k \le 10^7$, $1\le n,a \le 998244352$. Translated by ChatGPT 5