Number of distinct substrings 2

Given a string $S$, write a program that counts how many distinct substrings $S$ has.

A substring is a contiguous piece cut out of $S$, and its length must be at least 1.

For example, if $S$ is ababc, the substrings are a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc, and 12 of them are distinct.

The first line contains the string $S$. $S$ consists of lowercase letters only, and its length is at least 1 and at most 1,000,000.

Print the number of distinct substrings of $S$ on the first line.