SP16686 SOMESUMS - Some Sums

After giving a heartwarming, inspirational speech to the sorority sisters of Delta Gamma at the University of Maryland, Michael Shannon was assaulted on the street by an armed mathematician, who defined a function **f** as follows: The mathematician presented Shannon with an ultimatum: You will write a program to calculate this function modulo 10^9+7 for various values of **m**, **n**, and **k** within the given constraints XOR I will shoot you with this gun! As the mathematician lay recovering in his hospital bed, a Sigma Nu brother who had witnessed the event gingerly approached him and said, "Professor Martinson, I've written a program to solve your problem, but the online judge on your website keeps telling me the answer is wrong. Please tell me what the problem is. Submission ID 571972597." Wearily, Martinson replied, "Have you written a brute force program to verify your program's output for smaller cases?" The Sigma Nu brother replied, "Sorry, what did you say? I wasn't listening. Hey, are you going to eat that?" He then took the professor's chocolate pudding and went home to his lovely girlfriend from Zeta to enjoy the rest of the evening.

In the first line, an integer **T**, the number of test cases. Then **T** lines containing integers **m**, **n**, and **k** separated by spaces.

**T** lines containing the value of **f**(**m**,**n**,**k**) modulo 10^9+7 for each test case.