Problem: Given a string s, find the number of ways to split s to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk - i + 1 for all i (1 ≤ i ≤ k) and k is even.

Since the number of ways can be large, print it modulo 109 + 7.

Input

The only line of input contains a string s (2 ≤ |s| ≤ 106) of even length consisting of lowercase Latin letters. 

Output

Print one integer, the number of ways of partitioning the string modulo 109 + 7.

Examples

Input

abcdcdab


Output

1

Input

abbababababbab


Output

3

Note

In the first case, the only way to partition the string is ab|cd|cd|ab.

In the second case, the string can be partitioned as ab|b|ab|ab|ab|ab|b|ab or ab|b|abab|abab|b|ab or abbab|ab|ab|abbab.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  int data = 0, m = 1;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') {
    m = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    data = (data << 1) + (data << 3) + (ch ^ 48);
    ch = getchar();
  }
  return (m) ? data : -data;
}
int fail[1000005], up[1000005], len[1000005], ch[1000005][26], f[1000005],
    g[1000005], p, oo, n, m, cl, last, Delta[1000005];
char s[1000005], str[1000005];
inline void Init() {
  fail[0] = fail[1] = ++oo;
  len[1] = -1;
  return;
}
inline void Extend(int c, int pos) {
  p = last;
  while (s[pos] != s[pos - len[p] - 1]) p = fail[p];
  if (!ch[p][c]) {
    cl = fail[p];
    ++oo;
    while (s[pos] != s[pos - len[cl] - 1]) cl = fail[cl];
    cl = ch[cl][c];
    fail[oo] = cl;
    ch[p][c] = oo;
    len[oo] = len[p] + 2;
  }
  p = ch[p][c];
  last = p;
  Delta[p] = len[p] - len[fail[p]];
  up[p] = (Delta[p] == Delta[fail[p]]) ? up[fail[p]] : p;
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  for (int i = 1; i <= n / 2; i++) s[2 * i - 1] = str[i];
  for (int i = n; i > n / 2; i--) s[2 * (n - i + 1)] = str[i];
  Init();
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    Extend(s[i] - 'a', i);
    f[i] = 0;
    for (int x = last; x > 1; x = fail[p]) {
      p = up[x];
      g[x] = (x ^ p) ? g[fail[x]] : 0;
      g[x] = (g[x] + f[i - len[p]]) % 1000000007;
      if (i % 2 == 0) f[i] = (f[i] + g[x]) % 1000000007;
    }
  }
  cout << f[n] << endl;
  return 0;
}