Подсчет палиндромов

Каждый палиндром всегда можно создать из других палиндромов, если один символ также является палиндромом. Например, строку "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$.

Примеры