# Appreciation

/*
 * Problem :: 2011 / 암호코
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 100자리 암호가 주어졌을 때 99자리 암호의 해석이 몇가지 나올 수 있는지 안다면,
 *   100자리 암호의 해석이 몇가지 나올 수 있는지 알아내는 데 도움이 되는가?
 *   + Yes => DP 로 풀자
 *     # 역시 경우의 수는 일단 DP 다
 *
 * - 실수 할 수 있는 부분이 꽤 있었다
 *   + A ~ I 까지는 한자리 숫자로 암호화, J ~ Z 까지는 두자리 숫자로 암호화 된다
 *     이러한 성질로 인해 코드의 해석이 다양해질 수 있다
 *   + 아래는 이러한 성질로 추론가능한 코드의 특성이다
 *     # 주어진 코드의 첫번째 숫자가 0 이면 이 코드는 잘못된 것이다
 *     # 주어진 코드의 현재 숫자가 0 이고, 그 전 숫자도 0 이면 이 코드는 잘못된 것이다
 *     # 주어진 코드의 현재 숫자가 0 이고, 그 전 숫자가 3 보다 크면 이 코드는 잘못된 것이다
 *     # 주어진 코등의 현재 숫자를 c, 그 전 숫자를 p 라고 할 때,
 *       10*p+c >= 10 이고 10*p+c <= 26 일 때만 두자리 숫자로 암호화된 알파벳으로 해석가능하다
 *     # dp[i] = i 번째 글자까지 코드를 해석했을 때, 나올 수 있는 해석의 가짓수라면
 *       중간에 dp[i] = 0 이 되는 경우, 이 코드는 잘못된 것이다
 *
 * Point
 * - 처음에 출력 부분 설명의 "암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다" 를
 *   보지 못했었다... 문제좀 주의깊게 읽자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    string code; cin >> code;

    // Control : Output
    /* 코드의 맨 앞자리 숫자가 0 인 경우 */
    if (code[0] == '0') {
        /* 해석 불가능하다 (최소 숫자가 1 이상이어야지 한자리 숫자로 암호화된 알파벳으로 해석가능 */
        cout << 0 << endl;
        exit(0);
    }

    // Process
    int N = code.length();
    int dp[N+1]; /* dp[i] = i 번째 글자까지 코드를 해석했을 때, 나올 수 있는 해석의 가짓수 */
    memset(dp, 0, sizeof(dp));
    dp[0] = dp[1] = 1;
    for (int i=2; i<=N; i++) {
        int c = code[i-1] - '0'; /* i 번째 글자의 숫자값 */
        int p = code[i-2] - '0'; /* i-1 번째 글자의 숫자값 */

        /* i 번째 글자의 숫자값이 0 이 아니면 */
        if (c != 0) {
            /* 한자리 숫자로 암호화된 알파벳으로 해석가능 */
            dp[i] += dp[i-1];
        }
        /* i 번째 글자를 일의 자리, i-1 번째 글자를 십의 자리로 해서 읽었을 때,
         * 즉, 10*p+c 의 값으로 보았을 때 이 값이 10 이상이고 26 이하이면 */
        if (10*p+c >= 10 && 10*p+c <= 26) {
            /* 두자리 숫자로 암호화된 알파벳으로 해석가능 */
            dp[i] += dp[i-2];
        }

        // Control : Output
        /* i 번째 글자까지 코드를 해석했는 데, 해석의 가짓수가 0 이라면 */
        if (dp[i] == 0) {
            /* 이 코드는 잘못된 것임 */
            cout << 0 << endl;
            exit(0);
        }

        /* 1000000 으로 나눈 나머지로 갱신 */
        dp[i] %= 1000000;
    }

    // Control : Output
    cout << dp[N] << endl;
}

// Helper Functions
/* None */