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;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 - '0' + c, c = getchar();
  x *= f;
}
const int N = 1e6 + 10, mod = 1e9 + 7;
int ch[N][26], fail[N], len[N], diff[N], last;
int fa[N];
struct Palindromic_Tree {
  char S[N];
  int ncnt, n;
  void init() {
    n = 0;
    S[0] = -1;
    ncnt = last = 1;
    fail[1] = 0, fail[0] = 1, len[0] = 0, len[1] = -1;
  }
  int get(int u) {
    while (S[n - len[u] - 1] != S[n]) u = fail[u];
    return u;
  }
  void insert(int c) {
    S[++n] = c;
    int cur = get(last);
    if (!ch[cur][c]) {
      int now = ++ncnt;
      len[now] = len[cur] + 2;
      fail[now] = ch[get(fail[cur])][c], ch[cur][c] = now;
      diff[now] = len[now] - len[fail[now]];
      fa[now] = (diff[now] == diff[fail[now]]) ? fa[fail[now]] : fail[now];
    }
    last = ch[cur][c];
  }
} PT;
char str[N], s1[N];
int n;
int f[N], g[N];
int main() {
  scanf("%s", s1 + 1);
  n = strlen(s1 + 1);
  if (n & 1) {
    puts("0");
    return 0;
  }
  for (int i = 1, l = 0; i * 2 <= n; ++i)
    str[++l] = s1[i], str[++l] = s1[n - i + 1];
  f[0] = 1;
  PT.init();
  for (int i = 1; i <= n; ++i) {
    PT.insert(str[i] - 'a');
    for (int v = last; v; v = fa[v]) {
      g[v] = f[i - len[fa[v]] - diff[v]];
      if (diff[v] == diff[fail[v]]) g[v] = (g[v] + g[fail[v]]) % mod;
      if (!(i & 1)) f[i] = (f[i] + g[v]) % mod;
    }
  }
  printf("%d", f[n]);
  return 0;
}