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 INF = 2e9;
const long long LINF = 2e16;
const int magic = 348;
const int MOD = 1e9 + 7;
const double eps = 1e-10;
const double pi = acos(-1);
template <typename T>
inline void Get(T &first) {
  bool f;
  char ch;
  T res;
  while (!isdigit(ch = getchar()) && ch != '-') {
  }
  if (ch == '-')
    f = false, res = 0;
  else
    f = true, res = ch - '0';
  while (isdigit(ch = getchar())) res = res * 10 + ch - '0';
  first = (f ? res : (-res));
}
template <typename T1, typename... T2>
inline void Get(T1 &first, T2 &...second) {
  Get(first);
  Get(second...);
}
struct fastio {
  static const int S = 1e7;
  char rbuf[S + 48], wbuf[S + 48];
  int rpos, wpos, len;
  fastio() { rpos = len = wpos = 0; }
  inline char Getchar() {
    if (rpos == len) rpos = 0, len = fread(rbuf, 1, S, stdin);
    if (!len) return EOF;
    return rbuf[rpos++];
  }
  template <typename T>
  inline void Get(T &first) {
    char ch;
    bool f;
    T res;
    while (!isdigit(ch = Getchar()) && ch != '-') {
    }
    if (ch == '-')
      f = false, res = 0;
    else
      f = true, res = ch - '0';
    while (isdigit(ch = Getchar())) res = res * 10 + ch - '0';
    first = (f ? res : (-res));
  }
  template <typename T1, typename... T2>
  inline void Get(T1 &first, T2 &...second) {
    Get(first);
    Get(second...);
  }
  inline void getstring(char *s) {
    char ch;
    while ((ch = Getchar()) <= 32) {
    }
    for (; ch > 32; ch = Getchar()) *s++ = ch;
    *s = '\0';
  }
  inline void flush() {
    fwrite(wbuf, 1, wpos, stdout);
    fflush(stdout);
    wpos = 0;
  }
  inline void Writechar(char ch) {
    if (wpos == S) flush();
    wbuf[wpos++] = ch;
  }
  template <typename T>
  inline void Print(T first, char ch) {
    char s[20];
    int pt = 0;
    if (first == 0)
      s[++pt] = '0';
    else {
      if (first < 0) Writechar('-'), first = -first;
      while (first) s[++pt] = '0' + first % 10, first /= 10;
    }
    while (pt) Writechar(s[pt--]);
    Writechar(ch);
  }
  template <typename T1, typename... T2>
  inline void Print(T1 &first, T2 &...second) {
    Print(first, ' ');
    Print(second..., ' ');
    Writechar('\n');
  }
  inline void printstring(char *s) {
    int pt = 1;
    while (s[pt] != '\0') Writechar(s[pt++]);
  }
} io;
template <typename T>
inline void check_max(T &first, T cmp) {
  first = max(first, cmp);
}
template <typename T>
inline void check_min(T &first, T cmp) {
  first = min(first, cmp);
}
template <typename T>
inline T myabs(T first) {
  return first >= 0 ? first : -first;
}
template <typename T>
inline T gcd(T first, T second) {
  return second == 0 ? first : gcd(second, first % second);
}
template <typename T>
inline T add(T first) {
  if (first >= MOD) first -= MOD;
  return first;
}
template <typename T>
inline T add(T first, int MO) {
  if (first >= MO) first -= MO;
  return first;
}
template <typename T>
inline T sub(T first) {
  if (first < 0) first += MOD;
  return first;
}
template <typename T>
inline T sub(T first, int MO) {
  if (first < 0) first += MO;
  return first;
}
template <typename T>
inline T mul(T first, T second) {
  return 1ll * first * second % MOD;
}
template <typename T>
inline T mul(T first, T second, int MO) {
  return 1ll * first * second % MO;
}
template <typename T>
inline void Add(T &first, T second) {
  first = add(first + second);
}
template <typename T>
inline void Add(T &first, T second, int MO) {
  first = add(first + second, MO);
}
template <typename T>
inline void Sub(T &first, T second) {
  first = sub(first - second);
}
template <typename T>
inline void Sub(T &first, T second, int MO) {
  first = sub(first - second, MO);
}
template <typename T>
inline void Mul(T &first, T second) {
  first = mul(first, second);
}
template <typename T>
inline void Mul(T &first, T second, int MO) {
  first = mul(first, second, MO);
}
template <typename T>
inline int quick_pow(int first, T second) {
  int res = 1;
  while (second) {
    if (second & 1) res = 1ll * res * first % MOD;
    first = 1ll * first * first % MOD;
    second >>= 1;
  }
  return res;
}
template <typename T>
inline int quick_pow(int first, T second, int MO) {
  int res = 1;
  while (second) {
    if (second & 1) res = 1ll * res * first % MO;
    first = 1ll * first * first % MO;
    second >>= 1;
  }
  return res;
}
const int MAXN = 1e6;
char s[MAXN + 48], ss[MAXN + 48];
int n;
int dp[MAXN + 48];
namespace PAM {
int nxt[MAXN + 48][27], fail[MAXN + 48], slink[MAXN + 48], len[MAXN + 48],
    diff[MAXN + 48], serie[MAXN + 48], last, tot;
inline int Create() {
  ++tot;
  memset(nxt[tot], 0, sizeof(nxt[tot]));
  fail[tot] = slink[tot] = len[tot] = 0;
  return tot;
}
inline void init() {
  len[0] = 0;
  len[1] = -1;
  fail[0] = 1;
  fail[1] = 0;
  slink[0] = slink[1] = 0;
  diff[0] = 1;
  diff[1] = -1;
  memset(nxt[0], 0, sizeof(nxt[0]));
  memset(nxt[1], 0, sizeof(nxt[1]));
  tot = last = 1;
}
inline int getfail(int pos, int first) {
  while (s[pos] != s[pos - len[first] - 1]) first = fail[first];
  return first;
}
inline void extend(int pos) {
  int w = s[pos] - 'a' + 1, fa = getfail(pos, last);
  if (!nxt[fa][w]) {
    int cur = Create();
    len[cur] = len[fa] + 2;
    int tmp = getfail(pos, fail[fa]);
    fail[cur] = nxt[tmp][w];
    diff[cur] = len[cur] - len[fail[cur]];
    if (diff[cur] == diff[fail[cur]])
      slink[cur] = slink[fail[cur]];
    else
      slink[cur] = fail[cur];
    nxt[fa][w] = cur;
  }
  last = nxt[fa][w];
}
inline void calc_dp(int pos) {
  for (register int v = last; len[v] > 0; v = slink[v]) {
    serie[v] = dp[pos - (len[slink[v]] + diff[v])];
    if (diff[v] == diff[fail[v]]) Add(serie[v], serie[fail[v]]);
    Add(dp[pos], serie[v]);
  }
  if (pos & 1) dp[pos] = 0;
}
inline void build() {
  dp[0] = 1;
  init();
  for (register int i = int(1); i <= int(n); i++) {
    extend(i), calc_dp(i);
  }
}
}  // namespace PAM
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  if (n & 1) {
    puts("0");
    return 0;
  }
  for (register int i = 1, j = n, pt = 1; i < j; i++, j--, pt += 2)
    ss[pt] = s[i], ss[pt + 1] = s[j];
  for (register int i = int(1); i <= int(n); i++) s[i] = ss[i];
  PAM::build();
  printf("%d\n", dp[n]);
  io.flush();
  return 0;
}