2.1 Danger! A new disease outbreak!
(RankList for this Question)
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}\)

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.

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\).

Log In to solve the Question