В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А – 1, Б – 2, …, Я – 33), а пробел – нулем.
Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.
Входные данные:
В первой строке содержится последовательность из не более чем 70 цифр.
Выходные данные:
Выведите одно число - количество возможных сообщений.
Пример:
| Входные данные |
Выходные данные |
| 1025 |
4 |