#include <stdio.h>
#include <string.h>
const int mod=1000000;

int dp[5001];

int bottom_up(char *num,int len) {
    dp[0]=1;
    dp[1]=1;
    for(int i=2; i<=len; i++) {
        int current=num[i-1]-'0';
        if(current>=1 && current<=9) {
            dp[i]=(dp[i-1]+dp[i])%mod;
        }
        

        int pre=num[i-2]-'0';
        int ten_num=pre*10 + current;
        if(ten_num >=10 && ten_num <=26) {
            dp[i]=(dp[i-2]+dp[i])%mod;
        }
    }
    return dp[len];
}

int main() {
    char num[5005];
    scanf("%s",num);
    if(num[0]=='0') {
        printf("0");
        return 0;
    }
    int n=strlen(num);
    printf("%d",bottom_up(num,n));
    return 0;
}