#include<stdio.h>

 #include<string.h>

 const int MAXN=;

 const int MOD=;

 int dp[MAXN];

 char str[MAXN];

 int next[MAXN];

 void getNext(char *p)

 {

     int j,k;

     j=;

     k=-;

     next[]=-;

     int len=strlen(p);

     while(j<len)

     {

         if(k==-||p[j]==p[k])

         {

             j++;

             k++;

             next[j]=k;

         }

         else k=next[k];

     }

 }

 int main()

 {

     int T;

     int n;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         scanf("%s",&str);

         getNext(str);

         dp[]=;

         int ans=;

         for(int i=;i<=n;i++)

         {

             dp[i]=dp[next[i]]+;

             dp[i]%=MOD;

             ans+=dp[i];

             ans%=MOD;

         }

         printf("%d\n",ans);

     }

     return ;

 }