In the message, consisting of only Russian letters and spaces, each letter was replaced by its serial number in the Russian alphabet (A – 1, B – 2, …, I – 33), and the space – zero.
Given a given sequence of digits, it is required to find the number of original messages from which it could be obtained.
Input:
The first line contains a sequence of no more than 70 digits.
Output:
Print one number - the number of possible messages.
Example: