Palindromlar və supergüclər#5618
Timus Onlayn Hakimində adında "palindrom" sözü olan yeddi problemi həll etdikdən sonra Mişa qeyri-adi bir qabiliyyət qazandı. İndi, o, bir sözü oxuduqda, həmin sözün unikal və boş olmayan palindrom alt sətirlərinin sayını düşünərək hesablaya bilir.
Dima Mişanın səhv etmədiyinə əmin olmaq istəyir. Bunun üçün o, sözə bir-bir s_1, \ldots, s_n hərfini əlavə edir və hər hərfdən sonra Mişadan hazırkı sözün neçə fərqli boş olmayan palindrom alt sətirləri ehtiva etdiyini deməsini xahiş edir. Mişa həqiqətən heç vaxt səhv etmirsə, hansı ədədi deyəcək?
Yeganə sətirdə s_1 \ldots s_n sətri verilir, burada s_i kiçik latın hərfləridir (1 \le n \le 10^5).
ədəd çıxarın, bir boşluqla ayırın. -ci ədəd s_1 \ldots s_i prefiksinin fərqli boş olmayan palindrom alt sətirlərinin sayına bərabər olmalıdır.
Nümunə 1