MOON1 - Moon Safari (medium)

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.

AirSum

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 ;-)


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

hide comments
2017-02-09 02:17:21 [Rampage] Blue.Mary
"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
2017-02-09 00:39:08 Francky
zhangyide solution disqualified as exact copy of another one. Please fix your own submission to get points.
2015-06-28 23:25:57 jas.py
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.


Last edit: 2022-11-01 01:20:46
2014-09-30 18:14:29 Vignesh Manoharan
wow finally
best problem ever :)
cant believe im (almost) top score
2014-06-09 09:01:29 Francky
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 ;-)
2014-06-09 08:21:43 Linghui Liu
@Sam Winchester, congrats to you.
2014-06-09 04:10:50 Sam Winchester
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.