思路与算法

状态 $j\in[0,m-1]$ 表示当前号码的后缀与禁串前缀相同的最大长度。长度达到 $m$ 就已经出现禁串，必须丢弃该转移。前导零合法，因此每一步都枚举完整十进制字符0至9。

先计算禁串的前缀函数 $\pi$。从状态 $j$ 追加字符时，若字符与禁串下一位不匹配，沿 $\pi[j-1]$ 回退，直到可匹配或到0；匹配则长度加1。对所有状态和10种字符建立固定矩阵 $A$：$A_{u,v}$ 为从旧状态 $v$ 转移到新状态 $u$ 的字符种数，达到终态 $m$ 的字符不计入。

初始空串只有状态0的计数为1，即列向量 $V_0=(1,0,\ldots,0)^\mathsf T$。长度为 $n$ 的合法串分布是 $V_n=A^nV_0$。用二进制矩阵幂，最后把全部非终态计数相加并对 $K$ 取模。矩阵幂结果的第0列恰为该初始向量的转移结果。

正确性说明

前缀函数回退枚举当前匹配前缀的全部可能边界，找到追加字符后最长的合法前后缀重合长度，因此状态转移完整且不重复。若产生长度 $m$ 的匹配，禁串已出现，该串及其全部后续扩展都不合法，所以丢弃恰当；不能像普通KMP枚举匹配那样完成匹配后回退继续计数。

每个旧合法串追加一个字符，恰对应一条矩阵转移；矩阵元素记录不同字符的数量，乘法累加便逐一统计新串。由空串初始状态归纳，$A^nV_0$ 精确统计所有长为 $n$ 的避开禁串的号码。每个号码恰落在一个非终态，求和即总数。模运算只改变计数表示，不改变目标余数。

复杂度

前缀函数初始化与计算 $O(m)$。这里逐个状态、字符沿失败链建立转移，给出保守界 $O(10m^2)$；初始化矩阵为 $O(m^2)$。矩阵幂每次乘法 $O(m^3)$，共 $O(\log(n+1))$ 轮，最后求和 $O(m)$。总时间 $O(m+10m^2+m^3\log(n+1))$，额外空间 $O(m^2)$。不分配长度为 $n$ 的数组。

易错点

1. 禁串作为字符串读取，保留前导零，状态0也允许追加0。
2. 禁止完整匹配后不能再回退继续计数；重叠前后缀则由失败链正确处理。
3. 矩阵定义是新状态行、旧状态列，与列向量约定一致；初始空串仅状态0为1。
4. $K$ 可为合数，不可依赖模逆元或费马小定理。代码只做加乘及取模。
5. 覆盖 $n<m$、单字符禁串、全零重叠、周期禁串、最大 $n$ 和合数模数。原候选K=9973超出当前源K≤1000，全包点拒用且未改原包；本题为合规自编训练数据与样例。独立答案以自相关生成函数和无除法Kitamasa验证，另与直接后缀DP及完整短串枚举交叉核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int size_, mod;
using Matrix = vector<vector<ll>>;
Matrix multiply(const Matrix &a, const Matrix &b) {
    Matrix c(size_, vector<ll>(size_));
    for (int i = 0; i < size_; i++)
        for (int k = 0; k < size_; k++)
            if (a[i][k])
                for (int j = 0; j < size_; j++)
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    string pattern;
    cin >> n >> size_ >> mod >> pattern;
    vector<int> pi(size_);
    for (int i = 1; i < size_; i++) {
        int j = pi[i - 1];
        while (j && pattern[i] != pattern[j])
            j = pi[j - 1];
        if (pattern[i] == pattern[j])
            j++;
        pi[i] = j;
    }
    Matrix base(size_, vector<ll>(size_)), result(size_, vector<ll>(size_));
    for (int state = 0; state < size_; state++) {
        result[state][state] = 1;
        for (char digit = '0'; digit <= '9'; digit++) {
            int next = state;
            while (next && pattern[next] != digit)
                next = pi[next - 1];
            if (pattern[next] == digit)
                next++;
            if (next < size_)
                base[next][state]++;
        }
    }
    while (n) {
        if (n & 1)
            result = multiply(result, base);
        base = multiply(base, base);
        n >>= 1;
    }
    ll answer = 0;
    for (int state = 0; state < size_; state++)
        answer = (answer + result[state][0]) % mod;
    cout << answer << '\n';
}