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 maxn = 1e6 + 5, mod = 1e9 + 7;
inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }
inline int sub(int x, int y) { return x < y ? x - y + mod : x - y; }
int n;
char s[maxn], t[maxn];
int lst = 1, tot = 1, fa[maxn], len[maxn], ch[maxn][26], dif[maxn], slink[maxn],
    pos[maxn];
int f[maxn], g[maxn];
int extend(int i) {
  int x = lst, c = s[i] - 'a';
  while (s[i - len[x] - 1] != s[i]) x = fa[x];
  if (!ch[x][c]) {
    int k = ++tot, y = fa[x];
    len[k] = len[x] + 2;
    while (s[i - len[y] - 1] != s[i]) y = fa[y];
    fa[k] = ch[y][c];
    dif[k] = len[k] - len[fa[k]];
    ch[x][c] = k;
    if (dif[fa[k]] == dif[k])
      slink[k] = slink[fa[k]];
    else
      slink[k] = fa[k];
  }
  return lst = ch[x][c];
}
int main() {
  scanf("%s", t + 1);
  n = strlen(t + 1);
  if (n & 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n >> 1; ++i)
    s[i * 2 - 1] = t[i], s[i * 2] = t[n - i + 1];
  len[1] = -1;
  fa[0] = 1;
  for (int i = 1; i <= n; ++i) pos[i] = extend(i);
  int ans = 0;
  f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    int x = pos[i];
    while (x > 1) {
      g[x] = f[i - len[slink[x]] - dif[x]];
      if (dif[x] == dif[fa[x]]) g[x] = add(g[x], g[fa[x]]);
      if (~i & 1) f[i] = add(f[i], g[x]);
      x = slink[x];
    }
  }
  printf("%d\n", f[n]);
  return 0;
}