## MOON - Moon Safari (easy)

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 8Output: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 |