MOON1 - Moon Safari (medium)

# 核心公式  # Constraints 系统规定参数 ##### 1 < T ##### 1 < r ##### 1 < N < 10^9 ##### 1 < a < 10^9 ###### (T < 1000 and r < 18 ) or (T < 100 and r < 72) or (T < 10 and r < 256) or (T = 1 and r < 444) # Example 解释说明 ###### 第一组数, 当 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