Distinct Substrings

Given a string s, return the number of distinct non-empty substrings.

Constraints

• 0 ≤ n ≤ 1,000 where n is the length of s

https://binarysearch.com/problems/Distinct-Substrings

Examples

Example 1

Input

• s = aaab

Output

• answer = 7

Explanation

We have the following distinct substrings:

• "a"
• "aa"
• "aaa"
• "aaab"
• "aab"
• "ab"
• "b"

Solution