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 MOD = 1e9 + 7;
template <typename T>
void chkmax(T &a, T b) {
  a = max(a, b);
}
template <typename T>
void chkmin(T &a, T b) {
  a = min(a, b);
}
template <typename T>
void ADD(T &a, T b) {
  a = a + b;
  if (a >= MOD) a -= MOD;
}
const int N = 1100000;
int n;
char P[N], S[N];
int par[N], anc[N], len[N], nxt[N][30], F[N], G[N];
int tot, cnt, las;
void append(int c) {
  c -= 'a' - 1;
  S[++tot] = c;
  int p = las;
  while (p && S[tot] != S[tot - len[p] - 1]) p = par[p];
  if (!p) p = 1;
  if (nxt[p][c])
    las = nxt[p][c];
  else {
    int np = las = nxt[p][c] = ++cnt;
    len[np] = len[p] + 2;
    int q = par[p];
    while (q && S[tot] != S[tot - len[q] - 1]) q = par[q];
    if (!q)
      par[np] = 2;
    else
      par[np] = nxt[q][c];
    int nq = par[np];
    if (len[np] - len[nq] == len[nq] - len[par[nq]] && nq != 2)
      anc[np] = anc[nq];
    else
      anc[np] = np;
  }
  for (int np = nxt[p][c]; np != 2; np = par[anc[np]]) {
    G[np] = ((np != anc[np] ? G[par[np]] : 0) + F[tot - len[anc[np]]]) % MOD;
    ADD(F[tot], G[np]);
  }
}
int main() {
  ios ::sync_with_stdio(0);
  cin >> (P + 1);
  n = strlen(P + 1);
  cnt = 2;
  las = 1;
  len[1] = -1;
  par[2] = 1;
  anc[1] = 1;
  anc[2] = 2;
  F[0] = 1;
  for (int i = 1, j = n; i < j; ++i, --j)
    append(P[i]), F[tot] = 0, append(P[j]);
  cout << F[tot] << endl;
}