P3193.cpp

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int nxt[22];

struct Matrix {
    int dat[22][22];

    Matrix operator*(const Matrix& m) const {
        Matrix res;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                res.dat[i][j] = 0;
            }
        }

        for (int i = 0; i < M; i++) {
            for (int k = 0; k < M; k++) {
                for (int j = 0; j < M; j++) {
                    res.dat[i][j] = (res.dat[i][j] + dat[i][k] * m.dat[k][j]) % K;
                }
            }
        }
        return res;
    }
};

Matrix qpow(Matrix a, int k) {
    Matrix res;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            res.dat[i][j] = 0;
        }
        res.dat[i][i] = 1;
    }
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M >> K;
    Matrix G;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            G.dat[i][j] = 0;
        }
    }

    string s;
    cin >> s;
    s = ' ' + s;

    for (int i = 2; i < M; i++) {
        nxt[i] = nxt[i-1];
        while (nxt[i] && s[nxt[i]+1] != s[i]) nxt[i] = nxt[nxt[i]];
        if (s[nxt[i]+1] == s[i]) nxt[i]++;
    }

    for (int i = 0; i < M; i++) {
        for (int c = 0; c <= 9; c++) {
            int j = i;
            while (j && s[j+1] - '0' != c) j = nxt[j];
            if (s[j+1] - '0' == c) j++;
            G.dat[j][i] = (G.dat[j][i] + 1) % K;
        }
    }

    G = qpow(G, N);
    int ans = 0;
    for (int i = 0; i < M; i++) ans = (ans + G.dat[i][0]) % K;
    cout << ans << '\n';
    return 0;
}