Decode Count

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.

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

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.