폴리네시아글롯

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

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

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

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

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

제한

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

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

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

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