题解（首发）

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

vector<int> getPrimes(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
            for (int i = p * 2; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    return primes;
}

int countDecompositions(int N, int M) {
    vector<int> primes = getPrimes(N);
    vector<int> dp(N + 1, 0);
    dp[0] = 1;
    
    for (int p : primes) {
        for (int j = N; j >= p; j--) {
            for (int k = 1; k <= M && j - k * p >= 0; k++) {
                dp[j] = (dp[j] + dp[j - k * p]) % MOD;
            }
        }
    }
    return dp[N];
}

int main() {
    int N, M;
    cin >> N >> M;
    cout << countDecompositions(N, M) << endl;
    return 0;
}

deepseek协作完成