wlskrla7   1년 전

우르술라는 인공 언어의 열렬한 팬이다. 오늘 날 그녀는 실제 폴리네시아 언어에서 영감을 받은 언어를 개발하기 시작했다. 그녀는 언어에 대한 규칙을 설정했다.

- 모든 단어는 문자로 구성되며, 문자는 자음 또는 모음이다.
- 단어의 자음 다음에는 모음이 와야 한다.

예를 들어, a가 유일한 모음이고 h가 유일한 자음인 언어는 a, aa, aha, aaha, haha, haha는 유효한 단어지만, h, ahh, ahaha, ahha는 유효하지 않은 단어다. 자음에 대한 규칙은 자음으로 단어를 끝낼뿐만이 아닌, 자음 다음 자음도 허용하지 않다는 것에 주의하라.
우르술라는 새로운 언어에 사용할 수 있는 자음이 C개고 모음이 V개면, 길이 L에서 유효한 단어가 몇 개나 있을지 결과를 10^9+9로 나눈 나머지를 출력하는 프로그램을 작성하라.

입력
첫 번째 줄에 테스트케이스인 정수 T를 입력받고, 그 다음줄에는 C, V, L을 입력받는다.
범위 제한은 본문 참고.

출력
각 테스트케이스마다, Case #x: y를 출력한다. x는 1부터 시작하는 데스트케이스 번호고, y는 본문에 설명한 길이 L의 유효한 단어의 개수를 10^9+7 (1000000007)로 나눈 나머지를 출력하라.

댓글을 작성하려면 로그인해야 합니다.