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;
const int N = 1e6 + 5, MOD = 1e9 + 7, P = 26;
inline int add(int a, const int &b) {
  if ((a += b) >= MOD) a -= MOD;
  return a;
}
inline int sub(int a, const int &b) {
  if ((a -= b) < 0) a += MOD;
  return a;
}
inline int mul(const int &a, const int &b) { return 1ll * a * b % MOD; }
inline int &inc(int &a, const int &b) { return a = add(a, b); }
inline int &dec(int &a, const int &b) { return a = sub(a, b); }
inline int &pro(int &a, const int &b) { return a = mul(a, b); }
inline int qpow(int a, int b) {
  int c = 1;
  for (; b; b >>= 1, pro(a, a))
    if (b & 1) pro(c, a);
  return c;
}
int n, fa[N], anc[N], len[N], a[N], lst, ptr, ch[N][P], f[N], g[N], dif[N];
char s[N];
inline void init() {
  fa[0] = fa[1] = lst = ptr = 1;
  len[1] = -1;
  anc[0] = 1;
}
inline void append(int n) {
  int c = a[n], p = lst;
  while (a[n - len[p] - 1] ^ a[n]) p = fa[p];
  if (!ch[p][c]) {
    int q = fa[p];
    while (a[n - len[q] - 1] ^ a[n]) q = fa[q];
    fa[++ptr] = ch[q][c];
    ch[p][c] = ptr;
    len[ptr] = len[p] + 2;
    dif[ptr] = len[ptr] - len[fa[ptr]];
    anc[ptr] = dif[ptr] == dif[fa[ptr]] ? anc[fa[ptr]] : fa[ptr];
  }
  lst = ch[p][c];
}
int main() {
  init();
  scanf("%s", s + 1);
  n = strlen(s + 1);
  if (n & 1) return puts("0"), 0;
  for (int i = 1; i <= n; i += 2) a[i] = s[i + 1 >> 1] - 'a';
  for (int i = 2; i <= n; i += 2) a[i] = s[n - (i >> 1) + 1] - 'a';
  a[0] = -1;
  f[0] = 1;
  for (int x = 1; x <= n; x++) {
    append(x);
    for (int i = lst; i; i = anc[i]) {
      g[i] = f[x - len[anc[i]] - dif[i]];
      if (fa[i] ^ anc[i]) inc(g[i], g[fa[i]]);
      if (~x & 1) inc(f[x], g[i]);
    }
  }
  printf("%d\n", f[n]);
  return 0;
}