암호 해석
면접 대비시간 제한2초메모리 제한128 MB
숫자 문자열을 A-Z 알파벳으로 디코딩하는 방법의 수를 100만으로 나눈 나머지로 구합니다.
문제
알파벳 대문자 A부터 Z까지를 각각 1부터 26까지의 숫자로 바꾸어 암호를 만들 수 있다. 예를 들어 어떤 숫자 문자열은 여러 가지 알파벳 문자열로 해석될 수 있다.
숫자로만 이루어진 암호가 주어졌을 때, 가능한 해석의 가짓수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 길이가 5000 이하인 암호가 주어진다. 암호는 숫자로만 이루어져 있다.
출력
가능한 해석의 가짓수를 출력한다. 정답이 매우 클 수 있으므로 1000000으로 나눈 나머지를 출력한다.
암호가 잘못되어 해석할 수 없는 경우에는 0을 출력한다.