Distinct Substring Count of a Genome Strand

Given a string s, count how many distinct non-empty substrings it has. A substring is any contiguous block of characters; two substrings are the same only if they are equal as strings, regardless of where they occur.

One classic method inserts every suffix of s into a trie; the number of trie nodes below the root then equals the number of distinct substrings. The string consists of lowercase English letters only.

Input format

Line 1: the string s.

Output format

A single integer: the number of distinct non-empty substrings of s.

Constraints

• 1 <= length of s <= 40
• s consists of lowercase English letters.