Polynesiaglot (Small 1)

Ursula likes to build constructed languages. Today she starts one inspired by real Polynesian languages, and so far she has fixed two rules.

• Every word is made of letters. Each letter is a consonant or a vowel.
• Every consonant in a word must be immediately followed by a vowel.

For example, in a language whose only vowel is a and whose only consonant is h, the words a, aa, aha, aaha, and haha are valid, while h, ahh, ahah, and ahha are not. The second rule forbids a consonant followed by another consonant, and it also forbids a word that ends with a consonant.

Ursula's language has $C$ different consonants and $V$ different vowels. Count the valid words of length $L$. The answer can be very large, so print it modulo the prime $10^9+7$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $C$, $V$, and $L$, separated by spaces.

Limits

• $1 \le T \le 15$
• $1 \le C \le 100$
• $1 \le V \le 100$
• $1 \le L \le 15$

For each test case, print one line of the form Case #x: y, where x is the test case number starting from 1 and y is the number of valid words of length $L$, modulo $10^9+7$.

Take $C = 1$, $V = 1$, $L = 4$. Write the vowel as a and the consonant as h. The valid words are aaaa, aaha, ahaa, haaa, and haha, so the answer is 5.

Take $C = 1$, $V = 2$, $L = 2$. Write the vowels as a and e and the consonant as h. The valid words are aa, ae, ea, ee, ha, and he, so the answer is 6.