1 #include <cstdio> 2 #include <cstring> 3  4 const int maxn = 200000 + 10; 5 const int MOD = 10007; 6 char s[maxn]; 7 int next[maxn], l; 8  9 void get_next()10 {11     int k = -1, j = 0;12     next[0] = -1;13     while(j < l)14     {15         if(k == -1 || s[k] == s[j])16         {17             k++;18             j++;19             next[j] = k;20         }21         else k = next[k];22     }23 }24 25 int main(void)26 {27     int T;28     scanf("%d", &T);29     while(T--)30     {31         scanf("%d", &l);32         scanf("%s", s);33         get_next();34         35         int ans = 0;36         for(int j = 0; j < l; ++j)37             if(next[j] > 0 && next[j] + 1 != next[j+1])38                 ans = (ans + next[j]) % MOD;39         ans = (ans + l + next[l]) % MOD;40         printf("%d\n", ans);41     }42     43     return 0;44 }