SCELL - SUPER CELL

no tags 

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 0th second, 1 cell is there.
  • At 1st second, 2 new cells are born and there are total 3 living cells.
  • At 2nd second, 6 new cells are born and there are total 9 living cells.
  • At 3rd second, 18 new cells are born and there are total 27 living cells.
  • At 4th second, 54 new cells are born and there are total 81 living cells.

In the second sample:

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

In the third sample:

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

hide comments
clone123: 2020-02-16 18:31:39

answer for second test case should be 20


Added by:Shahed Shahriar
Date:2016-04-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:National High School Programming Contest 2016, Bangladesh Final Round