Bạn được cho một xâu có độ dài \(n\), và phải đếm số lượng xâu con khác nhau trong xâu đó.

Input

• Dòng đầu tiên và duy nhất của input gồm 1 xâu có độ dài \(n\), gồm các kí tự in thường a - z.

Output

• In ra 1 số nguyên duy nhất là số lượng xâu con khác nhau của xâu được cho.

Constraints

• \(1 \leq n \leq 10^5\)

Example

Note

Các xâu con khác nhau của xâu abaa là a, b, aa, ab, ba, aba, baa và abaa.