Підрахунок паліндромів

Кожен паліндром можна скласти з інших паліндромів, враховуючи, що один символ також є паліндромом. Наприклад, рядок "bobseesanna" можна скласти кількома способами:

• bobseesanna = bob + sees + anna

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

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

• ...

Знайдіть кількість різних способів, якими можна скласти рядок $s$ з паліндромів.

Вхідні дані

Один рядок $s$ довжиною не більше $1000$.

Вихідні дані

Виведіть кількість різних способів, якими можна скласти рядок $s$ з паліндромів. Відповідь виведіть за модулем $10^9+7$.

Приклади