폴리네시아어 만들기 (Small 1)

우르술라는 인공어를 만드는 일을 좋아한다. 오늘은 실제 폴리네시아 언어에서 영감을 받은 언어를 만들기 시작했고, 지금까지 정한 규칙은 두 가지다.

• 모든 단어는 글자로 이루어진다. 글자는 자음이거나 모음이다.
• 단어 안의 자음 뒤에는 반드시 모음이 바로 와야 한다.

예를 들어 모음이 a 하나, 자음이 h 하나뿐인 언어에서 a, aa, aha, aaha, haha는 올바른 단어지만 h, ahh, ahah, ahha는 올바르지 않다. 두 번째 규칙 때문에 자음 뒤에 자음이 오는 단어뿐 아니라 자음으로 끝나는 단어도 올바르지 않다.

우르술라의 언어에 서로 다른 자음이 $C$개, 서로 다른 모음이 $V$개 있다. 길이가 $L$인 올바른 단어가 몇 개인지 구하여라. 답이 매우 클 수 있으므로 소수 $10^9+7$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각각 세 정수 $C$, $V$, $L$이 공백으로 구분되어 주어진다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 길이가 $L$인 올바른 단어의 개수를 $10^9+7$로 나눈 나머지다.

$C = 1$, $V = 1$, $L = 4$인 경우를 보자. 모음을 a, 자음을 h라고 하면 올바른 단어는 aaaa, aaha, ahaa, haaa, haha의 5개다.

$C = 1$, $V = 2$, $L = 2$인 경우도 보자. 모음을 a와 e, 자음을 h라고 하면 올바른 단어는 aa, ae, ea, ee, ha, he의 6개다.