#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;
}
namespace Small{
	int f[30],g[30];
	const int ff[]={0,3,6,23,86,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;
				if(x&&c)ans=(ans+2)%mod;
				printf("%d %d\n",val,ans);
			}else{
				int val=1ll*(qpow(2,k)-1)*inv3%mod;
				ans=1ll*ans*2%mod;
				if(!x&&c)ans=(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;
				printf("%d %d\n",val,calc(c+2));
			}
			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(j<n&&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(j<n&&a[j]==a[j+1]){puts("-1");return;}
					a[j+2>>1]=a[j];
				}
				n=n+2>>1;
			}
			--k,++c;
		}
	}
}
namespace Big{
	const int ff[]={0,3,6,23,86,344,1376,5504,22016,88064,352256,1409024,5636096,22544384,90177536,360710144,442840569,771362269,85449055,341796220,367184873,468739485,627755651,874957933};
	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){
			if(c!=0)exit(-1);
			printf("%d %d\n",qpow(2,k-1),2);
			return;
		}
		if(n==2){
			if(c==0){
				printf("%d %d\n",qpow(2,k-1),2);
				return;
			}
		}
		if(n==3)k-=2,++c;
		if(k<=0){puts("-1");return;}
		if(k==1){
			if(x)puts("-1");
			else printf("%d %d\n",1,calc(c+1));
			return;
		}
		printf("%d %d\n",qpow(2,k-1),(7ll*qpow(2,c-2)%mod));
	}
	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]){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(j<n&&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);
	Small::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<=5)Small::solve(n,len);
		else Big::solve(n,len);
	}
}