Description

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

We define two substrings to be different if and only if either their lengths are different, or their lengths are the same but there exists at least one position where they differ.

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

Input Format

The first line contains an integer $n$.

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

Output Format

Output a single integer in one line, representing the number of distinct substrings.

5
aabaa

11

3
aba

5

Hint

Please use a 64-bit integer for the output.

Constraints

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

Translated by ChatGPT 5