시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 18 15 14 82.353%

## 문제

Ursula is a big fan of constructing artificial languages. Today, she is starting to work on a language inspired by real Polynesian languages. The only rules she has established are:

• All words consist of letters. Letters are either consonants or vowels.
• Any consonant in a word must be immediately followed by a vowel.

For example, in a language in which a is the only vowel and h is the only consonant, aaaahaaaha, and haha are valid words, whereas hahhahah, and ahha are not. Note that the rule about consonants disallows ending a word in a consonant as well as following a consonant with another consonant.

If Ursula's new language has C different consonants and V different vowels available to use, then how many different valid words of length L are there in her language? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+7 (1000000007).

## 입력

The first line of the input gives the number of test cases, TT test cases follow. Each consists of one line with three integers CV, and L.

Limits

• T = 15.
• C = 1.
• V = 1.
• 1 ≤ L ≤ 15.

## 출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of different valid words of length L in the language, modulo the prime 109+7 (1000000007).

## 예제 입력 1

2
1 1 4
1 2 2


## 예제 출력 1

Case #1: 5
Case #2: 6


## 힌트

In Case #1, suppose that the only vowel is a and the only consonant is h. Then the possible valid words of length 4 are: aaaaaahaahaahaaahaha.

In Case #2 (which would not appear in the Small dataset 1), suppose that the two vowels are a and e and the only consonant is h. Then the possible valid words of length 2 are: aaaeeaeehahe.

## 채점

• 예제는 채점하지 않는다.