题目描述

众所周知，AekdyCoin在字符串问题和数论问题上都很擅长。当给定字符串s时，我们可以写出该字符串的所有非空前缀。

例如：s：“abab”

前缀是：“a”、“ab”、“aba”、“abab”。

对于每个前缀，我们可以计算它在s中匹配的次数。因此我们可以看到前缀“a”匹配两次，“ab”匹配两次，“aba”匹配一次，“abab”匹配一次。现在你被要求计算所有前缀匹配时间的总和。对于“abab”，是2 + 2 + 1 + 1 = 6。

答案可能很大，因此输出mod 10007的答案。

输入格式

第一行是一个整数T，表示测试用例的数量。对于每个案例，第一行是一个整数n（1 <= n <= 200000），即字符串s的长度。后面有一行，给出字符串s。字符串中的字符均为小写字母。

输出格式

对于每个情况，只输出一个数字：即 mod 10007 中所有前缀的匹配时间之和。

1
4
abab

6