암호 해석

알파벳 대문자 A부터 Z까지를 각각 1부터 26까지의 숫자로 바꾸어 암호를 만들 수 있다. 예를 들어 어떤 숫자 문자열은 여러 가지 알파벳 문자열로 해석될 수 있다.

숫자로만 이루어진 암호가 주어졌을 때, 가능한 해석의 가짓수를 구하는 프로그램을 작성하시오.

첫째 줄에 길이가 5000 이하인 암호가 주어진다. 암호는 숫자로만 이루어져 있다.

가능한 해석의 가짓수를 출력한다. 정답이 매우 클 수 있으므로 1000000으로 나눈 나머지를 출력한다.

암호가 잘못되어 해석할 수 없는 경우에는 0을 출력한다.