Untitled

const int MOD = 1e9 + 7;
const int MAX_NUM = 1e6;

// Function to check if a number is prime
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

// Function to count prime ways
int countPrimeStrings(string s) {
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // There's one way to split an empty string

    // Iterate over the string
    for (int i = 1; i <= n; ++i) {
        // Try all possible substrings ending at index i
        for (int j = i - 1; j >= 0; --j) {
            if (s[j] == '0') continue; // Skip if leading zeros
            string sub = s.substr(j, i - j);
            if (sub.size() > 6) break; // If substring is too large, break

            int num = stoi(sub); // Convert the substring to an integer
            if (num > MAX_NUM) break; // If number is larger than 10^6, break
            
            // Check if the number is prime
            if (isPrime(num)) {
                dp[i] = (dp[i] + dp[j]) % MOD; // Update dp with modulo
            }
        }
    }

    return dp[n];
}