2.1 Danger! A new disease outbreak!

Score: 30pts

Time Limit: 1.00 sec

There is a breakout of a new disease on the planet, CodeLand. The entire planet is affected due to it. On the first day, \(x\) number of cases were reported. Since this disease spreads very fast a lot of people are infected. The number of new cases on a particular day is \(y\) times the number of new cases on the previous day. You have to calculate the number of new cases on the \(n^{th}\) day. Since the number can be very large, you have to output the result as result%p where p is \(10^{9} + 7\).

Constraints

\(1 \leq t \leq 1000\)

\(1 \leq x \leq 10^{6}\)

\(1 \leq y \leq 10^{6}\)

\(1 \leq n \leq 10^{6}\)

\(1 \leq x \leq 10^{6}\)

\(1 \leq y \leq 10^{6}\)

\(1 \leq n \leq 10^{6}\)

Input Format

The first line contains an integer \(t\), which denotes the number of test cases.

Each of the next \(t\) lines contains the following integers separated by a space:

\(x\): The number of cases reported on the first day.

\(y\): The factor by which the number of new cases on a particular day increases as compared to the previous day.

\(n\): The day on which you have to calculate the number of new cases.

Each of the next \(t\) lines contains the following integers separated by a space:

\(x\): The number of cases reported on the first day.

\(y\): The factor by which the number of new cases on a particular day increases as compared to the previous day.

\(n\): The day on which you have to calculate the number of new cases.

Output Format

For every test case print a single integer on a new line, the number of new cases on the \(n^{th}\) day.

Example 1

Input:

2

2 2 4

3 4 2

Output:

16

12

Explanation:

For the first test case:

The number of cases on the first day was \(2\).

The number of new cases on day \(2\): \(2 \times 2 = 4\).

The number of new cases on day \(3\): \(4 \times 2 = 8\).

The number of new cases on day \(4\): \(8 \times 2 = 16\).

For the second test case:

The number of cases on the first day was \(3\).

The number of new cases on day \(2\): \(4 \times 3 = 12\).

2

2 2 4

3 4 2

Output:

16

12

Explanation:

For the first test case:

The number of cases on the first day was \(2\).

The number of new cases on day \(2\): \(2 \times 2 = 4\).

The number of new cases on day \(3\): \(4 \times 2 = 8\).

The number of new cases on day \(4\): \(8 \times 2 = 16\).

For the second test case:

The number of cases on the first day was \(3\).

The number of new cases on day \(2\): \(4 \times 3 = 12\).