Problem B
The Digit Cipher

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.

Explanation of sample 1

In the first sample, the six possible strings are CBCABDJ, CWLDJ, CWAXJ, CWABDJ, CBCAXJ, och CBCLDJ.

32312410

6

1121222919

68