Background

一个简单的数学题

Description

输入n，a，k
定义f(x)=$a^x$$*$$x^k$
输出$T_n$=$\sum_{i=1}^{n}{f(i)}$。
答案对998244353取模

Format

Input

三个正整数n,a,k
(1<=n<=$10^{18}$)
(2<=a<=$10^9$)
(1<=k<=2000)
含义如题

Output

一个正整数$T_n$
含义如题

Sample 1

Input

1 1 1

Output

1

Hint

对于 50%的测试数据
n<=2000

Limitation

1s, 64Mb for each test case.

Source

lyhlyhlyh