## MOON2 - Moon Safari (Hard)

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

```0 < T×r < 2 560 000
1 < N < 10^9
1 < a < 10^9
```

Uniform random input in the range.
More precise information : there are 5 input files.
In0 : T<20000 and r <= 128
In1 : T<2000 and r <= 1250
In2 : T<200 and r <= 11000
In3 : T<20 and r <= 100000
In4 : T<2 and r <= 1000000

### Information

This trip can be done with a O(T×r×log(N)) method and some interpreted languages.
Edited(2017-02-11, after compiler changes).
My non optimal Py3 code got AC under 5s for each of the 5 input files.
@speed addicts : My fastest C code got AC in 0.42s. (approx 0.08s per file)
Good luck and have fun ;-)

hide comments pranav_arora: 2015-07-21 04:00:05 Can you please give some hints? I have been trying this problem from days but cannot improve the recurrence I set up for the medium version. :( Please help. Thanks! =(Francky)=> A new method is need ; check your complexity ; good luck. Last edit: 2015-07-21 09:35:10 Min_25: 2014-10-24 12:18:37 Finally done. :) --ans(Francky)--> Well done. Last edit: 2014-10-24 12:43:27 Francky: 2014-06-12 22:18:03 Congratulations to Robert Gerbicz as the first solver. Well done. (gerrob) Thanks! Last edit: 2014-06-14 18:29:02

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