Distinct Substring Queries

Time limit2sMemory limit512 MB

Summary

Maintain a string under push-back and pop-front operations, reporting the number of distinct substrings after each of up to a million queries.

Level: Hard9 of 10
Topics: String, String matching, Sorting, Trie
Solved: No attempts yet

Problem

The string $S$ is empty at the start. Write a program that performs the following two kinds of queries in order.

+ c: append the character $c$ to the end of $S$ . $c$ is a lowercase English letter.
-: remove the first character of $S$ .

Right after each query, the length of $S$ is always positive.

After each query, you must find the number of distinct substrings of $S$ at that moment.

Input

The first line contains the number of queries $Q$ ( $1 \le Q \le 1\,000\,000$ ).

Each of the next $Q$ lines contains one query.

Output

For each query, find the number of distinct substrings of $S$ right after that query. Print the sum of these numbers over all queries, modulo $1\,000\,000\,007$ .

Note

In the first example, the state after each query is as follows.

$S$ = a. It has 1 distinct substring: a.
$S$ = ab. It has 3 distinct substrings: a, b, ab.
$S$ = aba. It has 5 distinct substrings: a, b, ab, ba, aba.
$S$ = abaa. It has 8 distinct substrings: a, b, ab, ba, aa, aba, baa, abaa.
$S$ = baa. It has 5 distinct substrings: a, b, ba, aa, baa.
$S$ = aa. It has 2 distinct substrings: a, aa.
$S$ = a. It has 1 distinct substring: a.
$S$ = aa. It has 2 distinct substrings: a, aa.

The sum is $1 + 3 + 5 + 8 + 5 + 2 + 1 + 2 = 27$ , and $27 \bmod 1\,000\,000\,007 = 27$ , so the answer is 27.

Examples1

Example 1
Input
```
8
+ a
+ b
+ a
+ a
-
-
-
+ a
```
Expected output
```
27
```