문제
영문 알파벳으로 구성된 단어 중에서 연달아 세 개의 모음이 등장하지 않는 단어의 경우 좋은 단어라고 이야기한다.
N개의 영문 알파벳 문자로 만들 수 있는 단어들 중에서 좋은 단어의 경우는 총 몇 가지가 가능한지 구하는 프로그램을 작성하라.
영문 알파벳에서 가능한 모음은 'a', 'e', 'i', 'o', 'u' 총 다섯가지다. 그 외의 경우는 모두 자음이며, 문제에서는 알파벳 영문 소문자만 고려한다.
입력
입력은 한 줄로 이루어지며 정수 N(1≤N≤2,000)이 주어진다.
출력
길이 N으로 만들 수 있는 좋은 단어의 수를 출력한다. 답이 매우 클 수 있기 때문에 이를 20091128로 나눈 나머지를 출력한다.
예제 #1
1
26
예제 #2
3
17451