Biến đổi xâu

Cho xâu \(S = S_1 S_2 \dots S_n\) \((1 \le i \le j \le n)\) chỉ gồm các chữ cái tiếng Anh in thường.

Phép đảo ngược xâu là phép biến đổi xâu ban đầu thành một xâu mới có thứ tự các kí tự ngược lại so với xâu ban đầu. Ví dụ: “ten” đảo ngược thành “net”, “time” đảo ngược thành “emit”.

Mỗi lần áp dụng phép đảo ngược xâu trên một xâu con liên tiếp từ vị trí \(i\) đến vị trí \(j\) của xâu \(S\) sẽ thu được xâu

Gọi \(M\) là tập hợp các xâu \(S'\).

Yêu cầu. Tính số lượng xâu khác nhau trong tập hợp \(M\).

Input

Vào từ tệp văn bản gồm một dòng là xâu \(S\) \((1 \le |S| \le 2 \cdot 10^5)\).

Output

Ghi ra một số nguyên là kết quả của bài toán.

Input

%
tent

Output

%
6

Notes

Với ví dụ trên, tập \(M\) gồm:

Scoring

• (50%) \(1 \le n \le 100\);
• (50%) \(100 < n \le 2 \cdot 10^5\).