Cho xâu \(S\), Tèo muốn đếm số lượng các xâu con phân biệt của \(S\). Xâu con là một đoạn ký tự liên tiếp trong \(S\). Hãy dùng hash xâu để giải quyết bài toán hiệu quả.

Định dạng đầu vào

• Một dòng duy nhất chứa xâu \(S\) (\(1 \le |S| \le 2000\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượng xâu con phân biệt.

Ví dụ

Input:

ababa

Output:

9

Giải thích: Các xâu con phân biệt: a, b, ab, ba, aba, bab, abab, baba, ababa.

Ràng buộc

• 50% số điểm: \(|S| \le 500\).
• 50% số điểm còn lại: \(|S| \le 2000\).