题目：

首先想到 确保模式串不出现 就是 确保每个位置的后缀不是该模式串。

为了dp，需要记录第 i 个位置的后缀已经有几位和模式串的前几位吻合了。

所以想到可以转移到 j+1 或 0 。

但其实不一定是0，因为可能和前面的接上。这里就要用kmp了！

注意可以和很多位置接上的时候，应该和最长的那个接上，而不是和每个 nxt 都接上，也不是什么能选择的。

知道了当前 j 能转移到哪些 j ，就可以矩阵优化了。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=25;int n,m,mod,nxt[N],prn,ch[N];struct Matrix{  int a[N][N];  Matrix(){memset(a,0,sizeof a);}  Matrix operator * (const Matrix &b)const  {    Matrix c;    for(int i=0;i
        
         
          
           >=1;} for(int i=0;i