#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,mod=1e9+7,inv2=mod+1>>1,inv3=(mod+1)/3;
int T,tp;
ll n;
int a[N],b[N];
char s[N];
int qpow(int x,ll y=mod-2){
	int m=1;y%=(mod-1);
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)m=1ll*m*x%mod;
	return m;
}
#define NO {puts(tp?"0 -1":"0");return;}
namespace Baoli{
	int len[N],fa[N],nxt[N][2];
	int tot,lst,f[N];
	vector<int> G[N];
	void init(){
		for(int i=0;i<=tot;i++)len[i]=fa[i]=nxt[i][0]=nxt[i][1]=f[i]=0,G[i].clear();
		len[0]=tot=lst=0,fa[0]=-1;
	}
	void ins(int c){
		int cur=++tot;f[cur]=1;
		len[cur]=len[lst]+1;
		int p=lst;
		while(p!=-1&&!nxt[p][c])nxt[p][c]=cur,p=fa[p];
		if(p==-1)fa[cur]=0;
		else{
			int q=nxt[p][c];
			if(len[p]+1==len[q])fa[cur]=q;
			else{
				int cl=++tot;
				len[cl]=len[p]+1;
				for(int i=0;i<2;i++)nxt[cl][i]=nxt[q][i];
				fa[cl]=fa[q];
				while(p!=-1&&nxt[p][c]==q)nxt[p][c]=cl,p=fa[p];
				fa[q]=fa[cur]=cl;
			}
		}
		lst=cur;
	}
	void dfs(int u){
		for(int v:G[u])dfs(v),f[u]+=f[v];
	}
	void solve(int n,int m){
		init();
		for(int i=0;i<(1<<n);i++)ins(__builtin_popcount(i)&1);
		for(int i=1;i<=tot;i++)G[fa[i]].push_back(i);
		dfs(0);
		int p=0;
		for(int i=1;i<=m;i++){
			p=nxt[p][s[i]-'a'];
			if(!p)NO;
		}
		int ans1=f[p],ans2=0;
		for(int i=1;i<=tot;i++)if(f[i]==ans1)ans2+=len[i]-len[fa[i]];
		if(tp)printf("%d %d\n",ans1,ans2);
		else printf("%d\n",ans1);
	}
}
int pw2[30],f1[30],f2[30],g1[30],g2[30];
void init(int n){
	pw2[0]=1;
	for(int i=1;i<=n;i++)pw2[i]=(pw2[i-1]+pw2[i-1])%mod;
	f1[0]=f1[1]=1,f1[2]=2,f2[2]=1;
	for(int i=3;i<=n;i++){
		f1[i]=(f1[i-1]+2ll*f2[i-1])%mod;
		f2[i]=f1[i-1];
	}
	g1[0]=g1[1]=g2[0]=g2[1]=1;
	g1[2]=4,g2[2]=6;
	for(int i=3;i<=n;i++){
		g1[i]=(1ll*f1[i-1]*pw2[i-1]+5ll*f2[i-1]*pw2[i-3])%mod;
		g2[i]=(g1[i]+1ll*f2[i]*pw2[i-1])%mod;
	}
}
int calc(int c){
	return (1ll*f1[c-2]*(pw2[c-2]+pw2[c-1]+pw2[c-3]+pw2[c-2]+pw2[c-1]+pw2[c-2])+1ll*f2[c-2]*(pw2[c-3]+pw2[c-4]+pw2[c-3]+pw2[c-1]+pw2[c-3]+pw2[c-4]+pw2[c-3]+pw2[c-1]))%mod;
}
void work(ll k,int n,bool x,int c){
	if(n>=5)NO;
	if(n==4)c+=3,x^=1;
	if(n==3)c+=2,x=1;
	if(n==2)c+=1;
	if(k<c)NO;
	if(n==1){
		if(tp)printf("%d %d\n",qpow(2,k-1),2);
		else printf("%d\n",qpow(2,k-1));
		return;
	}
	//if(c+1>=k){
	//	if(tp)printf("%d %d\n",1,calc(k));
	//	else puts("1");
	//	return;
	//}
	if(k-c&1){
		int ans1=1ll*(qpow(2,k-c+1)-1)*inv3%mod;
		int ans2=(g1[c]+g2[c])%mod;
		if(tp)printf("%d %d\n",ans1,ans2);
		else printf("%d\n",ans1);
	}else{
		int ans1=1ll*(qpow(2,k-c+2)-1)*inv3%mod;
		int ans2;
		if(x)ans1=1ll*(ans1-1)*inv2%mod,ans2=g2[c];
		else ans1=1ll*(ans1+1)*inv2%mod,ans2=g1[c];
		if(tp)printf("%d %d\n",ans1,ans2);
		else printf("%d\n",ans1);
	}
}
void solve(ll k,int n){
	int c=0;
	while(1){
		int i=2;
		while(i<=n&&a[i]!=a[i-1])++i;
		if(i>n)return work(k,n,a[1],c);
		if(i&1){
			for(int j=1;j<=n;j+=2){
				if(j<n&&a[j]==a[j+1])NO;
				a[j+1>>1]=a[j];
			}
			n=n+1>>1;
		}else{
			a[0]=a[1]^1;
			for(int j=0;j<=n;j+=2){
				if(j<n&&a[j]==a[j+1])NO;
				a[j+2>>1]=a[j];
			}
			n=n+2>>1;
		}
		++c;
	}
} 
signed main(){
	//freopen("thuemorse.in","r",stdin);
	//freopen("thuemorse.out","w",stdout);
	scanf("%d%d",&T,&tp);
	init(25);
	for(;T--;){
		scanf("%lld\n%s",&n,s+1);
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)a[i]=s[i]=='b';
		if(n<=3)Baoli::solve(n,len);
		else solve(n,len);
	}
}