Distinct Substrings

Given a string s consisting of only lowercase English letters, your task is to compute the number of distinct substrings in s. A substring is defined as any contiguous sequence of characters within the string. Two substrings are considered different if their contents differ.

The input string will have a length n satisfying \(1 \leq n \leq 10^6\). Although the constraint allows large inputs, the intended solutions for this challenge need only handle moderately sized inputs based on the provided test cases.

Note: In this problem, the empty substring is not counted.

inputFormat

The input consists of a single line containing the string s composed solely of lowercase English letters.

For example:

abcd

outputFormat

Output a single integer representing the number of distinct substrings of the input string.

For example, for the input abcd, the correct output is 10.

abcd

10