Titania, the largest moon of Uranus. Recently a living cell has been found there and scientists say that this is the beginning of life there. They call it Super cell.

The super cell is very surprising. It lives for T seconds. Every second K-mitosis event occurs in the super cell. In a K-mitosis event, K new super cells born from the mother super cell. These new super cells also lives for exactly T seconds and K-mitosis event occurs every second in all the living super cells.

When the initial super cell has been found the time is 0 second. This super cell lives for next T seconds and at the T'th second it dies. Every super cell dies after T'th second when it is born.

You have to tell how many super cell will be there in Titania at N'th second.

Input

Input starts with an integer TC denoting number of test cases. In next TC lines there will be three integers T, K and N in each line. T denotes the amount of time a super cell lives. K denotes how many new super cells born during mitosis event. N denotes that you have to answer how many super cells live there in Titania at N'th second.

Output

For every test case print a single integer modulo 1000000007 (1e9+7), the number of super cells living at N'th second in Titania.

Constraints

1 ≤ TC ≤ 50

0 ≤ T ≤ 30

1 ≤ K ≤ 100

0 ≤ N ≤ 1000000000

Sample

Input
3
5 2 4
3 1 5
1 2 4

Output
81
24
16

Explanation

In the first sample:

• At 0^th second, 1 cell is there.
• At 1^st second, 2 new cells are born and there are total 3 living cells.
• At 2^nd second, 6 new cells are born and there are total 9 living cells.
• At 3^rd second, 18 new cells are born and there are total 27 living cells.
• At 4^th second, 54 new cells are born and there are total 81 living cells.

In the second sample:

• At 0^th second, 1 cell is there.
• At 1^st second, 1 new cell is born and there are total 2 living cells.
• At 2^nd second, 2 new cells are born and there are total 4 living cells.
• At 3^rd second, 4 new cells are born and the cell which is born at 0^th second dies. So, there are total 7 living cells.

In the third sample:

• At 0^th second, 1 cell is there.
• At 1^st second, 2 new cells are born and the cell which is born at 0^th second dies. So, there are 2 living cells.
• At 2^nd second, 4 new cells are born and the cells which are born at 1^st second die. So, there are 4 living cells.
• At 3^rd second, 8 new cells are born and the cells which are born at 2^nd second die. So, there are 8 living cells.
• At 4^th second, 16 new cells are born and the cells which are born at 3^rd second die. So, there are 16 living cells.