#include <stdio.h>
#include <algorithm>

using namespace std;

//long long
const long long mod = 1000000007;
long long n;
char z[30];
long long fring[30];
long long vis[30] , ringt[30] , rings[30] , top;
long long least[1<<10] , exact[1<<10];
long long cnt[1<<10] , cnt1[65567];
long long ans;
void clear () {
    long long i;
    for ( i = 0 ; i <= (1<<top) ; i++ ) least[i] = exact[i] = 0;
    top = 0;
    for ( i = 0 ; i <= 29 ; i++ ) vis[i] = ringt[i] = rings[i] = fring[i] = 0;
}
void predo () {
    long long i , j , num;
    for ( i = 0 ; i <= 65535 ; i++ ) {
        j = i;
        num = 0;
        while ( j ) {
            if ( j % 2 == 1 ) num++;
            j >>= 1;
        }
        cnt1[i] = num;
    }
    for ( i = 1 ; i <= (1<<10) ; i++ ) {
        cnt[i] = cnt1[i&65535] + cnt1[i>>16];
    }
}
long long pow ( long long f , long long x ) {
    long long t , s;
    s = 1; t = f;
    while ( x ) {
        if ( x % 2 == 1 ) s = (s*t) % mod;
        t = (t*t) % mod; x >>= 1;
    }
    return s;
}
long long gcd ( long long a , long long b ) {
    long long t;
    if ( a < b ) swap ( a , b );
    while ( b ) {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}
void work () {
    clear ();
    long long i , j , k , num , sum;
    scanf ( "%I64d" , &n );
    scanf ( "%s" , z + 1 );
    for ( i = 1 ; i <= 26 ; i++ ) {
        if ( !vis[i] ) {
            num = 1;
            j = z[i]-'a'+1;
            while ( j != i ) {
                num++;
                vis[j] = 1;
                j = z[j]-'a'+1;
            }
            vis[i] = 1;
            fring[num]++;
        }
    }
    for ( i = 1 ; i <= 26 ; i++ ) if ( fring[i] ) {
        ringt[++top] = i;
        rings[top] = i * fring[i];
    }
    for ( i = 0 ; i < (1<<top) ; i++ ) {
        sum = 0;
        j = i;
        for ( k = 1 ; k <= top ; k++ ) {
            if ( j % 2 == 1 ) sum += rings[k];
            j >>= 1;
        }
        least[i] = pow ( sum , n );
    }
    for ( i = 0 ; i < (1<<top) ; i++ ) {
        for ( k = i ; k ; k = (k-1) & i ) {
            if ( cnt[i] % 2 == cnt[k] % 2 ) exact[i] = (exact[i] + least[k]) % mod;
            else exact[i] = (exact[i] - least[k] + mod) % mod;
        }
    }
    ans = 0;
    for ( i = 1 ; i <= (1<<top) ; i++ ) {
        j = i;
        num = 1;
        for ( k = 1 ; k <= top ; k++ ) {
            if ( j % 2 == 1 ) {
                num = (num*ringt[k]) / gcd ( num , ringt[k] );
                num %= mod;
            }
            j >>= 1;
        }
        ans = ans + (exact[i]*num) % mod;
        ans %= mod;
    }
    printf ( "%I64d\n" , ans );
}
int main () {
    int t;
    scanf ( "%d" , &t );
    predo ();
    while ( t-- ) work ();
    return 0;
}