## MOON1 - Moon Safari (medium)

no tags

Air is a music duo from France.
You will be told the secret of the critically acclaimed album Moon Safari: mathematics.
The goal of your new task is to compute an ethereal sum. Three trips on the moon are provided, Moon (easy), Moon1 (medium), Moon2 (hard) with different constraints.

### Input

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

Output T lines, one for each test case, with SN,a,r = sum( a^i i^r, for i in [1..N] ).
Since the answer can get very big, output it modulo 109+7.

### Example

```Input:
2
3 4 5
6 7 8

Output:
16068
329990641
```

### Explanation

The first case is, with N=3, a=4, r=5, about the sum : 4^1 × 1^5 + 4^2 × 2^5 + 4^3 × 3^5 = 4 + 512 + 15552 = 16068.
The second case is, with N=6, a=7, r=8, about the sum : 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 (mod 10^9+7).

### 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)
```

### Information

This trip can be done with a O(T×r^2×log(N)) method and some interpreted languages.
My MOON1-Py3 code got AC in 9.00s for the 4 input files.
(My MOON2 code got AC in 0.00s with C, 0.18s with Py2.7, 0.35 with Py3.2)
Good luck and have fun ;-) [Rampage] Blue.Mary: 2017-02-09 02:17:21 "zhangyide" and some other accounts are robots of some other online judges in China, not real persons. =(Francky)=> Many thanks for that information. Could robots disqualify their submissions after AC ? (If you have contact with them). Some bots do so ; it should be the rule. Last edit: 2017-02-09 07:58:43 Francky: 2017-02-09 00:39:08 zhangyide solution disqualified as exact copy of another one. Please fix your own submission to get points. jas.py: 2015-06-28 23:25:57 i have solved MOON(tutorial) in 1.72 sec and getting TLE here. Guys please give a hint which part to optimise. =(Francky)=> The only hint is given with the complexity. It is not a problem where you have to find some optimisations, just the right method. Good luck. (jas.py)=>.....AC Last edit: 2015-07-11 16:30:02 Vignesh Manoharan: 2014-09-30 18:14:29 wow finally best problem ever :) cant believe im (almost) top score Francky: 2014-06-09 09:01:29 Congratulations @Sam Winchester, with that 0.00s, You'll keep rank#1 forever on this not easy problem. Well done, the hard part is waiting for you ;-) Linghui Liu: 2014-06-09 08:21:43 @Sam Winchester, congrats to you. Sam Winchester: 2014-06-09 04:10:50 this was the first problem of your francky which i was able to solve ... loved this problem .... accepted with 0.00 :) Last edit: 2014-06-09 04:34:50