#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 30;
const int mod = 1000000007;

int a[maxn], b[maxn], c[maxn], par[maxn], num[maxn], tot;
char s[maxn];

int findp(int x)
{
    return par[x] == x ? x : par[x] = findp(par[x]);
}

void unite(int u, int v)
{
    u = findp(u), v = findp(v);
    if(u == v) return;
    par[v] = u;
    num[u] += num[v];
}

int getid(int x)
{
    if(c[x] == -1)
    {
        c[x] = tot;
        b[tot] = 0;
        a[tot] = x;
        ++tot;
    }
    return c[x];
}

int pow_mod(int x, int n)
{
    int ret = 1;
    while(n)
    {
        if(n & 1) ret = (ll)ret * x % mod;
        x = (ll)x * x % mod;
        n >>= 1;
    }
    return ret;
}

ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

int cal(int n, int s, int now)
{
    int cnt = 0, f = 0;
    for(int i = 0; i < tot; ++i) if(s >> i & 1) cnt += b[i], ++f;
    if((now - f) % 2 == 0) f = 1;
    else f = -1;
    return f * pow_mod(cnt, n);
}

void inc(int &a, int b)
{
    a += b;
    if(a >= mod) a -= mod;
    else if(a < 0) a += mod;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < 26; ++i)
        {
            par[i] = i;
            num[i] = 1;
        }
        tot = 0;
        memset(c, -1, sizeof(c));
        scanf("%s", s);
        for(int i = 0; i < 26; ++i)
        {
            int d = s[i] - 'a';
            unite(i, d);
        }
        for(int i = 0; i < 26; ++i)
        {
            if(findp(i) != i) continue;
            int id = getid(num[i]);
            b[id] += num[i];
        }
        int ans = 0;
        for(int st = 0; st < (1 << tot); ++st)
        {
            ll l = 1;
            int now = 0;
            for(int i = 0; i < tot; ++i) if(st >> i & 1) l = lcm(l, a[i]), ++now;
            int tmp = 0;
            for(int ss = st; ss; ss = st & (ss - 1))
            {
                inc(tmp, cal(n, ss, now));
            }
            inc(ans, l % mod * tmp % mod);
        }
        printf("%d\n", ans);
    }
    return 0;
}