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