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 void proc_status() {
  ifstream t("/proc/self/status");
  cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>())
       << endl;
}
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline T read() {
  register T sum(0), fg(1);
  register char ch(getchar());
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fg = -1;
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 - '0' + ch;
  return sum * fg;
}
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e6;
int n;
char s0[MAXN + 5];
inline void input() { scanf("%s", s0 + 1), n = strlen(s0 + 1); }
namespace PAM {
const int MAX_NODE = MAXN * 2, alpha = 26;
int fail[MAX_NODE + 5], trans[MAX_NODE + 5][alpha], nxt[MAX_NODE + 5], cnt;
int len[MAX_NODE + 5], delta[MAX_NODE + 5];
int rt0, rt1, lst;
int S[MAX_NODE + 5], N = 0;
inline void init() {
  S[0] = -1;
  cnt = 1, lst = 0;
  memset(trans[0], 0, sizeof trans[0]);
  memset(trans[1], 0, sizeof trans[1]);
  len[0] = 0, len[1] = -1;
  fail[0] = 1;
}
inline int new_node(int l) {
  len[++cnt] = l;
  fail[cnt] = 0;
  memset(trans[cnt], 0, sizeof trans[cnt]);
  return cnt;
}
inline int extend(int ch) {
  int p = lst;
  S[++N] = ch;
  while (S[N - len[p] - 1] != S[N]) p = fail[p];
  int np = -1;
  if (!trans[p][ch]) {
    np = new_node(len[p] + 2);
    int t = fail[p];
    while (S[N - len[t] - 1] != S[N]) t = fail[t];
    fail[np] = trans[t][ch];
    delta[np] = len[np] - len[fail[np]];
    nxt[np] = delta[np] == delta[fail[np]] ? nxt[fail[np]] : fail[np];
    trans[p][ch] = np;
  } else
    np = trans[p][ch];
  return lst = np;
}
}  // namespace PAM
inline void solve() {
  static int s[MAXN + 5];
  for (int i = 1; i <= n / 2; ++i) {
    s[i * 2 - 1] = s0[i] - 'a';
    s[i * 2] = s0[n - i + 1] - 'a';
  }
  static int nd[MAXN + 5];
  PAM::init();
  for (int i = 1; i <= n; ++i) nd[i] = PAM::extend(s[i]);
  static int f[MAXN + 5], g[MAXN + 5];
  f[0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int p = nd[i]; p; p = PAM::nxt[p]) {
      g[p] = f[i - PAM::len[PAM::nxt[p]] - PAM::delta[p]];
      if (PAM::delta[p] == PAM::delta[PAM::fail[p]])
        (g[p] += g[PAM::fail[p]]) %= MOD;
      if (i % 2 == 0) (f[i] += g[p]) %= MOD;
    }
  printf("%d\n", (f[n] + MOD) % MOD);
}
int main() {
  input();
  solve();
  return 0;
}