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;
int const mod = 1e9 + 7;
int const MAXN = 1e6 + 5;
char s[MAXN], t[MAXN];
int child[MAXN << 1][26], parent[MAXN << 1], mxlen[MAXN << 1], cnt = 2,
                                                               last = 1;
int d[MAXN << 1], bot[MAXN << 1];
int f[MAXN], g[MAXN << 1];
int GetFail(int now, int pos) {
  while (now && s[pos] != s[pos - mxlen[now] - 1]) now = parent[now];
  return now;
}
int main() {
  cin >> (t + 1);
  int n = strlen(t + 1);
  for (register int i = 1; i <= n; ++i)
    s[i] = (i & 1) ? t[i / 2 + 1] : t[n - i / 2 + 1];
  parent[1] = 2;
  mxlen[1] = 0, mxlen[2] = -1;
  for (register int i = 0; i < 26; ++i) child[0][i] = 1;
  f[0] = 1;
  for (register int i = 1; i <= n; ++i) {
    int ch = s[i] - 'a';
    last = GetFail(last, i);
    if (child[last][ch])
      last = child[last][ch];
    else {
      ++cnt;
      child[last][ch] = cnt;
      mxlen[cnt] = mxlen[last] + 2;
      parent[cnt] = child[GetFail(parent[last], i)][ch];
      last = cnt;
      if (mxlen[parent[cnt]] * 2 > mxlen[cnt] &&
          (!d[parent[cnt]] ||
           mxlen[cnt] - mxlen[parent[cnt]] == d[parent[cnt]])) {
        d[cnt] = mxlen[cnt] - mxlen[parent[cnt]], bot[cnt] = bot[parent[cnt]];
        d[parent[cnt]] = mxlen[cnt] - mxlen[parent[cnt]];
      } else
        d[cnt] = 0, bot[cnt] = cnt;
    }
    for (register int cur = last; cur; cur = parent[bot[cur]]) {
      if (bot[cur] != cur)
        g[cur] = g[parent[cur]];
      else
        g[cur] = 0;
      if (mxlen[bot[cur]]) g[cur] = (g[cur] + f[i - mxlen[bot[cur]]]) % mod;
      if (i % 2 == 0) f[i] = (f[i] + g[cur]) % mod;
    }
  }
  printf("%d\n", f[n]);
  return 0;
}