问题描述

很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的长度为 N 的 DNA 序列（小兔子是外星生物，DNA 序列由小写英文字母构成），记为 S。

然后我们每次选择 S 的前 $K$ 个字符组成的子串，记为 P，统计 P 在 S 中在多少个不同位置出现，记录这个数量为 $A_K$ 。

现在需要统计 $\sum\limits_{K=1}^{N} A_K$。

你能完成这个任务吗？答案可能很大，你只需要输出答案 mod 10007 的值。

多组数据。

输入格式

第一行：一个整数 T，表示数据组数。

对于每组数据：

• 第1行：一个数字 N，表示 S 的长度。
• 第2行：一个字符串 S，全部由小写英文字母组成。

输出格式

对于每组数据，输出一行表示结果。

输入样例

1
4
abab

输出样例

6

数据范围

20个测试点（80分）：1 ≤ T ≤ 20, 1 ≤ N ≤ 200000

1个测试点（20分）：T = 1, 1 ≤ N ≤ 20000000