Leetcode 2478. Number of Beautiful Partitions

Count the number of ways to split string s into k contiguous substrings (each length ≥ minLength) such that every substring starts with a prime digit (2,3,5,7) and ends with a non-prime digit, returning the count modulo 1e9+7. This is typically solved with dynamic programming over positions and remaining parts (n ≤ 1000) using precomputed valid cut positions to enforce the start/end and length constraints.