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 read() {
  char c = getchar();
  int x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
struct modint {
  int x;
  modint(int o = 0) { x = o; }
  modint &operator=(int o) { return x = o, *this; }
  modint &operator+=(modint o) {
    return x = x + o.x >= 1000000007 ? x + o.x - 1000000007 : x + o.x, *this;
  }
  modint &operator-=(modint o) {
    return x = x - o.x < 0 ? x - o.x + 1000000007 : x - o.x, *this;
  }
  modint &operator*=(modint o) { return x = 1ll * x * o.x % 1000000007, *this; }
  modint &operator^=(int b) {
    modint a = *this, c = 1;
    for (; b; b >>= 1, a *= a)
      if (b & 1) c *= a;
    return x = c.x, *this;
  }
  modint &operator/=(modint o) { return *this *= o ^= 1000000007 - 2; }
  modint &operator+=(int o) {
    return x = x + o >= 1000000007 ? x + o - 1000000007 : x + o, *this;
  }
  modint &operator-=(int o) {
    return x = x - o < 0 ? x - o + 1000000007 : x - o, *this;
  }
  modint &operator*=(int o) { return x = 1ll * x * o % 1000000007, *this; }
  modint &operator/=(int o) { return *this *= ((modint(o)) ^= 1000000007 - 2); }
  template <class I>
  friend modint operator+(modint a, I b) {
    return a += b;
  }
  template <class I>
  friend modint operator-(modint a, I b) {
    return a -= b;
  }
  template <class I>
  friend modint operator*(modint a, I b) {
    return a *= b;
  }
  template <class I>
  friend modint operator/(modint a, I b) {
    return a /= b;
  }
  friend modint operator^(modint a, int b) { return a ^= b; }
  friend bool operator==(modint a, int b) { return a.x == b; }
  friend bool operator!=(modint a, int b) { return a.x != b; }
  bool operator!() { return !x; }
  modint operator-() { return x ? 1000000007 - x : 0; }
};
inline modint qpow(modint a, int b) { return a ^ b; }
int n;
char s[1000005], qwq[1000005];
int ch[1000005][26], len[1000005], fa[1000005], lst, cnt;
int dif[1000005], lnk[1000005];
inline void init() {
  len[0] = 0, len[1] = -1;
  fa[0] = 1, fa[1] = 1, lnk[0] = 1, cnt = 1;
}
int getfa(int x, int n) {
  while (s[n - len[x] - 1] != s[n]) x = fa[x];
  return x;
}
void ins(int c, int n) {
  int p = getfa(lst, n);
  if (!ch[p][c]) {
    int u = ++cnt, t = getfa(fa[p], n);
    len[u] = len[p] + 2, fa[u] = ch[t][c];
    ch[p][c] = u;
    dif[u] = len[u] - len[fa[u]];
    lnk[u] = (dif[u] == dif[fa[u]]) ? lnk[fa[u]] : fa[u];
  }
  lst = ch[p][c];
}
modint f[1000005], g[1000005];
signed main() {
  scanf("%s", qwq + 1), n = strlen(qwq + 1);
  if (n & 1) {
    puts("0");
    return 0;
  }
  init();
  int tl = 1, tr = n;
  for (register int i = (1); i <= (n); ++i)
    if (i & 1)
      s[i] = qwq[tl], ++tl;
    else
      s[i] = qwq[tr], --tr;
  f[0] = 1;
  for (register int i = (1); i <= (n); ++i) {
    ins(s[i] - 'a', i);
    for (int k = lst; k; k = lnk[k]) {
      g[k] = f[i - len[lnk[k]] - dif[k]];
      if (lnk[k] != fa[k]) g[k] += g[fa[k]];
      if (i % 2 == 0) f[i] += g[k];
    }
  }
  cout << f[n].x;
  return 0;
}