MOON2 - Moon Safari (Hard)

# 核心公式  # 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. 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.

2
3 4 5
6 7 8

16068
329990641