<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, min_len: int) -> int:
        n=len(s)
        mod=10**9+7
        prime=set(['2','3','5','7'])
        if s[0] not in prime or s[-1] in prime: return 0
        arr=[]
        last,i=0,1
        while i<n:
            if (i==n-1) or (s[i] not in prime and s[i+1] in prime):
                arr.append(i-last+1)
                last=i+1
                i+=2
            else:
                i+=1
        pre_sum={-1:0}
        m=len(arr)
        next_idx=[-1]*m
        for i,val in enumerate(arr):
            pre_sum[i]=pre_sum[i-1]+val
        for i in range(m):
            for j in range(i+1,m+1):
                if pre_sum[j-1]-pre_sum[i-1]>=min_len:
                    next_idx[i]=j-1
                    break
        @cache
        def dp(idx,length,started):
            if idx==m:
                return 1 if (length==k and not started) else 0
            ans=0
            if started:
                #end here
                ans+=dp(idx+1,length+1,0)
                #don't end here
                ans+=dp(idx+1,length,1)
            else:
                #start from here
                if next_idx[idx]!=-1: 
                    ans+=dp(next_idx[idx],length,1)
            return ans%mod
        return dp(0,0,0)
            
261000