시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 23 17 15 71.429%

문제

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

  • 1 ≤ T ≤ 100.
  • 1 ≤ C ≤ 50.
  • 1 ≤ V ≤ 50.
  • 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.

채점

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