Cho xâu ~S = S_1 S_2...S_i...S_j...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_1 S_2...S_j...S_i...S_n~ . Yêu cầu: Tính số lượng các xâu khác nhau nằm trong tập hợp ~M~.

Dữ liệu

Nhập từ tệp CAU4.INP:

Gồm một dòng là xâu ~S~ (độ dài không quá ~2 \times 10^5~).

Kết quả ra

Xuất ra tệp CAU4.OUT:

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

Ràng buộc

• Subtask ~1(50\%):~ Độ dài xâu ~S~ không quá ~100~.
• Subtask ~2(50\%):~ Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào

tent

Kết quả ra

6

Giải thích

Tập ~M~ gồm: tent, etnt, nett, tnet, ttne, tetn.