Cần hoàn thiện gấp sân bay quốc tế để kịp đón một nguyên thủ quốc gia tới thăm. Theo thiết kế có 2 phòng VIP: Phòng trái và Phòng phải, hai phòng phải được trang trí nội thất giống nhau.

Thảm trải sàn được chở tới là một cuộn được khâu từ ~n~ tấm thổ cẩm có độ dài như nhau. Mỗi tấm thuộc một trong ~26~ loại và được ký hiệu bằng một chữ cái latin thường. Vì vậy cuộn thảm được mô tả bởi xâu ~s~ độ dài ~n~.

Do thời gian gấp, người ta quyết định:

• Tháo chỉ khâu ở 2 chỗ, lấy đoạn giữa ~s[i..j]~ để lót Phòng trái.
• Trong lúc đó, từ phần còn lại bên trái (~s[1..i-1]~) có thể tháo chỉ ở ~0,1~ hoặc ~2~ chỗ rồi bỏ đi phần đầu/cuối để lấy ra một xâu con liên tiếp ~s[i_1..j_1]~.
• Tương tự, từ phần còn lại bên phải (~s[j+1..n]~) lấy ra một xâu con liên tiếp ~s[i_2..j_2]~.
• Sau đó khâu hai xâu con này lại theo đúng thứ tự trái–phải ban đầu để tạo tấm thảm cho Phòng phải.

Tấm thảm mới cho Phòng phải phải giống hệt tấm đã mang vào Phòng trái.

Yêu cầu

Đếm số cách chọn cặp chỉ số ~i, j~ (~1 < i \le j < n~) sao cho tồn tại các chỉ số ~i_1, j_1, i_2, j_2~ thỏa mãn:

• ~1 \le i_1 \le j_1 < i~
• ~j < i_2 \le j_2 \le n~
• ~s[i..j] = s[i_1..j_1] + s[i_2..j_2]~

Trong đó ~s[u..v]~ là xâu con liên tiếp từ vị trí ~u~ đến ~v~, và dấu ~+~ là phép nối xâu.

Dữ liệu

Một dòng chứa xâu ~s~ chỉ gồm chữ cái latin thường, với ~1 \le |s| \le 10^5~.

Kết quả

In ra một số nguyên: số lượng cặp ~i, j~ thỏa mãn yêu cầu.

Ví dụ

Ví dụ 1

Input

abababb

Output

3

Giải thích

Ví dụ 1

Với ~s =~ abababb có 3 cách chọn đoạn giữa:

• ~i=3, j=4~, ~s[3..4]=~ab. Có thể tách ab = a + b, trong đó a xuất hiện ở phần trái ab, và b xuất hiện ở phần phải abb.
• ~i=4, j=6~, ~s[4..6]=~bab. Có thể tách bab = ba + b, trong đó ba xuất hiện ở phần trái aba, và b xuất hiện ở phần phải b.
• ~i=5, j=6~, ~s[5..6]=~ab tương tự trường hợp đầu.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le |s| \le 10^5~
• ~s~ chỉ chứa ký tự latin thường.