CA loves strings, especially the substrings.
Now CA has a string $S$ which consists of $N$ digits. However, she split this string into two non-empty strings. Specifically, CA spilt the string into $S1$ and $S2$ two substrings at the middle of ith character and (i+1)th. Now, she wonders that there are how many non-empty strings are substring of $S1$ or $S2$ for each $i$.
First line contains $T$ denoting the number of testcases.
$T$ testcases follow. Each testcase contains a integer in the first line, denoting $N$, the length of string $S$. The second line is a string whose length is $N$.
$1 \le T \le 10,~2 \le N \le 200000$
For each testcase, you need output $1$ line.
Let $F_j$ represent the answer when $i = j$ in this testcase, you need to output $\sum_{j=1}^{N-1} F_j \times 100013^{N-j-1}~mod~(10^9+7)$