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>
#pragma GCC optimize("O3")
const int N = 1000010;
const int P = 1000000007;
char s[N];
int n, m, c[N], sz, ch[N][26], fail[N], len[N], diff[N], slink[N], g[N], f[N],
    last;
inline void Init() {
  c[0] = 233;
  (len[sz] = (0), sz++);
  (len[sz] = (-1), sz++);
  fail[0] = 1;
  fail[1] = 1;
  last = 0;
}
inline int find(int x) {
  while (c[m - len[x] - 1] != c[m]) x = fail[x];
  return x;
}
inline void insert(int x) {
  c[++m] = x;
  int idx = find(last);
  if (!ch[idx][x]) {
    int nw = (len[sz] = (len[idx] + 2), sz++);
    fail[nw] = ch[find(fail[idx])][x];
    ch[idx][x] = nw;
    diff[nw] = len[nw] - len[fail[nw]];
    slink[nw] = diff[nw] == diff[fail[nw]] ? slink[fail[nw]] : fail[nw];
  }
  last = ch[idx][x];
}
int main() {
  Init();
  scanf("%s", s + 1);
  n = strlen(s + 1);
  int l = n >> 1, r = l + 1, cur = 0;
  register int x, ans;
  f[0] = 1;
  while (r - l <= n) {
    ++cur;
    insert(cur & 1 ? s[l--] - 'a' : s[r++] - 'a');
    ans = 0;
    for (x = last; x; x = slink[x]) {
      g[x] = f[cur - (len[slink[x]] + diff[x])];
      if (diff[x] == diff[fail[x]]) g[x] = (g[x] + g[fail[x]]) % P;
      ans = (ans + g[x]) % P;
    }
    if (!(cur & 1)) f[cur] = ans;
  }
  printf("%d\n", ans);
  return 0;
}