Palindrome Partition

문자열 s가 주어질 때, 분할에 k개의 부분 문자열 (p1, p2, p3, ..., pk)이 있다면 모든 i (1 ≤ i ≤ k)에 대해 pi = pk - i + 1이고 k가 짝수가 되도록 s를 부분 문자열들로 분할하는 방법의 수를 구한다.

방법의 수가 클 수 있으므로, 이를 109 + 7로 나눈 나머지를 출력한다.

입력의 유일한 줄에는 소문자 라틴 문자로 이루어진 짝수 길이의 문자열 s (2 ≤ |s| ≤ 106)가 주어진다.

문자열을 분할하는 방법의 수를 109 + 7로 나눈 나머지를 정수 하나로 출력한다.

첫 번째 경우에 문자열을 분할하는 유일한 방법은 ab|cd|cd|ab이다.

두 번째 경우에 문자열은 ab|b|ab|ab|ab|ab|b|ab, ab|b|abab|abab|b|ab 또는 abbab|ab|ab|abbab으로 분할할 수 있다.