n=40的01串，求有多少m=40的01串中包含它，包含的定义是存在子串有至多一个字符不相同
600组n=15的数据 15组n=40的数据，所以我们只能支持n^5的算法。
陷入两个比较有意思的坑：
1 如果手动构建fail树，建立两个并行的串，左串代表当前未使用那一个可以不相同的字符的名额，右串代表已经使用了这个名额，那么按照bfs m步的想法，左串可以通过“使用名额”到达右串，也可以通过“不使用名额”走一个fail，而右串一旦失配，只能在右串的对应位置进行fail。这样跑一遍矩阵乘法，复杂度是(2*n)^3
但是不对，因为假设右串失配了，可能距离一个点从左串跳过来已经过了很久了，那个名额已经可以再次使用了，所以它可以再跳回左串。这样就会导致我们失去一些答案。
2 如果插入n+1个串，代表原串，和原串第i个位置不同的串，这样点是n^3，那么矩阵乘法是n^6，还有一个logm的快速幂时间，复杂度会超
陷入了误区：快速幂一定比直接转移快。快速幂的快体现在将m转移到logm，但是二维矩阵的自乘是(点数^3)的，加一个快速幂的优化是从m(n*n)到logm(n*n*n)。
所以暴力插入n+1个串建树，暴力(n*n)^2的枚举边，跑m次转移。
L read() {L x;scanf("%lld" , &x) ; return x ; } ;
char s[50] ;
L c[40 * 40 + 5] ;
L a[40 * 40 + 5][40 * 40 + 5] ;
L b[40 * 40 + 5] ;
L n , m ;
struct AC{
L next[40 * 40 + 5][2] , fail[40 * 40 + 5] , en[40 * 40 + 5] ;
L ro , to ;
L newnode() {
to++;
for(L i = 0 ; i < 2 ; i ++ ) next[to][i] = -1 ;
en[to] = 0 ;
return to ;
}
void init() {
to = -1 ;
ro = newnode() ;
}
void inse() {
L now = ro ;
for(L i = 1 ; i <= n ; i ++ ) {
if(next[now][s[i]-'0'] == -1) next[now][s[i]-'0'] = newnode();
now = next[now][s[i]-'0'];
}
en[now]++;
}
void build() {
queue<int>q;
fail[ro]=ro;
for(L i=0;i<2;i++){
if(next[ro][i] == -1) next[ro][i]=ro;
else {
fail[next[ro][i]]=ro;
q.push(next[ro][i]);
}
}
while(!q.empty()){
L now=q.front();q.pop();
for(L i=0;i<2;i++){
if(next[now][i]==-1)next[now][i] = next[fail[now]][i] ;
else {
fail[next[now][i]] = next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
void gao() {
inse() ;
for(int i = 1 ; i <= n ; i ++ ) {
s[i] = '0' + ((s[i] - '0') ^ 1) ;
inse();
s[i] = '0' + ((s[i] - '0') ^ 1) ;
}
build() ;
for(int i = 0 ; i <= to ; i ++ ) {
for(int j = 0 ; j <= 1 ; j ++ ) {
int v = next[i][j];
if(en[i] == 0)
a[i][v] ++ ;
}
}
for(int i = 0 ; i <= to ; i ++ ) {
if(en[i] != 0) a[i][i] += 2 ;
}
b[0] = 1 ;
for(int i = 1 ; i <= m ; i ++ ) {
memset(c, 0 , sizeof(c)) ;
for(int u = 0 ; u <= to ; u ++ ) {
for(int v = 0 ; v <= to ; v ++ ) {
c[v] += b[u] * a[u][v] ;
}
}
for(int j = 0 ; j <= to ; j ++ )
b[j] = c[j] ;
}
L ans = 0 ;
for(int i = 0 ; i <= to ; i ++ ) {
if(en[i] != 0) ans += b[i] ;
}
cout << ans << endl ;
}
}ac;
int main () {
L t = read() ;
while(t -- ) {
n = read() ; m = read() ;
scanf("%s" , s+1) ;
memset(a,0,sizeof(a)) ;
memset(b,0,sizeof(b)) ;
ac.init() ;
ac.gao() ;
}
}