Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3924
Musical Notes

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Besides his skills of playing Hearthstone, Bob is also insterested in learning piano in order to make himself more charming, of course, to Alice.

Now, Bob had transcribed a musical score for himself to practice. Unfortunately, he only copied the numbered musical notation, which use numbers 1 to 7 representing the musical notes(sung as do, re, mi...) and he forgot to mark the musical notes, which means he did't know the lengths of those notes. Bob remembered that the composition contains m bar and k quarter rest in the end of the composition. Each bar include 4 beats, and the length of quarter equals one beat. There are 5 other musical notes with differnt lengths——whole note, half note, quarter note, eighth note and sixteenth note. In our cases, the length of a whole note is equal to 4 beats, and the length of others are respectively equal to 2, 1, 1/2 and 1/4 beats in order.

Knowing m and k, he can calculate the whole length of those musical notes, l beats, which equals 4*m-k beats. Then he counted out n, the number of notes represented by number 1 to 7, with which he may find out how the composition is formed, namely finding out the length of each note. He thought there might be too many cases to form the composition, so he want you to find out the number of possible ways to form the composition.

Input

The first line of input contains an integer T (T ≤ 20) . T is the number of the cases. In the next T lines, there are three integer m, k, n, representing the number of bars, the number of quarter rests, and the number of musical notes.(1 ≤ m ≤ 10000, 0 ≤ k ≤ 3, mnm+13)

Output

The output contains T lines, and each line contain an answer to a case. The answers might be to large, you should output them modulo 1000000007. If there is no possible ways, output 0.

Sample Input

1
2 0 5

Sample Output

75

Hint

The number of whole, half, quarter, eighth, sixteenth notes can be:

0, 3, 2, 0, 0. In this situation we may find 10 ways to form the composition.

1, 0, 4, 0, 0. In this situation we may find 5 ways.

1, 1, 1, 2, 0. In this situation we may find 60 ways.


Author: YU, Hang
Source: ZOJ Monthly, February 2016
Submit    Status