将所有序列的数量，减去全部数值都是合数的序列数量，就是有至少一个质数的序列的数量。然后可以想到一个递推：f(i, j)代表序列长度为i，所有数字之和mod p的值是j的话，序列的数量。用矩阵乘法做这个递推就可以了。

#include <cstdio>

#define mul(a, b) (((long long)(a) * (long long)(b)) % 20170408)

bool composite[20000005];
int composite_mod[105];
int all_mod[105];

using namespace std;

int n, m, p;

int matrix[100][100];
int fastpow[32][100][100];
int current[32][100];

int calc(int* modlist)
{
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < p; j++) {
            matrix[i][j] = fastpow[0][i][j] = modlist[(((j - i) % p) + p) % p];
        }
    }
    for (int pwr = 1; pwr < 32; pwr++) {
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < p; j++) {
                fastpow[pwr][i][j] = 0;
                for (int k = 0; k < p; k++) {
                    fastpow[pwr][i][j] += mul(fastpow[pwr-1][i][k], fastpow[pwr-1][k][j]);
                    if (fastpow[pwr][i][j] >= 20170408) {
                        fastpow[pwr][i][j] -= 20170408;
                    }
                }
            }
        }
    }
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < p; j++) {
            current[i][j] = 0;
        }
    }
    current[0][0] = 1;
    int working = 1;
    for (int bit = 0; bit < 32; bit++) {
        if (n & (1 << bit)) {
            for (int i = 0; i < p; i++) {
                for (int j = 0; j < p; j++) {
                    current[working][i] += mul(current[working-1][j], fastpow[bit][j][i]);
                    if (current[working][i] >= 20170408) {
                        current[working][i] -= 20170408;
                    }
                }
            }
            working++;
        }
    }
    return current[working-1][0];
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    /* Technically, this is incorrect, but good enough for our purposes */
    composite[1] = true;
    
    for (int i = 2; i <= 5000; i++) {
        if (!composite[i])
            for (int j = i << 1; j <= 20000000; j += i) {
                composite[j] = true;
        }
    }
    int curmod = 1 % p;
    for (int i = 1; i <= m; i++) {
        all_mod[curmod]++;
        if (composite[i]) {
            composite_mod[curmod]++;
        }
        curmod++;
        if (curmod == p) {
            curmod = 0;
        }
    }
    printf("%d", (((calc(all_mod)-calc(composite_mod))
             % 20170408) + 20170408) % 20170408);
    return 0;
}