const maxn=;

       mo=;

 var    a,f,rig:array[..maxn] of dword;

     nt:array[..maxn,'a'..'z'] of longint;

     last,sum,i:dword;

     s:ansistring;

     eg:array[..maxn*] of record nt,v:dword; end;

     lt:array[..maxn] of dword;

     el:dword;

     time:array[..maxn] of qword;

     T,j,TT:dword;

     ans:array[..maxn] of qword;

     C:array[-..,-..] of qword;

     du,g:array[..maxn] of longint;

     b:array[..] of longint;

 procedure SAM_init; inline;

 begin

     fillchar(f,sizeof(f),);

     fillchar(nt,sizeof(nt),);

     fillchar(a,sizeof(a),);

     fillchar(rig,sizeof(rig),);

     el:=;

     fillchar(lt,sizeof(lt),);

     fillchar(ans,sizeof(ans),);

     fillchar(du,sizeof(du),);

     fillchar(g,sizeof(g),);

     last:=; sum:=;

 end;

 procedure SAM_ins(ch:char); inline;

 var next,p,np,q,nq:longint;

 begin

     inc(sum); p:=last; np:=sum; a[np]:=a[p]+; last:=np;  rig[np]:=;

     while (p<>-) and (nt[p][ch]=-) do begin nt[p][ch]:=np; p:=f[p]; end;

     if p=- then f[np]:= else

     begin

         q:=nt[p][ch];

         if a[p]+=a[q] then f[np]:=q else

         begin

             inc(sum); nq:=sum; a[nq]:=a[p]+;

             nt[nq]:=nt[q];

             f[nq]:=f[q]; f[q]:=nq; f[np]:=nq;

             while (p<>-) and (nt[p][ch]=q) do begin nt[p][ch]:=nq; p:=f[p]; end;

         end;

     end;

 end;

 procedure SAM_visit1; inline;

 var i,l,r:longint;

     c:char;

 begin

     for i:= to sum do

         for c:='a' to 'z' do

             if nt[i][c]<>- then inc(du[nt[i][c]]);

     l:=; r:=; b[]:=; g[]:=;

     while l<=r do

     begin

         for c:='a' to 'z' do

             if nt[b[l]][c]<>- then

             begin

                 dec(du[nt[b[l]][c]]);

                 inc(g[nt[b[l]][c]],g[b[l]]);

                 if du[nt[b[l]][c]]= then

                 begin

                     inc(r);

                     b[r]:=nt[b[l]][c];

                 end;

             end;

         inc(l);

     end;

     for i:= to sum do inc(time[rig[i]],g[i]);

 end;

 procedure dfs(u:dword);

 var i:dword;

 begin

     i:=lt[u];

     while i<> do

     begin

         dfs(eg[i].v);

         rig[u]:=rig[u]+rig[eg[i].v];

         i:=eg[i].nt;

     end;

 end;

 procedure add(u,v:dword); inline;

 begin

     inc(el);

     eg[el].v:=v;

     eg[el].nt:=lt[u];

     lt[u]:=el;

 end;

 procedure SAM_rig; inline;

 begin

     el:=;

     fillchar(lt,sizeof(lt),);

     for i:= to sum do add(f[i],i);

     dfs();

 end;

 procedure main; inline;

 var n,q,i,j:dword;

     cnt:qword;

 begin

     if T<> then

     begin

         fillchar(time,sizeof(time),);

         SAM_init;

     end;

     readln(n,q);

     readln(s);

     SAM_init;

     for i:= to n do SAM_ins(s[i]);

     SAM_rig;

     SAM_visit1;

     for i:= to n do

         for j:=i to n do ans[i]:=(ans[i]+C[j,i]*time[j]) mod mo;

     for i:= to q do

     begin

         readln(j);

         if j>n then writeln() else

         writeln(ans[j]);

     end;

 end;

 begin

     C[,]:=;

     for i:= to  do

         for j:= to i do

         begin

             C[i,j]:=(c[i-,j-]+c[i-,j]);

             if C[i,j]>=mo then C[i,j]:=C[i,j]-mo;

         end;

     readln(T);

     for TT:= to T do main;

 end.