Таньд хоосон биш жижиг үсэгнүүдээс бүрдсэн $s$ тэмдэгт мөр өгөгдөнө. Энэ тэмдэгт мөрнөөс давхардаагүй хос палиндром дэд тэмдэгт мөрийг олно.

Илүү тодорхой тайлбарлавал, та $(a, b, x, y)$ энэ нь $1 ≤ a ≤ b < x ≤ y ≤ |s|$ байх багцаас дэд тэмдэгт мөрнүүд $s[a... b]$, $s[x... y]$ гэсэн палиндромуудын тоог олно.

Палиндром тэмдэгт мөр гэдэг нь зүүнээс баруун тийш, баруунаас зүүн тийш яг адилхан уншигддаг тэмдэгт мөрийг хэлнэ. Жишээ нь: "$abacaba$", "$z$", "$abba$" эдгээр нь палиндром.

Тэмдэгт мөр $s$ = $s_{1}s_{2}... s_{|s|}$-ийн дэд тэмдэгт мөр нь $s[i... j]$ ($1 ≤ i ≤ j ≤ |s|$) буюу $s_{i}s_{i + 1}... s_{j}$ юм. Жишээ нь: Тэмдэгт мөр $s$ = "$abacaba$" ба дэд тэмдэгт мөр нь $s[2...4]$ буюу "$bac$" юм.

Оролт

Эхний мөрөнд хоосон биш жижиг үсэгнүүдээс бүрдсэн ('$a$'...'$z$') тэмдэг мөр $s$-ийг оруулна. $s$ нь хамгийн ихдээ $2000$ тэмдэгт агуулна.

Гаралт

Нэг тоо хэвлэнэ. Энэ тоо нь $s$-ийн давхцаагүй хос палиндром дэд тэмдэгт мөрийн тоо ширхэг юм.

С++ хэлний оролт гаралтын хэлбэрт %lld буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин cin, cout урсгал эсвэл %I64d хэлбэрийг ашиглавал тохиромжтой.