#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;
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;
}
int f[30],g[30];
const int ff[]={0,3,6,23,84,344,1376,5504,22016,88064,352256,1409024,5636096,22544384,90177536,360710144,442840569,771362269,85449055,341796220,367184873,468739485,627755651,874957933};
void init(int n){
	for(int i=1;i<=n;i++)f[i]=(2*f[i-1]+(i&1^1))%mod;
	for(int i=1;i<=n;i++)g[i]=2*(g[i-1]+1)%mod;
}
int calc(int x){//求出出现恰好一次的本质不同子串数量 
	return ff[x];
}
void work(ll k,int n,bool x,int c){
//	printf("%lld %d %d %d\n",k,n,x,c);
	if(k<0||n>=5){puts("-1");return;}
	if(n==4)n-=2,k-=2,c+=2,x^=1;
	if(n==1){
		int ans=2ll*(f[c]+1)*(f[c]+1)%mod;
		if(k==0){
			if(x==1)puts("-1");
			else printf("1 %d\n",calc(c));
		}else if(k==1)printf("1 %d\n",calc(k+c));
		else{
			printf("%d %d\n",qpow(2,k-1),ans);
		}
		return;
	}
	if(n==2){
		int ans=1ll*(f[c+1]+1)*(f[c+1]+1)%mod;
		if(k==0)puts("-1");
		else if(k==1){
			if(x==1)puts("-1");
			else printf("1 %d\n",calc(k+c));
		}else if(k==2){
			printf("1 %d\n",calc(k+c));
		}else if(k&1){
			int val=1ll*(qpow(2,k+1)-1)*inv3%mod;
			val=1ll*(val+1)*inv2%mod;
			if(x)val=(val-x+mod)%mod;
			printf("%d %d\n",val,ans);
		}else{
			int val=1ll*(qpow(2,k)-1)*inv3%mod*2%mod;
			ans=1ll*ans*2%mod;
			printf("%d %d\n",val,ans);
		}
		return;
	}
	if(n==3){
		k-=2;
		if(k<=0)puts("-1");
		else if(k==1){
			printf("1 %d\n",calc(k+c+2));//求出出现恰好一次的本质不同子串数量 
		}else{
			int val=1ll*(qpow(2,k+(k&1))-1)*inv3%mod;
			if(k&1^1)val=2ll*val%mod;
			int ans=2ll*(g[c]+1)*(g[c]+1)%mod;
			printf("%d %d\n",val,ans);
		}
		return;
	}
	puts("-1");
}
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(a[j]==a[j+1]){puts("-1");return;}
				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(a[j]==a[j+1]){puts("-1");return;}
				a[j+2>>1]=a[j];
			}
			n=n+2>>1;
		}
		--k,++c;
	}
}
signed main(){
	scanf("%d",&T);
	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';
		solve(n,len);
	}
}