## MOON - Moon Safari (easy)

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×N < 10^6
1 < a < 10^9
1 < r < 10^9
```

### Information

This trip can be obviously done with a O(T×N×log(r)) method and some interpreted languages.
Good luck and have fun ;-)

 Added by: Francky Date: 2014-06-07 Time limit: 10s-20s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64 Resource: Own problem