고대 필사본
시간 제한1초메모리 제한128 MB
단어의 '*'를 채워 모음/자음 연속 길이와 동일 문자 반복 제한을 만족하는 경우의 수를 구하는 문제로, 이전 글자 종류와 반복 길이를 상태로 하는 DP로 풉니다.
문제
발트 지역의 고고학자들이 중요한 프로젝트를 진행하던 중, 그들이 탐사하는 지역에 살았던 문명을 이해하는 데 결정적인 것으로 보이는 고대 필사본을 발견했다. 필사본에는 그림이 가득해서 학자들은 문서의 주제를 대략 파악할 수 있었다.
그러나 글로 쓰인 부분도 있는데, 바로 여기서 문제가 생긴다. 사용된 언어가 매우 오래되었을 뿐 아니라 필사본의 여러 부분이 훼손되어 일부 글자가 사라졌고, 학자들은 무엇이 적혀 있는지 완전히 읽어낼 수 없다.
한 학자가 말하길, 이 단어들이 다음과 같은 규칙이 알려진 어떤 언어를 떠올리게 한다고 했다. 어떤 단어에서도 연속한 모음은 최대 개, 연속한 자음은 최대 개까지만 올 수 있으며, 서로 같은(같은 글자가 반복되는) 모음은 연속해서 최대 개, 같은 자음은 연속해서 최대 개까지만 올 수 있다.
그 학자는 더 정확한 정보를 찾으러 자리를 떠났다. 남은 학자들은 그가 돌아오기를 기다리는 동안, 필사본에 이 가설과 모순되는 점이 없는지 확인하고 앞으로의 작업량을 가늠하기 위해, 주어진 제약만으로 필사본을 해독할 수 있는 서로 다른 방법의 수를 알고 싶어 한다. 그들을 도와주자!
참고: 모음은 aeiou이고, 알파벳의 나머지 21개 글자는 자음이다.
입력
첫째 줄에 네 정수 , , , (, )가 공백 하나로 구분되어 주어진다. 둘째 줄에는 필사본에서 뽑아낸 단어 하나가 주어지며, 최대 15개의 소문자 라틴 알파벳으로 이루어지고, 사라진 글자(있는 경우)는 *로 표시된다.
출력
주어진 제약만으로 올바른 단어를 만들 수 있는 방법의 수를 나타내는 정수 하나를 출력한다. 답은 64비트 부호 있는 정수에 들어간다. 학자의 추측이 틀려서 올바른 단어를 만들 수 없는 경우도 있는데, 이때 답은 당연히 0이다.