Palindromik sıra (Çətin)

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.

Giriş verilənləri

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.

Çıxış verilənləri

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ələr