Given a message consisting only of letters from a -letter alphabet and spaces, each letter has been replaced by its serial number in the alphabet (A — , B — , , YA — ), and each space has been replaced by . Given a sequence of digits, determine the number of original messages from which this sequence could have been obtained.
The first line contains a sequence of digits.
Output a single number.
Example 1