Moony is playing a game with unique sequences of numbers. Two sequences are said to be distinct when both the sequences are sorted in ascending order then there is at least one position in the sequences where the numbers present at that position are different. For example (1, 2, 4) and (1, 3, 4) are distinct since position 2 has different numbers in the sequences.

There are K levels in the game.
· For level 1, Moony is given a range of numbers from 1 to N and he is supposed to make unique
sequences of length M. The number of unique sequences he can make is his score.
· For level 2, he has to make sequences of length (M + 1). For level 3, length of sequences should
be (M + 2) and so on. That is, at every level, he has to make sequences of 1 unit greater than before.
· From level 3, the game starts getting harder and the range of numbers to choose from will be 1 unit greater than the previous one. For example, for level 3, range would be (N + 1); for level 4,
range would be (N + 2) and so on.

Output the sum of scores from all levels. As your answer can be very large print the value of the sum of scores modulo 1,000,000,007

Input :
⦁    The first line of input takes T test cases.
⦁    T lines follow. The input accepts 3 integer values N, M, and K.
Output :
For each test case, print the maximum possible score for Moony.
Constraints :
1 <= T <= 100
1 <= N <= 5 x 10^5
1 <= M <= N
1 <= K <= 5 x 10^5