균형 잡힌 문자열
면접 대비시간 제한1초메모리 제한1024 MB
? 문자를 채워 인접한 글자가 모음과 자음으로 번갈아 나오는 균형 문자열을 만드는 경우의 수를 구합니다.
문제
균형을 중시하는 사람이 균형 조건을 만족하는 문자열의 구조를 연구하고 있다. 이런 문자열을 균형 잡힌 문자열이라고 부른다.
균형 잡힌 문자열은 길이가 짝수인 모든 부분 문자열에서 자음의 개수와 모음의 개수가 같은 문자열이다. 모음은 a, e, i, o, u, y 여섯 글자이고, 나머지 20개 글자는 자음이다. 문자열은 소문자 알파벳으로만 이루어진다.
예를 들어 orooji의 길이가 짝수인 부분 문자열은 {or, ro, oo, oj, ji, oroo, rooj, ooji, orooji}이다. 이 중 oo, oroo, ooji, orooji는 자음과 모음의 개수가 같지 않으므로 orooji는 균형 잡힌 문자열이 아니다. arup의 길이가 짝수인 부분 문자열은 {ar, ru, up, arup}이고 모두 균형이 맞으므로 arup은 균형 잡힌 문자열이다. 균형 잡힌 문자열의 길이는 홀수일 수도 있다. 예를 들어 ali의 길이가 짝수인 부분 문자열은 al과 li뿐이고 둘 다 균형이 맞으므로 ali는 균형 잡힌 문자열이다.
단어에서 몇 글자를 지우고 그 자리를 ?로 바꾼 문자열이 주어진다. 모든 ?를 소문자 알파벳으로 바꾸어 균형 잡힌 문자열을 만드는 방법의 수를 구하라. 어떤 위치 i에서 i번째 글자가 다르면 두 방법은 다른 것으로 본다. 모든 ?를 같은 글자로 바꿀 필요는 없다.
입력
첫 줄에 문자열의 개수 n이 양의 정수로 주어진다. 다음 n개의 줄에는 각각 소문자와 ?로만 이루어진 문자열이 한 줄에 하나씩 주어진다. 각 문자열의 길이는 1 이상 100 이하이다.
출력
각 문자열에 대해 String #d: v 형식으로 출력한다. 여기서 d는 문자열의 번호이고, v는 ?를 소문자 알파벳으로 바꾸는 방법의 수이다. 각 문자열의 출력 뒤에는 빈 줄을 하나 남긴다. 주어진 문자열에 대해 v는 부호 있는 64비트 정수에 들어간다고 보장된다.
힌트
예제 입력의 첫 번째와 마지막 문자열에는 ?가 없다. 첫 번째 문자열은 균형 잡힌 문자열이 아니므로 어떻게 채워도 균형 잡힌 문자열이 될 수 없어 답은 0이다. 마지막 문자열은 균형 잡힌 문자열이므로 만드는 방법이 1가지뿐이어서 답은 1이다.