Number of Beautiful Partitions
You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.
A partition of s is called beautiful if:
sis partitioned intoknon-intersecting substrings.- Each substring has a length of at least
minLength. - Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are
'2','3','5', and'7', and the rest of the digits are non-prime.
Return the number of beautiful partitions of s. Since the answer may be very large, return it modulo 10^9 + 7.
A substring is a contiguous sequence of characters within a string.
Example 1
Input
s = "23542185131", k = 3, minLength = 2Output
3There exists three ways to create a beautiful partition: "2354 | 218 | 5131", "2354 | 21851 | 31", and "2354218 | 51 | 31".
Example 2
Input
s = "23542185131", k = 3, minLength = 3Output
1There exists one way to create a beautiful partition: "2354 | 218 | 5131".
Constraints
- 1 <= k, minLength <= s.length <= 1000
- s consists of the digits '1' to '9'.