Count the Ways to Split a Digit String into Primes

Count the Ways to Split a Digit String into Primes

You are given a string s consisting solely of decimal digits ('0' through '9').

A split of s is called valid if:

1. The string is partitioned into one or more non-empty contiguous substrings.
2. When converted to an integer, each substring is a prime number.
3. No substring contains a leading zero (for example, "7" is valid, but "07" is not).
4. Each prime integer does not exceed 10^9 (i.e., at most 9 digits).

Return the total number of valid splits of s. Since the answer may be very large, return it modulo 10^9 + 7 (1000000007).

Function Signature

def count_prime_splits(s: str) -> int:
    pass

Examples

Example 1:

Input: s = "113"
Output: 2
Explanation:
The valid splits are:
- ["11", "3"]: 11 and 3 are both primes.
- ["113"]: 113 is prime.
Note that ["1", "13"] and ["1", "1", "3"] are invalid because 1 is not a prime.

Example 2:

Input: s = "3175"
Output: 3
Explanation:
The valid splits are:
- ["3", "17", "5"]
- ["31", "7", "5"]
- ["317", "5"]
All segments in each partition are primes without leading zeros.

Example 3:

Input: s = "023"
Output: 0
Explanation:
Any initial segment would begin with '0', which violates the leading zero constraint.

Constraints

• 1 <= len(s) <= 1000
• s consists only of digits from '0' to '9'.
• Each segment represents an integer in the range [2, 10^9].

Edge Cases to Consider

• Strings with leading zeros (e.g., "0", "03").
• Digits 0 and 1 are not prime.
• Segments that exceed 9 digits or 10^9 should be skipped.
• No valid split exists (should return 0).