Polynesiaglot

Interview

Time limit5sMemory limit512 MB

Summary

Count length-L strings over C consonants and V vowels with no adjacent consonants and no trailing consonant, modulo 1e9+7.

Level: Easy3 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

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).

Input

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$

Output

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$ .

Hint

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.

Examples2

Example 1
Input
```
2
1 1 4
1 2 2
```
Expected output
```
Case #1: 5
Case #2: 6
```

Example 2

Input

Expected output

Case #1: 1
Case #2: 1
Case #3: 50
Case #4: 50