SP26913 SCELL - SUPER CELL

**Description:** 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

N/A

N/A