#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rz resize
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int mod=1e9+7;
int T,tp,sz;
ll n;
string str,str0;
struct SAM{
    struct node{
        int link,len,occ,to[2];
    };
    vector<node>t;
    vector<vector<int>>G;
    vector<int>cnt;
    int tot,last;
    void extend(int c){
        int cur=++tot,p=last;
        t[cur].len=t[p].len+1;
        while(p!=-1&&!t[p].to[c]){
            t[p].to[c]=cur;
            p=t[p].link;
        }
        if(p!=-1){
            int q=t[p].to[c];
            if(t[q].len==t[p].len+1){
                t[cur].link=q;
            }
            else{
                int clone=++tot;
                for(int i=0;i<2;i++)t[clone].to[i]=t[q].to[i];
                t[clone].link=t[q].link,t[clone].len=t[p].len+1;
                t[q].link=t[cur].link=clone;
                while(p!=-1&&t[p].to[c]==q){
                    t[p].to[c]=clone;
                    p=t[p].link;
                }
            }
        }
        t[cur].occ++;
        last=cur;
    }
    void dfs(int u){
        for(auto v:G[u]){
            dfs(v);
            t[u].occ+=t[v].occ;
        }
    }
    void build(int n){
        t.rz((1<<n+1)+5);
        G.rz((1<<n+1)+5);
        cnt.rz((1<<n+1)+5);
        t[0].link=-1;
        for(int i=0;i<1<<n;i++)extend(__builtin_popcount(i)&1);
        for(int i=1;i<=tot;i++){
            G[t[i].link].pb(i);
        }
        dfs(0);
        for(int i=1;i<=tot;i++){
            cnt[t[i].occ]=(cnt[t[i].occ]+t[i].len-t[t[i].link].len)%mod;
        }
    }
    pair<int,int>qry(string &str){
        int it=0,o=1;
        for(int i=0;i<str.size();i++){
            int c=str[i]-'a';
            if(!t[it].to[c]){
                o=0;
                break;
            }
            it=t[it].to[c];
        }
        if(!o){
            return {0,-1};
        }
        return {t[it].occ,cnt[t[it].occ]};
    }
    
}sam[21];
ll fpow(ll x,ll y=mod-2){
    ll z(1);
    for(;y;y>>=1){
        if(y&1)z=z*x%mod;
        x=x*x%mod;
    }return z;
}
ll calc(ll n,int f=0){
    if(n<0)return 0;
    ll res;
    if(n%2==0)res=((fpow(2,n+1)-2)*fpow(3)+f*(n%2==0))%mod;
    else res=((fpow(2,n+1)-1)*fpow(3)+f*(n%2==0))%mod;
    return (res+mod)%mod;
}
ll calc0(ll n,int f){
    if(!f){
        if(n==1)return 1;
        if(n==2)return 4;
        return 13*fpow(4,n-3)%mod;
    }
    if(n==1)return 1;
    if(n==2)return 6;
    return 21*fpow(4,n-3)%mod;
}
pair<ll,ll>sol(){
    sz=str.size();
    ll c=0;
    while(1){
        int o=-1;
        for(int i=0;i<sz-1;i++){
            if(str[i]==str[i+1]){
                o=i;
                break;
            }
        }
        if(o==-1)break;
        str0.clear();
        for(int i=o%2;i<=o;i+=2){
            if(str[i]=='b')str0+='a';
            else str0+='b';
        }
        for(int i=o+1;i<sz;i+=2){
            if(i+1<sz&&str[i]==str[i+1])return {0,-1};
            if(str[i]=='a')str0+='a';
            else str0+='b';
        }
        str=str0,sz=str.size(),c++;
        //cout<<str<<" "<<n<<"\n";
    }
    //cout<<str<<" "<<n<<"\n";
    if(sz>=5)return {0,-1};
    bool x=str[0]-'a';
    if(sz==4)c+=3,x^=1;
    if(sz==3)c+=2,x=1;
    if(sz==2)c+=1;
    //答案只和c,x有关
    //算的是n-c阶串里面ab,ba总出现次数+(x^1)*(n-c mod 2 == 0)
    if(c>n||c==n&&x)return {0,-1};
    //缩出来是a/b,原串也只能是a/b
    if(sz==1){
        return {fpow(2,n-1),2};
    }
    //出现次数为1(??)
    //此时缩出来可能是(n,0),也可能是(n-1,0/1)
    if(c+1>=n){
        return {1,(calc0(n,0)+calc0(n-1,0)+calc0(n-1,1))%mod};
    }
    //calc0(c,0/1):缩出来为(c,0/1)的等价类个数
    if(n-c&1){
        return {calc(n-c,x^1),(calc0(c,0)+calc0(c,1))%mod};
    }
    return {calc(n-c,x^1),calc0(c,x)};
}
// string get(string str){
//     sz=str.size();
//     while(1){
//         int o=-1;
//         for(int i=0;i<sz-1;i++){
//             if(str[i]==str[i+1]){
//                 o=i;
//                 break;
//             }
//         }
//         if(o==-1)break;
//         str0.clear();
//         for(int i=o%2;i<=o;i+=2){
//             if(str[i]=='b')str0+='a';
//             else str0+='b';
//         }
//         for(int i=o+1;i<sz;i+=2){
//             if(i+1<sz&&str[i]==str[i+1])return "fail";
//             if(str[i]=='a')str0+='a';
//             else str0+='b';
//         }
//         str=str0,sz=str.size(),n--;
//         //cout<<str<<" "<<n<<"\n";
//     }
//     return str;
// }
int main(){
    // freopen("thuemorse.in","r",stdin);
    // freopen("thuemorse.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    for(int i=1;i<=5;i++)sam[i].build(i);
    // for(int i=1;i<=6;i++){
    //     cout<<"len:"<<i<<"\n";
    //     for(int j=0;j<1<<i;j++){
    //         string tmp;
    //         for(int k=0;k<i;k++){
    //             if(j>>k&1)tmp+='b';
    //             else tmp+='a';
    //         }
    //         cout<<tmp<<" "<<get(tmp)<<"\n";
    //     }
    // }
    cin>>T;tp=1;
    while(T--){
        cin>>n>>str;
        pair<ll,ll>tmp;
        if(n<=5){
            tmp=sam[n].qry(str);
        }
        else{
            tmp=sol();
        }
        if(!tp)cout<<tmp.fi<<"\n";
        else cout<<tmp.fi<<" "<<tmp.se<<"\n";
    }
}