$\sum_{i=0}^{\infty} r^i i^d$

AC一覧

Problem Statement / 問題文

Let $\widetilde{r}$ be a rational number such that $-1 < \widetilde{r} < 1$ and $\widetilde{r} \equiv r \pmod{998{,}244{,}353}$. Given integers $r$ and $d$, calculate $\sum_{i=0}^{\infty} \widetilde{r}^i i^d$ modulo $998{,}244{,}353$. The answer is well-defined under the constraints of this problem. We define $0^0 = 1$.

Constraints / 制約

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

Input / 入力

$r$ $d$


Output / 出力

$\mathit{answer}$


Sample / サンプル

# 1

499122177 5

1082


Timelimit: 5 secs