#include <bits/stdc++.h>
using namespace std;
#define INF 1000000007
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> ii;
typedef vector<pair<int,int> > vii;
typedef vector<vector<pair<int,int> > > vvii;
#define all(x) x.begin(), x.end()
#define tr(x,it) for(auto it = x.begin();it!=x.end();++it)
#define sz(a) int((a).size())
#define pb push_back
#define MP make_pair
#define fpresent(c,x) ((c).find(x) != (c).end()) // set,map
#define present(c,x) (find(all(c),x) != (c).end()) //vector
#define X first
#define Y second
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define NFOR(i,a,b) for(int i=a;i>=b;--i)
ll expo(int base, int exp, int MOD=INF) {
ll res=1;
while(exp>0) {
if(exp&1) res=(res*base)%MOD;
base=((ll)base*base)%MOD;
exp=exp>>1;
}
return res;
}
struct node
{
char c;
node *next[26];
int no;
void reset(char ch)
{
c=ch;
FOR(i,0,25)next[i]=NULL;
no=1;
}
};
int fac[5001];
int invf[5001];
int f[5001];
int ans[5001];
node *root;
char s[5001];
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);
fac[0]=1;invf[0]=1;
FOR(i,1,5000)
{
fac[i]=((ll)fac[i-1]*i)%INF;
invf[i]=expo(fac[i],INF-2);
}
int T;
cin>>T;
while(T--)
{
memset(f,0,sizeof(f));
int n,q;
cin>>n>>q;
cin>>s;
root=(node *)malloc(sizeof(node));
root->reset('$');
node *curr;
FOR(i,0,n-1)
{
curr=root;
FOR(j,i,n-1)
{
if(curr->next[s[j]-'a']==NULL)
{
curr->next[s[j]-'a']=(node *)malloc(sizeof(node));
curr=curr->next[s[j]-'a'];
curr->reset(s[j]);
++f[1];
}
else {curr=curr->next[s[j]-'a'];--f[curr->no];(curr->no)+=1;++f[curr->no];}
}
}
ll temp=0;
memset(ans,0,sizeof(ans));
FOR(i,1,n)
{
if(f[i])
FOR(j,1,i)
{
//=((((((ll)fac[i]*(ll)invf[j])%INF)*(ll)invf[i-j])%INF)*(ll)f[i])%INF;
temp=(ll)fac[i]*invf[j];
if(temp>=INF)temp%=INF;
temp*=invf[i-j];
if(temp>=INF)temp%=INF;
temp*=f[i];
if(temp>=INF)temp%=INF;
ans[j]+=temp;
if(ans[j]>=INF)ans[j]-=INF;
}
}
int x;
while(q--)
{
cin>>x;
if(x<=n)cout<<ans[x]<<"\n";else cout<<"0\n";
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSBJTkYgMTAwMDAwMDAwNwogCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bGw7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHZlY3RvcjxpbnQ+ID4gdnZpOwp0eXBlZGVmIHBhaXI8aW50LGludD4gaWk7CnR5cGVkZWYgdmVjdG9yPHBhaXI8aW50LGludD4gPiB2aWk7CnR5cGVkZWYgdmVjdG9yPHZlY3RvcjxwYWlyPGludCxpbnQ+ID4gPiB2dmlpOwogCiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQojZGVmaW5lIHRyKHgsaXQpIGZvcihhdXRvIGl0ID0geC5iZWdpbigpO2l0IT14LmVuZCgpOysraXQpCiNkZWZpbmUgc3ooYSkgaW50KChhKS5zaXplKCkpIAojZGVmaW5lIHBiIHB1c2hfYmFjayAKI2RlZmluZSBNUCBtYWtlX3BhaXIKI2RlZmluZSBmcHJlc2VudChjLHgpICgoYykuZmluZCh4KSAhPSAoYykuZW5kKCkpICAvLyBzZXQsbWFwCiNkZWZpbmUgcHJlc2VudChjLHgpIChmaW5kKGFsbChjKSx4KSAhPSAoYykuZW5kKCkpICAvL3ZlY3RvcgojZGVmaW5lIFggZmlyc3QKI2RlZmluZSBZIHNlY29uZAojZGVmaW5lIEZPUihpLGEsYikgZm9yKGludCBpPWE7aTw9YjsrK2kpCiNkZWZpbmUgTkZPUihpLGEsYikgZm9yKGludCBpPWE7aT49YjstLWkpCmxsIGV4cG8oaW50IGJhc2UsIGludCBleHAsIGludCBNT0Q9SU5GKSB7CiAgICBsbCByZXM9MTsKICAgIHdoaWxlKGV4cD4wKSB7CiAgICAgICBpZihleHAmMSkgcmVzPShyZXMqYmFzZSklTU9EOwogICAgICAgYmFzZT0oKGxsKWJhc2UqYmFzZSklTU9EOwogICAgICAgZXhwPWV4cD4+MTsKICAgIH0KICAgIHJldHVybiByZXM7Cn0Kc3RydWN0IG5vZGUKewogICAgY2hhciBjOwogICAgbm9kZSAqbmV4dFsyNl07CiAgICBpbnQgbm87CiAgICB2b2lkIHJlc2V0KGNoYXIgY2gpCiAgICB7CiAgICAgICAgYz1jaDsKICAgICAgICBGT1IoaSwwLDI1KW5leHRbaV09TlVMTDsKICAgICAgICBubz0xOwogICAgfQp9OwppbnQgZmFjWzUwMDFdOwppbnQgaW52Zls1MDAxXTsKaW50IGZbNTAwMV07CmludCBhbnNbNTAwMV07Cm5vZGUgKnJvb3Q7CmNoYXIgc1s1MDAxXTsKaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApOwogICAgZmFjWzBdPTE7aW52ZlswXT0xOwogICAgRk9SKGksMSw1MDAwKQogICAgewogICAgICAgIGZhY1tpXT0oKGxsKWZhY1tpLTFdKmkpJUlORjsKICAgICAgICBpbnZmW2ldPWV4cG8oZmFjW2ldLElORi0yKTsKICAgIH0KICAgIGludCBUOwogICAgY2luPj5UOwogICAgd2hpbGUoVC0tKQogICAgewogICAgICAgIG1lbXNldChmLDAsc2l6ZW9mKGYpKTsKICAgICAgICBpbnQgbixxOwogICAgICAgIGNpbj4+bj4+cTsKICAgICAgICBjaW4+PnM7CiAgICAgICAgcm9vdD0obm9kZSAqKW1hbGxvYyhzaXplb2Yobm9kZSkpOwogICAgICAgIHJvb3QtPnJlc2V0KCckJyk7CiAgICAgICAgbm9kZSAqY3VycjsKICAgICAgICBGT1IoaSwwLG4tMSkKICAgICAgICB7CiAgICAgICAgICAgIGN1cnI9cm9vdDsKICAgICAgICAgICAgRk9SKGosaSxuLTEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgaWYoY3Vyci0+bmV4dFtzW2pdLSdhJ109PU5VTEwpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY3Vyci0+bmV4dFtzW2pdLSdhJ109KG5vZGUgKiltYWxsb2Moc2l6ZW9mKG5vZGUpKTsKICAgICAgICAgICAgICAgICAgICBjdXJyPWN1cnItPm5leHRbc1tqXS0nYSddOwogICAgICAgICAgICAgICAgICAgIGN1cnItPnJlc2V0KHNbal0pOwogICAgICAgICAgICAgICAgICAgICsrZlsxXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2Uge2N1cnI9Y3Vyci0+bmV4dFtzW2pdLSdhJ107LS1mW2N1cnItPm5vXTsoY3Vyci0+bm8pKz0xOysrZltjdXJyLT5ub107fQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGxsIHRlbXA9MDsKICAgICAgICBtZW1zZXQoYW5zLDAsc2l6ZW9mKGFucykpOwogICAgICAgIEZPUihpLDEsbikKICAgICAgICB7CiAgICAgICAgICAgIGlmKGZbaV0pCiAgICAgICAgICAgIEZPUihqLDEsaSkKICAgICAgICAgICAgewogICAgICAgICAgICAgLy89KCgoKCgobGwpZmFjW2ldKihsbClpbnZmW2pdKSVJTkYpKihsbClpbnZmW2ktal0pJUlORikqKGxsKWZbaV0pJUlORjsKICAgICAgICAgICAgIHRlbXA9KGxsKWZhY1tpXSppbnZmW2pdOwogICAgICAgICAgICAgaWYodGVtcD49SU5GKXRlbXAlPUlORjsKICAgICAgICAgICAgIHRlbXAqPWludmZbaS1qXTsKICAgICAgICAgICAgIGlmKHRlbXA+PUlORil0ZW1wJT1JTkY7CiAgICAgICAgICAgICB0ZW1wKj1mW2ldOwogICAgICAgICAgICAgaWYodGVtcD49SU5GKXRlbXAlPUlORjsKICAgICAgICAgICAgIGFuc1tqXSs9dGVtcDsKICAgICAgICAgICAgIGlmKGFuc1tqXT49SU5GKWFuc1tqXS09SU5GOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGludCB4OwogICAgICAgIHdoaWxlKHEtLSkKICAgICAgICB7CiAgICAgICAgICAgIGNpbj4+eDsKICAgICAgICAgICAgaWYoeDw9biljb3V0PDxhbnNbeF08PCJcbiI7ZWxzZSBjb3V0PDwiMFxuIjsKICAgICAgICB9CiAgICB9CglyZXR1cm4gMDsKfSA=