#include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 /********************************************************************/

 const int maxn = 1e6+;

 char s[maxn];

 int Next[maxn];

 int sum[maxn];

 const int mod = ;

 int main(){

     int t; t = read();

     while(t--){

         int n; n = read();

         scanf("%s", s+);

         //int len = strlen(s+1);

         Next[] = ;;

         int k = ;

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

             while(k >  && s[k+] != s[i]){

                 k = Next[k];

             }

             if(s[k+] == s[i])

                 k++;

             Next[i] = k;

         }

         int ans = ;

         memset(sum, , sizeof(sum));

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

             sum[i] = (sum[Next[i]] + )%mod;

             ans = (ans + sum[i])%mod;

         }

         cout << ans << endl;

     }

     return ;

 }