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;
template <class T>
inline void rd(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 - '0' + c, c = getchar();
  x *= f;
}
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int link[N], slink[N], diff[N], len[N], last;
namespace PT {
int ch[N][26], ncnt;
int S[N], n;
void init() {
  ncnt = 1;
  link[0] = 1, link[1] = 0;
  len[0] = 0, len[1] = -1;
  S[0] = -1;
}
void ins(int c) {
  S[++n] = c;
  int p = last;
  while (S[n - len[p] - 1] != S[n]) p = link[p];
  if (!ch[p][c]) {
    int q = ++ncnt, u = link[p];
    while (S[n - len[u] - 1] != S[n]) u = link[u];
    link[q] = ch[u][c], ch[p][c] = q;
    len[q] = len[p] + 2, diff[q] = len[q] - len[link[q]],
    slink[q] = diff[q] == diff[link[q]] ? slink[link[q]] : link[q];
  }
  last = ch[p][c];
}
}  // namespace PT
int dp[N], g[N];
int n;
char S[N], T[N];
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  for (int i = 1, tp = 0; i < n - i + 1; ++i)
    T[++tp] = S[i], T[++tp] = S[n - i + 1];
  PT::init();
  dp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    PT::ins(T[i] - 'a');
    for (int u = last; len[u] > 0; u = slink[u]) {
      g[u] = dp[i - len[slink[u]] - diff[u]];
      if (slink[u] != link[u]) g[u] = (g[u] + g[link[u]]) % mod;
      if (!(i & 1)) dp[i] = (dp[i] + g[u]) % mod;
    }
  }
  printf("%d", dp[n]);
  return 0;
}