Để kịp hoàn thiện sân bay quốc tế trước khi đón một nguyên thủ quốc gia, người ta cần trang trí hai phòng VIP (Phòng trái và Phòng phải) bằng hai tấm thảm giống hệt nhau để tránh rắc rối ngoại giao.

Cuộn thảm ban đầu được khâu từ ~n~ tấm thổ cẩm có độ dài bằng nhau. Mỗi tấm thuộc một trong ~26~ loại và được ký hiệu bởi 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~ (chỉ gồm chữ thường).

Người ta sẽ tháo chỉ khâu ở 2 chỗ, lấy đoạn giữa ~s[i..j]~ đem lót Phòng trái. Phần thảm còn lại gồm:

• đoạn bên trái: ~s[1..i-1]~
• đoạn bên phải: ~s[j+1..n]~

Để làm thảm cho Phòng phải, họ sẽ:

• cắt ra một xâu con liên tiếp ~s[i_1..j_1]~ từ đoạn trái,
• cắt ra một xâu con liên tiếp ~s[i_2..j_2]~ từ đoạn phải,
• rồi khâu hai xâu con này theo đúng thứ tự trái → phải, thu được xâu ~s[i_1..j_1] + s[i_2..j_2]~.

Tấm thảm mới phải giống hệt tấm đã mang vào Phòng trái, tức là bằng đúng ~s[i..j]~.

Yêu cầu

Đếm số 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 của ~s~ từ vị trí ~u~ đến ~v~ (đánh số từ ~1~).

Dữ liệu

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

Kết quả

In ra một số nguyên — số cách chọn đoạn thảm ~s[i..j]~ để lót Phòng trái sao cho có thể tạo ra tấm thảm giống hệt cho Phòng phải theo quy tắc trên.

Ví dụ

Ví dụ 1

Input

abababb

Output

3

Giải thích

Ví dụ 1

Với ~s = \text{abababb}~ (đánh số từ ~1~), có đúng ~3~ cách chọn ~[i..j]~ thỏa mãn:

1. ~i=3, j=4~: ~s[3..4]=\text{ab}~ Chọn ~s[i_1..j_1]=s[1..1]=\text{a}~, ~s[i_2..j_2]=s[5..5]=\text{b}~ ⇒ "a" + "b" = "ab".

2. ~i=4, j=6~: ~s[4..6]=\text{bab}~ Chọn ~s[i_1..j_1]=s[2..3]=\text{ba}~, ~s[i_2..j_2]=s[7..7]=\text{b}~ ⇒ "ba" + "b" = "bab".

3. ~i=5, j=6~: ~s[5..6]=\text{ab}~ Chọn ~s[i_1..j_1]=s[1..1]=\text{a}~, ~s[i_2..j_2]=s[7..7]=\text{b}~ ⇒ "a" + "b" = "ab".

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

• ~n = |s| \le 10^5~
• ~s~ chỉ gồm chữ cái Latin thường
• Cặp ~i, j~ phải thỏa ~1 < i \le j < n~
• Các đoạn ghép phải lấy từ hai phía còn lại và đều không rỗng: ~i_1 \le j_1~, ~i_2 \le j_2~