인공 폴리네시아어 (라지)

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

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

예를 들어 모음이 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 100$
• $1 \le C \le 50$
• $1 \le V \le 50$
• $1 \le L \le 500$

각 테스트 케이스마다 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의 여섯 개다.