You are given a sequence whose $n^{\text{th}}$ term is

$T_n=n^K\times R^n$
You have to evaluate the series
$S_n=T_1+T_2+T_3+\cdots+T_n$
Find $S_n\:\text{mod}\:(10^9+7)$.

Input Format

The first line of input contains $\mathbf{T}$, the number of test cases.

Each test case consists of three lines, each containing $\mbox{K}$, $n$ and $\mbox{R}$ respectively.

Output Format

For each test case, print the required answer in a line.

Constraints

$1\leq T\leq10$

$1\leq K\leq10^3$

$1\leq n\leq10^{16}$

$2\leq R\leq10^{16}$

$R\ \text{mod}\ (10^9+7)\neq1$

Sample Input

2
2
5
2
3
4
3

Sample Output

1146
5988

Explanation

Case 1: $1146=1^2\times2^1+2^2\times2^2+3^2\times2^3+4^2\times2^4+5^2\times2^5$

Case 2: $5988=1^3\times3^1+2^3\times3^2+3^3\times3^3+4^3\times3^4$

见题面

见题面