A mint stamps each coin with a serial made only of decimal digits. The serial is later decoded into letters using the fixed table 1 -> A, 2 -> B, ..., 26 -> Z. To decode a serial you split it left to right into groups, where each group is either a single digit forming 1-9, or two adjacent digits forming a number 10-26. A group may never have a leading zero (so 0, 06 are not valid groups), which means a 0 can only ever be the second digit of 10 or 20.

Count the number of distinct ways to decode the given serial. Print the count modulo 1000000007. If the serial cannot be decoded at all, the answer is 0.

Input format

A single line: the serial string, consisting only of characters 0-9.

Output format

A single integer: the number of valid decodings, taken modulo 1000000007.

Constraints

• 1 <= length of the serial <= 60
• Every character is a digit 0-9.

226

3

12

2