Polynesiaglot

Ursula builds constructed languages. Her newest one takes its shape from the Polynesian languages, and she has fixed only two rules.

• Every word is a sequence of letters, and each letter is either a consonant or a vowel.
• Every consonant in a word is immediately followed by a vowel.

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

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

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

Limits

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

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

In the first sample test case, let the only vowel be a and the only consonant be h. The words of length 4 are aaaa, aaha, ahaa, haaa, and haha.

In the second sample test case, let the vowels be a and e and the only consonant be h. The words of length 2 are aa, ae, ea, ee, ha, and he.