$\sum_{i=0}^{n-1} r^i i^d$

정수 $r$, $d$, $n$이 주어질 때, $\sum_{i=0}^{n-1} r^i i^d$을 $998244353$로 나눈 나머지를 계산한다. $0^0 = 1$으로 정의한다.

제약 조건

• $0 \le r < 998244353$
• $0 \le d \le 10000000$
• $0 \le n \le 1000000000000000000$

$r$ $d$ $n$

$\mathit{answer}$