Message#862

Message

1 second
64 megabytes
Easy

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.

Input

The first line contains a sequence of digits.

Output

Output a single number.

Examples

Example 1

Loading
Loading