#include <iostream>

using namespace std;

const int maxn = 605;

#define int long long

const int mod = 999911659;

int n, p, r;
int cnt[maxn], pos[maxn][maxn];
int dp[maxn][maxn][10];
int inv[maxn], c[maxn][maxn];

int pw(int a, int b)
{
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
signed main()
{
    cin >> n >> p;
    int sum = 0, lst = 1;
    r = p;
    for (int i = 1; i <= p; i++) {
        sum = (10 * sum % p + 1) % p;
        lst = i;
        cnt[sum % p]++;
        pos[sum % p][++pos[sum % p][0]] = i;
        if (sum % p == 0)
            break;
    }
    for (int i = 0; i < p; i++) {
        cnt[i] *= (n / lst);
        for (int j = 1; j <= pos[i][0]; j++) {
            if (pos[i][j] <= n % lst) {
                cnt[i]++;
                if (pos[i][j] == n % lst)
                    r = i;
            } else
                break;
        }
        cnt[i] %= mod;
    }
    // cout << r << "\n";
    // for (int i = 0; i < p; i++)
    // cout << cnt[i] << "\n";
    for (int i = 0; i <= 8; i++)
        inv[i] = pw(i, mod - 2);
    for (int i = 0; i < p; i++)
        for (int j = 0; j <= 8; j++) {
            // c[i][j] = C_{cnt[i] + j - 1}^{j}
            c[i][j] = 1;
            for (int k = 1, s = cnt[i] + j - 1; k <= j; k++, s--)
                c[i][j] = s % mod * c[i][j] % mod * inv[k] % mod;
        }
    // for (int i = 0; i < p; i++)
    // for (int j = 0; j <= 8; j++)
    // cout << "C(" << cnt[i] + j - 1 << ", " << j << "):" << c[i][j] << "\n";
    for (int i = 0; i <= 8; i++)
        dp[0][0][i] = c[0][i];
    for (int i = 0; i < p; i++)
        for (int j = 0; j <= 8; j++)
            for (int k = 0; k <= 8 - j; k++)
                for (int pre = 0; pre < p; pre++)
                    (dp[i + 1][(pre + k * (i + 1) % p) % p][j + k] += (dp[i][pre][j] * c[i + 1][k] % mod)) %= mod;
    int ans = 0;
    for (int i = 0; i <= 8; i++)
        (ans += dp[p - 1][p - r][i]) %= mod;
    cout << ans << "\n";
    return 0;
}

你好。我是一个发帖狂人。