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 = 1000010, mo = 1000000007;
int n;
char s[N];
char t[N];
int diff[N];
int anc[N];
int g[N];
int f[N];
struct PAM {
  int last, tot;
  struct node {
    int son[26];
    int ff, len;
  } t[N];
  void init() {
    last = 0;
    tot = 1;
    t[1].len = -1;
    t[0].ff = t[1].ff = 1;
    anc[0] = 1;
  }
  void extend(int c, int n) {
    int p = last;
    while (s[n - t[p].len - 1] != s[n]) p = t[p].ff;
    if (!t[p].son[c]) {
      int v = ++tot, k = t[p].ff;
      t[v].len = t[p].len + 2;
      while (s[n - t[k].len - 1] != s[n]) k = t[k].ff;
      t[v].ff = t[k].son[c];
      t[p].son[c] = v;
      diff[v] = t[v].len - t[t[v].ff].len;
      anc[v] = (diff[v] == diff[t[v].ff]) ? anc[t[v].ff] : t[v].ff;
    }
    last = t[p].son[c];
  }
} pam;
void get_read() { scanf("%s", t + 1); }
void add(int &x, int y) {
  x += y;
  if (x >= mo) x -= mo;
}
void get_work() {
  pam.init();
  n = strlen(t + 1);
  if (n & 1) {
    puts("0");
    return;
  }
  int l = 0, r = n + 1;
  int tmp = 0;
  while (tmp < n) s[++tmp] = t[++l], s[++tmp] = t[--r];
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pam.extend(s[i] - 'a', i);
    for (int k = pam.last; k; k = anc[k]) {
      g[k] = f[i - pam.t[anc[k]].len - diff[k]];
      if (pam.t[k].ff != anc[k]) add(g[k], g[pam.t[k].ff]);
      if (!(i & 1)) add(f[i], g[k]);
    }
  }
  printf("%d", f[n]);
}
int main() {
  get_read();
  get_work();
  return 0;
}