Каждый палиндром всегда можно создать из других палиндромов, если один символ также является палиндромом. Например, строку "bobseesanna" можно создать несколькими способами: \begin{itemize} \item bobseesanna = bob + sees + anna \item bobseesanna = bob + s + ee + s + anna \item bobseesanna = b + o + b + sees + a + n + n + a \item ... \end{itemize} Найдите количество различных способов, которыми из палиндромов можно создать строку $s$. \InputFile Одна строка $s$ длины не более $1000$. \OutputFile Выведите количество различных способов, которыми можно создать строку $s$ из палиндромов. Ответ выведите по модулю $10^9 + 7$.