SP19997 MOON2 - Moon Safari (Hard)

[Air](http://en.wikipedia.org/wiki/Air_(French_band)) is a music duo from France. You will be told the secret of the critically acclaimed album [Moon Safari](http://en.wikipedia.org/wiki/Moon_Safari): mathematics. The goal of your new task is to compute an ethereal sum. Three trips on the moon are provided, [Moon](http://www.spoj.com/problems/MOON/) (easy), [Moon1](http://www.spoj.com/problems/MOON1/) (medium), [Moon2](http://www.spoj.com/problems/MOON2/) (hard) with different constraints.

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 _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.