Decode Count

Interview

Time limit2sMemory limit128 MB

Summary

Count the number of ways to decode a digit string into letters A-Z, modulo 1,000,000.

Level: Medium4 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

A code can be made by replacing uppercase letters A through Z with the numbers 1 through 26. A single string of digits may be decoded into alphabet strings in more than one way.

Given a code made only of digits, write a program that computes how many valid decodings are possible.

Input

The first line contains a code of length at most 5000. The code consists only of digits.

Output

Print the number of possible decodings. Because the answer can be very large, print the remainder after division by 1000000.

If the code is invalid and cannot be decoded, print 0.

Examples2

Example 1
Input
```
25114
```
Expected output
```
6
```
Example 2
Input
```
1111111111
```
Expected output
```
89
```