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 = 1000000007;
char S[1000005];
char S2[1000005];
int N, ind, cur, Serial[1000005], DP[1000005], suff;
struct PTree {
  int suf, next[26], len, slink, diff;
} Palind[1000005];
void initTree() {
  cur = suff = 2;
  Palind[1].suf = 1;
  Palind[1].len = -1;
  Palind[2].suf = 1;
  Palind[2].len = 0;
}
void Read() {
  cin.getline(S + 1, 1000005);
  N = strlen(S + 1);
}
void precalcS() {
  int left = 1, right = N;
  while (left <= right) {
    if (left > right) break;
    S2[++ind] = S[left];
    ++left;
    if (left > right) break;
    S2[++ind] = S[right];
    --right;
  }
}
void precalcSLink(int i) {
  Palind[i].diff = Palind[i].len - Palind[Palind[i].suf].len;
  if (Palind[i].diff == Palind[Palind[i].suf].diff)
    Palind[i].slink = Palind[Palind[i].suf].slink;
  else
    Palind[i].slink = Palind[i].suf;
}
void addLetter(int pos) {
  int let = S2[pos] - 'a';
  int curr = suff, len;
  while (1) {
    if (pos - Palind[curr].len - 1 >= 1 &&
        S2[pos] == S2[pos - Palind[curr].len - 1])
      break;
    curr = Palind[curr].suf;
  }
  if (Palind[curr].next[let] != 0) {
    suff = Palind[curr].next[let];
    return;
  }
  suff = ++cur;
  Palind[cur].len = Palind[curr].len + 2;
  Palind[curr].next[let] = cur;
  if (Palind[cur].len == 1) {
    Palind[cur].suf = 2;
    Palind[cur].slink = 2;
    Palind[cur].diff = 1;
    precalcSLink(cur);
    return;
  }
  while (1) {
    curr = Palind[curr].suf;
    len = Palind[curr].len;
    if (pos - len - 1 >= 1 && S2[pos - len - 1] == S2[pos]) {
      Palind[cur].suf = Palind[curr].next[let];
      precalcSLink(cur);
      return;
    }
  }
}
void Solve() {
  DP[0] = 1;
  for (int i = 1; i <= N; i++) {
    addLetter(i);
    int v = suff;
    DP[i] = 0;
    while (v > 2) {
      Serial[v] = DP[i - (Palind[Palind[v].slink].len + Palind[v].diff)];
      if (Palind[v].suf != Palind[v].slink) {
        Serial[v] = Serial[v] + Serial[Palind[v].suf];
        if (Serial[v] >= MOD) Serial[v] -= MOD;
      }
      DP[i] = DP[i] + Serial[v];
      if (DP[i] >= MOD) DP[i] -= MOD;
      v = Palind[v].slink;
    }
    if (i & 1) DP[i] = 0;
  }
  cout << DP[N] << "\n";
}
int main() {
  Read();
  precalcS();
  initTree();
  Solve();
  return 0;
}