翻译：
定义f[i]=f[i-1]+f[i-2]，+表示拼接的意思，即为f[i-1]与f[i-2]拼接起来组成f[i]
给出一个子串(长度<=100)，求这个子串在fn(n<=100)的子序列中出现了多少次
答案对1e9+7取模
题解
由于英文不好我理解成了子串与后缀
然后发现就不会做了2333
上网%了一发题解发现原来我我我我看错题了
由于求的是子序列，那么这个转移就很简单了
设f[i][l][r]表示，第i轮拼接，能匹配子串l~r的方案数
转移可以写成
f[i][l][r]+=f[i-1][l][r]+f[i-2][l][r]
f[i][l][r]+=f[i-1][l][k]*f[i-2][k+1][r]
考虑影响答案的情况
对于r=n，我们可以在i-1这个子串里加上2^lenth[i-1]这么多子序列。lenth[i]表示第i个拼接的长度
对于l=1，我们可以在l-2这个子串里加上2^lenth[i-2]这么多子序列
那么就这样差不多啦
/* 翻译： 定义f[i]=f[i-1]+f[i-2]，+表示拼接的意思，即为f[i-1]与f[i-2]拼接起来组成f[i] 给出一个子串(长度<=100)，求这个子串在fn(n<=100)的**子序列**中出现了多少次 答案对1e9+7取模 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL f[110][110][110];
LL lenth[110];//添加2^lenth[i]次方个数
char ch[110];int n,m;
int main()
{scanf("%d%d",&n,&m);scanf("%s",ch+1);for(int i=1;i<=n;i++)f[ch[i]-'0'][i][i]=1;lenth[0]=lenth[1]=2;for(int i=2;i<=m;i++)lenth[i]=(lenth[i-1]*lenth[i-2])%mod;for(int i=2;i<=m;i++)for(int l=1;l<=n;l++)for(int r=l;r<=n;r++){LL opx,opy;if(l==1)opx=lenth[i-1];else opx=1;if(r==n)opy=lenth[i-2];else opy=1;f[i][l][r]=(f[i][l][r]+(opx*f[i-2][l][r]+opy*f[i-1][l][r])%mod)%mod;for(int k=l;k<r;k++)f[i][l][r]=(f[i][l][r]+f[i-1][l][k]*f[i-2][k+1][r])%mod;}printf("%lld\n",f[m][1][n]);return 0;
}