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;
namespace prom {
int read() {
  char a = getchar();
  int res = 0;
  int f = 1;
  while (a < '0' || a > '9') {
    if (a == '-') f = -1;
    a = getchar();
  }
  while (a >= '0' && a <= '9') res = res * 10 + a - '0', a = getchar();
  return res * f;
}
const int p = 1000000007;
const int Maxn = 1000005;
void upd(int& x, int y) { x = (x + y) % p; }
struct TR {
  int son[26];
  int len, diff;
  int slink, fail;
} tr[Maxn];
int tot, last, n;
int newTR(int len) {
  int ro = ++tot;
  tr[ro] = TR();
  tr[ro].len = len;
  return ro;
}
int S[Maxn];
void Init() {
  tot = -1;
  last = n = 0;
  newTR(0);
  newTR(-1);
  tr[0].fail = 1;
  S[0] = -1;
}
int getfail(int x) {
  while (S[n] != S[n - tr[x].len - 1]) x = tr[x].fail;
  return x;
}
void ins(int a) {
  S[++n] = a;
  int p = getfail(last);
  if (!tr[p].son[a]) {
    int np = newTR(tr[p].len + 2);
    int fail = tr[getfail(tr[p].fail)].son[a];
    tr[np].fail = fail;
    tr[np].diff = tr[np].len - tr[fail].len;
    tr[np].slink = (tr[np].diff == tr[fail].diff) ? tr[fail].slink : fail;
    tr[p].son[a] = np;
  }
  last = tr[p].son[a];
}
char s[Maxn], T[Maxn];
int dp[Maxn], sr_g[Maxn];
int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  for (int i = 1; i * 2 <= n; i++) T[i * 2 - 1] = s[i], T[i * 2] = s[n - i + 1];
  dp[0] = 1;
  Init();
  for (int i = 1; i <= n; i++) {
    ins(T[i] - 'a');
    for (int j = last; tr[j].len > 0; j = tr[j].slink) {
      sr_g[j] = dp[i - (tr[tr[j].slink].len + tr[j].diff)];
      if (tr[j].diff == tr[tr[j].fail].diff) upd(sr_g[j], sr_g[tr[j].fail]);
      upd(dp[i], sr_g[j]);
    }
    if (i & 1) dp[i] = 0;
  }
  printf("%d\n", dp[n]);
  return 0;
}
}  // namespace prom
int main() { return prom::main(); }