루미 알고리즘

#1553실버Short Vowels

PO 2022 학교 예선코딩출제 Abdullah Zaghmout영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Solving algorithm problems is difficult, but one thing that is often even more difficult is preparing the test data. Take the problem Arabic for example. Here, the jury has spent many hours of intensive work constructing masterpieces such as hej vad heter du (hello what is your name).

A question that arises is: how do you create text strings that do not contain any short vowels? If you read the problem Arabic, you might remember that a short vowel is a vowel followed by at least two consonants. In the word tall (pine tree), the 'a' is a short vowel, while the word potatis (potato) does not have any short vowels. For simplicity, we count a, e, i, o, u, y as vowels in this problem.

One way to create words that do not contain any short vowels is to start with a word and then remove some letters from it. If we start from potatis, we could get ptais for example. But if the word instead became otats, unfortunately, a short vowel would arise.

Your task is to count the number of ways to remove letters from a given word so that the result does not contain any short vowels. It is allowed to not remove any letters at all (in the second example, this contributes 1 to the answer). However, it is not allowed to remove all the letters. If the same word arises by removing different amounts of letters, they are counted separately (In the first example, there are two ways to get the word tal, we can remove either the first or the second l).

Input

The input consists of a single line with a word S of at most 50 letters. The word consists only of the letters a-z.

Output

Output an integer, the number of ways to remove letters so that a word without short vowels is formed.

Note that the answer will not always fit in a 32-bit integer in the later test cases.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
120All characters in S are the same.
240∣S∣ ≤ 10
340No additional constraints.

예제

예제 1

입력
tall
출력
13

예제 2

입력
potatis
출력
107

출처 표기

출처: Programmeringsolympiaden 2022년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.