Polynesiaglot (Large)

Ursula likes building constructed languages. Today she started one inspired by real Polynesian languages. So far she has fixed two rules.

• Every word is made of letters. A letter is either a consonant or a vowel.
• A consonant inside a word must be immediately followed by a vowel.

For example, in a language where a is the only vowel and h is the only consonant, a, aa, aha, aaha, and haha are valid words, while h, ahh, ahah, and ahha are not. The rule blocks a consonant after a consonant, and it also blocks a word that ends in a consonant.

Ursula's new language has $C$ different consonants and $V$ different vowels. How many different valid words of length $L$ are there? The answer can get very large, so report 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 100$
• $1 \le C \le 50$
• $1 \le V \le 50$
• $1 \le L \le 500$

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 valid words of length $L$, modulo $10^9+7$.

In the first test case of the first example, suppose a is the only vowel and h is the only consonant. The valid words of length 4 are aaaa, aaha, ahaa, haaa, and haha, so there are five of them.

In the second test case of the same example, suppose the vowels are a and e and h is the only consonant. The valid words of length 2 are aa, ae, ea, ee, ha, and he, so there are six of them.