public class Solution {
    final int MOD = 1000000007;

    public int beautifulPartitions(String s, int k, int minLength) {
        int n = s.length();
        boolean[] isPrime = new boolean[n];
        boolean[] bs = new boolean[128];
        bs[50] = true;
        bs[51] = true;
        bs[53] = true;
        bs[55] = true;
        int index = 0;
        int[][] dp = new int[s.length()][k + 1];

        for (byte aByte : s.getBytes()) {
            if (bs[aByte]) {
                isPrime[index] = true;
            }
            index++;
        }
        // 如果最后一个是质数或第一个不是质数，不可能分割
        if (isPrime[n - 1] || !isPrime[0]) return 0;

        // 单个字符不可能分割，因为其不可能又是质数，又不是质数，直接从第二个开始
        for (int i = 1; i < n; i++) {

            // 右边是质数，以当前字符串分割不可能获得完美分割
            if (isPrime[i]) {
                // 直接跳过
                continue;
            }

            // 遍历 k
            for (int j = 1; j <= k; j++) {

                // 初始化条件
                if (j == 1) {
                    dp[i][j] = 1;
                    continue;
                }

                // 记录答案
                int ans = 0;

                // 遍历子串,l为子串右边位置
                for (int l = i - minLength; l >= 0; l--) {
                    // 如果分割的 l~i的左边不是质数，不满足条件，不考虑
                    if (!isPrime[l + 1]) {
                        continue;
                    }
                    // 否则加入记录
                    ans = add(ans, dp[l][j - 1]);
                }
                // 赋值
                dp[i][j] = ans;
            }
        }
        for (int i = 0; i < dp.length; i++) {
            System.out.println();
            for (int j = 0; j < dp[0].length; j++) {
                System.out.print(dp[i][j] + "，");

            }
        }
        return dp[n - 1][k];
    }

    int add(int a, int b) {
        return (a % MOD + b % MOD) % MOD;
    }

    @Test
    public void test() {
        String s = "23542185131";
        int k = 3;
        int minLength = 3;
        beautifulPartitions(s, k, minLength);
    }
}