MOON2  Moon Safari (Hard)
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 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.
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(20170211, 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:
20150721 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. :(


Min_25:
20141024 12:18:37
Finally done. :)


Francky:
20140612 22:18:03
Congratulations to Robert Gerbicz as the first solver. Well done.

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