问题描述
CA喜欢字符串，尤其喜欢子串。
现在他有一个长度为 $N$ 的由数字组成的字符串 $S$，然而他不小心把这个字符串分成了非空的两部分。
具体的，CA在第 $i~ (0 < i < n)$ 个字符和第 $i+1$ 个字符的中间，将这个字符串分成了 $S1,S2$ 两个字符串。
他想知道对于所有不同的 $i$，有多少个非空字符串是 $S1$ 或 $S2$ 的子串。
输入描述
第一行 $T$，表示有 $T$ 组数据。
接下来 $T$ 组数据，每组数据第一行一个整数 $N$，表示CA原本的字符串的长度，接下来一行一个长度为 $N$ 的由数字组成的字符串。
$1 \le T \le 10,~2 \le N \le 200000$
输出描述
对于每组数据输出1行,一个整数表示该组数据所有输出的hash值，我们采用如此的Hash方法：
令当$i=j$的答案为$F_j$,请输出$\sum_{j=1}^{N-1} F_j \times 100013^{N-j-1}~mod~(10^9+7)$
输入样例
2
2
00
4
0101
输出样例
1
13300539
Hint
对于第二组数据，当 $i=1$ 时，分成的两个串 $S1$ 为”0”，$S2$ 为”101”，满足条件的串有"0","1","10","01","101"
