ac

p(i) 表示 s[0...i-1] 已经转换完了，s[i...n-1]还未转换的情况下，后面合法的转换种数有多少并返回

p(n) 表示 全部转换完成，后续没有字符转换了，合法转化数为1


eg: "111123"

p(5) = 3 (1,2,3; 12,3; 1,23;)
p(4) = 2 (2,3; 23)
p(5) = 1
p(6) = 1

p(n) = p(n-1) + p(n-2)

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    static int mod = 1_000_000_000 + 7;

    public static void main(String[] args) {
        String s = sc.next();
        int n = s.length();
        char[] arr = s.toCharArray();
        if(arr[0] == '0'){
            System.out.println(0);
            return;
        }
        int[] dp = new int[n+1];
        dp[n] = 1;
        for(int i=n-1;i>=0;i--){
            if(arr[i] == '0'){
                dp[i] = 0;
            }else if(i == n-1){
                dp[i] = dp[i+1] % mod;
            }else {
                if(isChange(arr[i], arr[i+1])){
                    dp[i] = (dp[i+2] + dp[i+1]) % mod;
                }else{
                    dp[i] = dp[i+1] % mod;
                }
            }
        }
        System.out.println(dp[0]);
    }

    static boolean isChange(char c1, char c2){
        if(c1 == '1'){
            return true;
        }
        if(c1 == '2' && c2 >= '0' && c2 <= '6'){
            return true;
        }
        return false;
    }

}
/*
1111

5

01

0
*/