cho.sh

폴리네시아글롯

C개 자음과 V개 모음으로 자음 뒤에 항상 모음이 오고 마지막 글자가 모음인 길이 L 문자열 개수를 1000000007로 나눈 나머지로 구합니다.

쉬움3동적 계획법조합론면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

우르술라는 인공어를 만든다. 이번에 만드는 언어는 폴리네시아 계열 언어에서 모양을 따왔고, 정해 둔 규칙은 두 가지뿐이다.

  • 모든 단어는 글자를 늘어놓은 것이고, 각 글자는 자음이거나 모음이다.
  • 단어 안의 모든 자음 바로 뒤에는 모음이 와야 한다.

예를 들어 모음이 a 하나, 자음이 h 하나뿐인 언어에서 a, aa, aha, aaha, haha는 단어이고 h, ahh, ahah, ahha는 단어가 아니다. 두 번째 규칙은 자음으로 끝나는 단어도 막는다.

우르술라의 언어에는 서로 다른 자음이 CC개, 서로 다른 모음이 VV개 있다. 길이가 LL인 단어가 몇 개인지 세어라. 답이 매우 커질 수 있으므로 소수 109+710^9+7(1000000007)로 나눈 나머지를 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다. 이어지는 TT개의 줄에 각각 세 정수 CC, VV, LL이 주어진다.

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤C≤501 \le C \le 50
  • 1≤V≤501 \le V \le 50
  • 1≤L≤151 \le L \le 15

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 우르술라의 언어에서 길이가 LL인 단어의 개수를 109+710^9+7로 나눈 나머지이다.

힌트

첫 번째 예제 테스트 케이스에서 모음이 a 하나, 자음이 h 하나라고 하자. 길이가 4인 단어는 aaaa, aaha, ahaa, haaa, haha이다.

두 번째 예제 테스트 케이스에서 모음이 a와 e, 자음이 h 하나라고 하자. 길이가 2인 단어는 aa, ae, ea, ee, ha, he이다.