MOON2 - Moon Safari (Hard)
题意翻译
# 核心公式
![](https://www.spoj.com/content/francky:AirSum)
# Constraints 系统规定参数
0 < T×r < 2 560 000
1 < N < 10^9
1 < a < 10^9
所有数据均匀的分布在值域内
更精确的信息 : 总共有五个测试点
输入 0 : T<20000 and r <= 128
输入 1 : T<2000 and r <= 1250
输入 2 : T<200 and r <= 11000
输入 3 : T<20 and r <= 100000
输入 4 : T<2 and r <= 1000000
# Example 样例
Input:输入
2
3 4 5
6 7 8
Output:输出
16068
329990641
# Explanation 解释说明
###### 第一组数, 当 N=3, a=4, r=5, 求和 : 4^1 × 1^5 + 4^2 × 2^5 + 4^3 × 3^5 = 4 + 512 + 15552 = 16068.
###### 第二组数, 当 N=6, a=7, r=8, 求和: 7^1 × 1^8 + 7^2 × 2^8 + 7^3 × 3^8 + 7^4 × 4^8 + 7^5 × 5^8 + 7^6 × 6^8 + 7^7 × 7^8 = 204329992069 ≡ 329990641 (模 10^9+7).
题目描述
[Air](http://en.wikipedia.org/wiki/Air_(French_band)) is a music duo from France. You will be told the secret of the critically acclaimed album [Moon Safari](http://en.wikipedia.org/wiki/Moon_Safari): mathematics. The goal of your new task is to compute an ethereal sum.
![AirSum](../../content/francky:AirSum "AirSum")Three trips on the moon are provided, [Moon](http://www.spoj.com/problems/MOON/) (easy), [Moon1](http://www.spoj.com/problems/MOON1/) (medium), [Moon2](http://www.spoj.com/problems/MOON2/) (hard) with different constraints.
输入输出格式
输入格式
The first line contains an integer _T_, the number of test cases. On the next _T_ lines, you will be given three integers _N_, _a_ and _r_.
输出格式
Output _T_ lines, one for each test case, with _S $ _{N,a,r} $_ = sum( _a^i i^r_, for _i_ in \[_1..N_\] ). Since the answer can get very big, output it modulo 10 $ ^{9} $ +7.
输入输出样例
输入样例 #1
2
3 4 5
6 7 8
输出样例 #1
16068
329990641