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>
const int maxn = 1E+6 + 5;
const long long mod = 1E+9 + 7;
int n;
char s[maxn], t[maxn];
namespace PAM {
int ind, last, ch[maxn][26];
int fa[maxn], len[maxn];
int dif[maxn], sf[maxn];
inline void init() {
  ind = fa[0] = 1;
  len[0] = last = 0;
  len[1] = fa[1] = -1;
}
inline int getfa(int u) {
  while (s[n - len[u] - 1] != s[n]) u = fa[u];
  return u;
}
inline int extend(int c) {
  int p = getfa(last);
  if (ch[p][c]) return last = ch[p][c];
  int np = ++ind;
  len[np] = len[p] + 2;
  fa[np] = ch[getfa(fa[p])][c];
  ch[p][c] = np, dif[np] = len[np] - len[fa[np]];
  if (dif[np] == dif[fa[np]])
    sf[np] = sf[fa[np]];
  else
    sf[np] = fa[np];
  return last = np;
}
}  // namespace PAM
long long f[maxn], g[maxn];
int main() {
  scanf("%s", t + 1), PAM::init();
  int Len = strlen(t + 1);
  for (int i = 1; i <= Len; ++i)
    s[i] = i & 1 ? t[i / 2 + 1] : t[Len - i / 2 + 1];
  f[0] = 1;
  for (n = 1; n <= Len; ++n) {
    for (int p = PAM::extend(s[n] - 'a'); p > 1; p = PAM::sf[p]) {
      g[p] = f[n - PAM::len[PAM::sf[p]] - PAM::dif[p]];
      if (PAM::dif[p] == PAM::dif[PAM::fa[p]]) (g[p] += g[PAM::fa[p]]) %= mod;
      (f[n] += g[p]) %= mod;
    }
    if (n & 1) f[n] = 0;
  }
  printf("%lld", f[Len]);
}