폴리네시아글롯

Ursula는 인공 언어를 만드는 것을 매우 좋아한다. 오늘 그녀는 실제 폴리네시아 언어에서 영감을 받은 언어를 만들기 시작한다. 그녀가 정한 규칙은 다음뿐이다.

• 모든 단어는 문자로 이루어진다. 문자는 자음 또는 모음이다.

• 단어의 모든 자음 바로 뒤에는 반드시 모음이 와야 한다.

예를 들어, 아가 유일한 모음이고 ㅎ이 유일한 자음인 언어에서는 아, 아아, 아하, 아아하, 하하는 올바른 단어이지만, 하, 아흐흐, 아하흐, 아흐하는 올바르지 않다. 자음에 관한 규칙은 자음 뒤에 다른 자음이 오는 것뿐만 아니라 단어가 자음으로 끝나는 것도 허용하지 않는다는 점에 유의한다.

Ursula의 새로운 언어에서 사용할 수 있는 서로 다른 자음이 C개이고 서로 다른 모음이 V개라면, 이 언어에는 길이가 L인 서로 다른 올바른 단어가 몇 개 있는가? 출력값이 매우 큰 수일 수 있으므로, 결과를 소수 $10^{9}$+7 (1000000007)로 나눈 나머지만 출력한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 1 (테스트 세트 1 - 공개)

T = 15. C = 1. V = 1. 1 ≤ L ≤ 15.

작은 데이터 세트 2 (테스트 세트 2 - 공개)

1 ≤ T ≤ 100. 1 ≤ C ≤ 50. 1 ≤ V ≤ 50. 1 ≤ L ≤ 15.

큰 데이터 세트 (테스트 세트 3 - 비공개)

1 ≤ T ≤ 100. 1 ≤ C ≤ 50. 1 ≤ V ≤ 50. 1 ≤ L ≤ 500.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 세 정수 C, V, L이 있는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작한다), y은 언어에서 길이가 L인 서로 다른 올바른 단어의 수를 소수 $10^{9}$+7 (1000000007)로 나눈 나머지이다.

케이스 #1에서 유일한 모음이 아이고 유일한 자음이 ㅎ이라고 하자. 그러면 길이가 4인 가능한 올바른 단어는 다음과 같다: aaaa, aaha, ahaa, haaa, haha.

케이스 #2에서는(작은 데이터 세트 1에는 나오지 않는다) 두 모음이 아와 에이고 유일한 자음이 ㅎ이라고 하자. 그러면 길이가 2인 가능한 올바른 단어는 다음과 같다: aa, ae, ea, ee, ha, he.