\(f_{i,j}\) 表示X串前 \(i\) 位 匹配到A串第 \(j\) 位的方案数，因为不能匹配到A串第 \(m\) 位，所以答案是 \(\sum_{i=0}^{m-1}f_{n,i}\)
\(f[i][j] = \sum_{k=0}^{m-1} f[i-1][k] * g[k][j]\)
g[i][j] 是 从第 i 位匹配到第 j 位的方案数
\(f_{i-1} \times G=f_i\)
其实初始的 \(f_0\) 应该是[1,0,0,0,0,0....] 即 \(f_{0,0}=1\)
\(f_0\times G^n = G^n\) 的第一行 所以就没有再写一遍乘法了namespace QvvQ {int n = in, m = in, mod = in, nxt[25];char s[24];struct Mod { int a; Mod(int _a) : a(_a) {} Mod(ll _a) : a(_a % mod) {} Mod() {} int inv() {return Pow(a, mod - 2, mod);} inline Mod &operator += (const int b) {a += b; if (a < 0) a += mod; else if (a >= mod) a -= mod; return *this;} inline Mod &operator -= (const int b) {a -= b; if (a < 0) a += mod; else if (a >= mod) a -= mod; return *this;} inline Mod &operator *= (const int b) {a = a * 1ll * b % mod; if (a < 0) a += mod; return *this;} inline Mod &operator /= (const int b) {a = a * 1ll * Pow(b, mod - 2, mod) % mod; if (a < 0) a += mod; return *this;} inline Mod &operator += (const Mod rhs) {return *this += rhs.a;} inline Mod &operator -= (const Mod rhs) {return *this -= rhs.a;} inline Mod &operator *= (const Mod rhs) {return *this *= rhs.a;} inline Mod &operator /= (const Mod rhs) {return *this /= rhs.a;} friend Mod inline operator + (Mod c, const Mod rhs) {return c += rhs.a;} friend Mod inline operator - (Mod c, const Mod rhs) {return c -= rhs.a;} friend Mod inline operator * (Mod c, const Mod rhs) {return c *= rhs.a;} friend Mod inline operator / (Mod c, const Mod rhs) {return c /= rhs.a;} inline Mod &operator = (const int x) {a = x; return *this;} inline Mod &operator = (const ll x) {a = x % mod; return *this;} inline Mod &operator = (const Mod rhs) {a = rhs.a; return *this;}};// f[i][j] = \sum_{k=0}^m-1 f[i-1][k] * g[k][j]struct Matrix { int n; Mod a[23][21]; Matrix(int _n = 0) {n = _n; lo0(i, n) lo0(j, n) a[i][j] = 0;} Matrix operator * (const Matrix &rhs) const { Matrix res(n); lo0(k, n) lo0(i, n) { if (!a[i][k].a) continue; lo(j, 0, rhs.n) res.a[i][j] += a[i][k] * 1ll * rhs.a[k][j]; } return res; } Matrix operator ^ (int x) const { Matrix res(n), A; A.n = n; lo0(i, n) res.a[i][i] = 1; lo0(i, n) lo0(j, n) A.a[i][j] = a[i][j]; while (x) { if (x & 1) res = res * A; A = A * A; x >>= 1; } return res; }} G(m);void init() { in, s + 1; nxt[1] = 0; for (int i = 2, j = 0; i <= m; ++i) { while (j && s[j + 1] != s[i]) j = nxt[j]; j += s[j + 1] == s[i], nxt[i] = j; } lo0(i, m) lo(cc, '0', '9') { int j = i; while (j && s[j + 1] != cc) j = nxt[j]; j += s[j + 1] == cc, G.a[i][j] += 1; }}void solve() { //其实初始的f_0应该是[1,0,0,0,0,0....] 即f_{0,0}=1 //f_n*G_n = G_n的第一行 所以就没有再写乘法了 G = G ^ n; Mod ans = 0; lo0(i, m) ans += G.a[0][i]; out, ans.a;}}