영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Alice has invented a revolutionary cipher that no one will be able to solve! Here's how it works: you take the string to be encrypted and replace each letter with its position in the alphabet. For example, A becomes 1, B becomes 2, C becomes 3, and so on up to Ö which becomes 29 (the last 3 letters in the Swedish alphabet are Å, Ä, and Ö). When she did this, she discovered a major problem with the cipher: it cannot always be decoded uniquely!
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: Example of the ambiguity that can occur with Alice's new cipher.
Write a program that reads an encrypted message and outputs how many different original strings could have given rise to this message. For the given input, there is always at least one possible original string.
Input
The input is a single line of 1 to 15 digits, the encrypted message.
Output
Print an integer: the number of strings that would be encrypted to the message in the input.
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.
| Group | Points | Constraints |
|---|---|---|
| 1 | 40 | For every 3 consecutive digits, at least one of them is not 1 or 2. |
| 2 | 60 | No additional constraints. |
Explanation of sample 1
In the first sample, the six possible strings are CBCABDJ, CWLDJ, CWAXJ, CWABDJ, CBCAXJ, och CBCLDJ.
예제
예제 1
32312410
6
예제 2
1121222919
68