Palindromik sıra (Çətin)#5940
Ksyuşanın s adlı bir sırası var. O, bu sıranın hərflərinin yerini dəyişərək müxtəlif kombinasiyalar yaratmağa çalışır.
Ksyuşa indi maraqlanır ki, bu hərflərin yerini dəyişməklə neçə fərqli palindrom yarada bilər.
Bir sıra palindrom adlanır, əgər o, həm soldan sağa, həm də sağdan sola eyni şəkildə oxunursa. Məsələn, "ded" bir palindromdur.
Birinci sətirdə s (1 ≤ |s| ≤ 10^6) sırası verilib. Bu sıra yalnız kiçik latın hərflərindən ibarətdir.
Yeganə tam ədəd çıxarın — Ksyuşanın sıranın hərflərini yerini dəyişməklə əldə edə biləcəyi müxtəlif palindromların sayı. Cavab çox böyük ola biləcəyi üçün onu 1000000000 (10^9) modulu ilə çıxarın.
Nümunə 1