금고와 명 윅

저번에 조직의 상하관계를 모르는 명 윅은 조직의 강함의 최소보다 자신의 강함이 더 크면 조직을 털 수 있을 것이라고 생각했었다. 

드디어 명 윅은 조직이 가질 수 있는 강함을 계산했다! 자신의 강함이 조직의 강함의 최솟값보다 크다는 것을 알게된 명 윅은 조직의 금고를 털기로 하였다. 조직이 여행을 간 날에 명 윅은 금고에 침입하는 것을 성공하게 된다. 금고에 침입한 명 윅은 여행에서 돌아오는 날짜와 조직의 상하관계를 알게 되었다. 조직의 강함은 실제로 자신의 강함보다 컸다. 이를 안 명 윅은 여행에서 돌아오기 전에 금고를 열 수 있다면 금고를 열기로 하였다. 명 윅은 주변의 금고에서 암호를 찾게 되었다. 이는 다음과 같다. 

"아래 문자열 S를 k(k는 짝수)개의 부분 문자열$(p_1, p_2, ... p_k)$로 나누어 $p_i = p_{k-i+1} (1 \leq i \leq k)$ 만들라."

문제를 읽어본 명 윅은 이 문제의 답이 하나가 아니라는 것을 깨달았다. 그래서 명 윅은 모든 답을 일일이 넣어볼 예정이다. 명 윅은 이 일을 조직원들이 여행에서 돌아오기 전에 끝내야 하므로 모든 가짓수를 구해 미리 시간을 예상해보려고 한다. 그런데 명 윅은 어려워서 이를 하지 못한다. 여러분들이 이를 도와주자.

Input

첫째 줄에 문자열 $S\ (2 \leq |S| \leq 1000000,\ |S|는 짝수)$가 주어진다.

Output

조건을 만족하는 개수를 $10^9+7$로 나눈 나머지를 첫째 줄에 출력하여라.

IOExample

입력1
abcdcdab

출력1
1

입력2
abbababababbab

출력2
3

예제 설명
첫 번째 예제는 ab|cd|cd|ab 1가지만 가능하다.

두 번째 예제는 ab|b|ab|ab|ab|ab|b|ab, ab|b|abab|abab|b|ab, abbab|ab|ab|abbab 3가지가 가능하다.