Palindromların sayılması

Hər bir palindrom digər palindromlardan ibarət ola bilər, əgər bir simvol belə palindromdursa. Məsələn, "bobseesanna" sətirini bir neçə fərqli şəkildə yaratmaq mümkündür:

• bobseesanna = bob + sees + anna

• bobseesanna = bob + s + ee + s + anna

• bobseesanna = b + o + b + sees + a + n + n + a

• ...

Palindromlardan istifadə edərək $s$ sətirini yaratmağın müxtəlif yollarının sayını tapın.

Giriş verilənləri

Uzunluğu 1000-dən çox olmayan bir sətir $s$ verilir.

Çıxış verilənləri

$s$ sətirini palindromlardan yaratmağın müxtəlif yollarının sayını çıxarın. Cavabı $10^9+7$ moduluna görə verin.

Nümunələr