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>
const int N = 1e6;
const int mod = 1e9 + 7;
using namespace std;
int n;
char s[N + 5], ns[N + 5];
struct PAM {
  int ch[N + 5][26], fail[N + 5], len[N + 5], nc, las, f[N + 5], sf[N + 5],
      d[N + 5], pos[N + 5];
  char s[N + 5];
  void init(char *ch) {
    for (int i = 1; i <= n; i++) s[i] = ch[i];
    s[0] = '#';
    len[1] = -1;
    pos[0] = 1;
    fail[0] = 1;
    f[0] = 1;
    nc = 1;
  }
  void insert(int x) {
    int p = las;
    while (s[x - len[p] - 1] != s[x]) p = fail[p];
    if (!ch[p][s[x] - 'a']) {
      len[++nc] = len[p] + 2;
      int j = fail[p];
      while (s[x - len[j] - 1] != s[x]) j = fail[j];
      fail[nc] = ch[j][s[x] - 'a'];
      d[nc] = len[nc] - len[fail[nc]];
      if (d[nc] == d[fail[nc]])
        pos[nc] = pos[fail[nc]];
      else
        pos[nc] = fail[nc];
      ch[p][s[x] - 'a'] = nc;
    }
    las = ch[p][s[x] - 'a'];
    int j = las;
    while (j > 1) {
      sf[j] = f[x - len[pos[j]] - d[j]];
      if (pos[j] != fail[j]) sf[j] += sf[fail[j]], sf[j] %= mod;
      if (x % 2 == 0) f[x] += sf[j], f[x] %= mod;
      j = pos[j];
    }
  }
  void build() {
    for (int i = 1; i <= n; i++) insert(i);
  }
} pa;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  int l = 1, r = n;
  for (int i = 1; i <= n; i++)
    if (i % 2 == 1)
      ns[i] = s[l++];
    else
      ns[i] = s[r--];
  pa.init(ns);
  pa.build();
  cout << pa.f[n] << endl;
  return 0;
}