<p>You are given a string <code>s</code> that consists of the digits <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> and two integers <code>k</code> and <code>minLength</code>.</p>

<p>A partition of <code>s</code> is called <strong>beautiful</strong> if:</p>

<ul>
	<li><code>s</code> is partitioned into <code>k</code> non-intersecting substrings.</li>
	<li>Each substring has a length of <strong>at least</strong> <code>minLength</code>.</li>
	<li>Each substring starts with a <strong>prime</strong> digit and ends with a <strong>non-prime</strong> digit. Prime digits are <code>&#39;2&#39;</code>, <code>&#39;3&#39;</code>, <code>&#39;5&#39;</code>, and <code>&#39;7&#39;</code>, and the rest of the digits are non-prime.</li>
</ul>

<p>Return<em> the number of <strong>beautiful</strong> partitions of </em><code>s</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;23542185131&quot;, k = 3, minLength = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> There exists three ways to create a beautiful partition:
&quot;2354 | 218 | 5131&quot;
&quot;2354 | 21851 | 31&quot;
&quot;2354218 | 51 | 31&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;23542185131&quot;, k = 3, minLength = 3
<strong>Output:</strong> 1
<strong>Explanation:</strong> There exists one way to create a beautiful partition: &quot;2354 | 218 | 5131&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;3312958&quot;, k = 3, minLength = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> There exists one way to create a beautiful partition: &quot;331 | 29 | 58&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k, minLength &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists of the digits <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code>.</li>
</ul>

class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        '''
        partition s into k non intersecting substrings
        each of length >= minLength
        each substring starts with a prime digit and ends with a non prime digit
        2 3 5 7 prime everything else is nonprime
        return the number of beautiful partitions of s modulo 1e9 + 7

        we need to do a dp
        if we get to the end and we did k - 1 cuts
        and each substring is beautiful then we have a good partition
        we need to know the index of the start and the end of the substring to know if the start is prime and the end is non prime
        and to check length

        start, end, cuts
        can be 1000^3
        optimize with a for loop so we can get the length, and the prime conditions in a loop.
        index, cuts
        This way we make much less calls to the dp
        we also only make a cut when it is neccessary.

        index, cuts
        1000 1000
        1000^2 good
        '''
        n = len(s)
        MOD = int(1e9) + 7
        primes = set("2357")

        if s[0] not in primes or s[n - 1] in primes:
            return 0

        @cache
        def dp(index, cuts):
            if cuts == k - 1:
                return 1
            if index >= n or cuts >= k:
                return 0
            
            beautiful = 0
            for i in range(index + minLength - 1, n - (k - cuts - 1) * minLength):
                if s[i] not in primes and s[i + 1] in primes:
                    beautiful += dp(i + 1, cuts + 1)

            return beautiful
            
        return dp(0, 0) % MOD
72700