数列求和 - Problem Detail - HFOJ

ID: 3949

Type: RemoteJudge

1000ms

125MiB

Difficulty: 6

Uploaded By:

Tags>

数学

题目描述

给定 $n,a,k$ ，求：

\sum_{i=1}^n i^k a^i

答案对 $10^9 + 7$ 取模。

输入格式

输入一行三个非负整数 $n,a,k$ 。其中 $n, a \ge 1$ 。

输出格式

输出一行一个整数表示答案。

3 4 0

3 10 1

3 9 2

提示

测试点编号	$n=$	$k=$
$1$	$10^6$	$10^3$
$2$	$10^6$	$2\times 10^3$
$3$	$10^{18}$	$0$
$4$		$1$
$5,6$		$2$
$7,8$		$10^3$
$9,10$		$2\times 10^3$

对于 $100\%$ 的数据， $n\le10^{18}$ ， $a\le10^9$ ， $k\le2000$