Fun with strings
Tag(s):

## LCP, Medium-Hard, Suffix Arrays, Suffix Trees

Problem
Editorial
Analytics

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

• $T \le 5$
• $S$ consists of lowercase english alphabets only.
• (25 points) : $n \le 10^3$
• (75 points) : $n \le 10^5$
SAMPLE INPUT
2
2
ab
3
zzz
SAMPLE OUTPUT
6
46
Explanation

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$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Basic Programming > Implementation
• Data Structures > Arrays
• Math > Number Theory