즐거운 단어
시간 제한1초메모리 제한128 MB
빈칸을 대문자로 채워 모음 3연속과 자음 3연속을 피하고 'L'이 최소 한 번 등장하는 단어의 개수를 구합니다.
문제
알파벳 대문자로 이루어진 단어에서 일부 글자가 밑줄(_)로 지워져 있다. 밑줄마다 대문자 알파벳 하나를 넣어 새 단어를 만들려고 한다.
모음은 A, E, I, O, U이고, 그 외의 알파벳은 자음이다. 즐거운 단어는 다음 조건을 모두 만족한다.
- 모음이 3개 연속으로 나오지 않는다.
- 자음이 3개 연속으로 나오지 않는다.
- 문자
L을 적어도 하나 포함한다.
주어진 문자열의 모든 밑줄을 알파벳으로 바꿔 즐거운 단어를 만드는 경우의 수를 구하라.
입력
첫째 줄에 지워진 단어가 주어진다. 단어의 길이는 최대 100이고, 알파벳 대문자와 밑줄(_)로만 이루어져 있다. 밑줄의 개수는 최대 10이다.
출력
밑줄을 알파벳으로 바꿔 즐거운 단어를 만들 수 있는 경우의 수를 출력한다.
힌트
정답은 2^63 - 1 이하이다.