SOLVE
LATER
You are given a string $$S = S_0S_1 \cdots S_{n-1}$$ of length $$n$$.
Find the sum of length of LCP(Longest Common Prefix) over all the $$ \frac{n^2(n+1)^2}{4} $$ ordered pairs of its substrings.
Formally, say the substring of $$S$$ starting at index $$i$$ and ending at index $$j$$ is represented by $$S_{ij}$$, and let $$L(A,B)$$ represent the length of LCP of strings A and B.
Then compute the value of :
$$$ \displaystyle \large \sum_{i=0}^{n-1} \sum_{j=i}^{n-1} \sum_{k=0}^{n-1} \sum_{l=k}^{n-1} L(S_{ij},S_{kl}) $$$
As this value may be very large, print it modulo 10^9 + 7
Input
The first line contains $$T$$, the number of test cases. It is followed by $$2T$$ lines, describing the strings in the testcases . Each string is described by two lines.
The first line contains $$n$$, length of the string $$S$$.
Second line contains the string $$S$$ consisting of lowercase english alphabets only.
Output
Print $$T$$ lines containing the sum of lengths of lcp over all ordered pairs of substrings of $$S$$ modulo 10^9+7 for the $$T$$ testcases, each on a new line.
Constraints
When $$S=ab$$, the answer equals
$$L(a,a)+L(a,ab) + L(a,b) + L(ab,a)+L(ab,ab)+L(ab,b)+L(b,a)+L(b,ab)+L(b,b)$$
$$ = 1+1+0+1+2+0+0+0+1 = 6$$