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

AC一覧

Problem Statement問題文

Given integers $r$, $d$ and $n$, calculate $\sum_{i=0}^{n-1} r^i i^d$ modulo $998{,}244{,}353$. We define $0^0 = 1$.

Constraints制約

• $0 \le r < 998{,}244{,}353$
• $0 \le d \le 10^{7}$
• $0 \le n \le 10^{18}$

Input入力

$r$ $d$ $n$


Output出力

$\mathit{answer}$


Sampleサンプル

# 1

2 5 8

2767418


Timelimit: 5 secs

Before submitting, please confirm terms and conditions