Problem Background

After being overwhelmed at NOI, the novice YJQ decided to study strings and encountered the following problem:

Problem Description

Given a string of length $n$, find the number of distinct substrings.

We define two substrings as distinct if and only if they have different lengths or have the same length but differ at any position.

A substring is defined as a contiguous sequence of characters in the original string.

Input Format

The first line contains an integer $n$.

The next line contains $n$ characters representing the given string.

Output Format

Output a single integer representing the number of distinct substrings.

Sample Input and Output

Sample Input #1

5
aabaa

Sample Output #1

11

Sample Input #2

3
aba

Sample Output #2

5

Notes/Hints

Please use 64-bit integers for output.

Data Size and Constraints

• For $30\%$ of the data, $n \leq 1000$.
• For $100\%$ of the data, $1 \leq n \leq 10^5$, and the string contains only lowercase English letters.

见题面 Input 部分

见题面 Output 部分