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 N = 1e6 + 100;
const int MOD = 1e9 + 7;
struct PAM {
  int next[N][26], fail[N], len[N];
  int txt[N], diff[N], link[N];
  int tot, root0, root1, last, size;
  void init() {
    last = tot = size = 0;
    txt[size] = -1;
    root0 = newnode(0);
    root1 = newnode(-1);
    fail[root0] = 1;
    fail[root1] = 0;
  }
  int newnode(int l) {
    len[tot] = l;
    diff[tot] = 0;
    memset(next[tot], 0, sizeof(next[tot]));
    tot++;
    return tot - 1;
  }
  int getfail(int x) {
    while (txt[size - len[x] - 1] != txt[size]) x = fail[x];
    return x;
  }
  void extend(int c) {
    txt[++size] = c;
    int now = getfail(last);
    if (!next[now][c]) {
      int tmp = newnode(len[now] + 2);
      fail[tmp] = next[getfail(fail[now])][c];
      next[now][c] = tmp;
    }
    last = next[now][c];
    diff[last] = len[last] - len[fail[last]];
    if (diff[last] == diff[fail[last]])
      link[last] = link[fail[last]];
    else
      link[last] = fail[last];
  }
} pam;
char s[N], t[N];
int f[N], g[N], n;
int main() {
  scanf("%s", t + 1);
  n = strlen(t + 1);
  if (n & 1) {
    printf("0\n");
    return 0;
  }
  pam.init();
  f[0] = 1;
  for (int i = 1; i <= n; ++i)
    s[i] = i & 1 ? t[(i + 1) >> 1] : t[n + 1 - (i >> 1)];
  for (int i = 1; i <= n; ++i) {
    pam.extend(s[i] - 'a');
    for (int j = pam.last; j; j = pam.link[j]) {
      g[j] = f[i - pam.diff[j] - pam.len[pam.link[j]]];
      if (pam.link[j] != pam.fail[j]) g[j] = (g[j] + g[pam.fail[j]]) % MOD;
      if ((i & 1) == 0) f[i] = (f[i] + g[j]) % MOD;
    }
  }
  printf("%d\n", f[n]);
}