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>
char aa[1 + 1000000 + 1];
int tt[2 + 1000000][26], fff[2 + 1000000][26], ff[2 + 1000000],
    ff_[2 + 1000000], len[2 + 1000000], diff[2 + 1000000], dp_[2 + 1000000];
int node(int l) {
  static int _;
  len[_] = l;
  return _++;
}
void init() {
  int a;
  node(0), node(-1);
  aa[0] = -1;
  for (a = 0; a < 26; a++) fff[0][a] = fff[1][a] = 1;
}
int main() {
  static char cc[1000000 + 1];
  static int dp[1000000 + 1];
  int n, m, s_;
  init();
  scanf("%s", cc), n = strlen(cc);
  dp[0] = 1;
  s_ = 0;
  for (m = 1; m <= n; m++) {
    int a = (m % 2 == 1 ? cc[m / 2] : cc[n - m / 2]) - 'a', s, x;
    aa[m] = a;
    if (aa[m - 1 - len[s_]] != a) s_ = fff[s_][a];
    if (tt[s_][a] == 0) {
      int t = node(len[s_] + 2), f = tt[fff[s_][a]][a];
      diff[t] = len[t] - len[f], ff[t] = f,
      ff_[t] = diff[t] != diff[f] ? f : ff_[f];
      tt[s_][a] = t;
      memcpy(fff[t], fff[f], sizeof fff[f]), fff[t][(int)aa[m - len[f]]] = f;
    }
    s_ = tt[s_][a];
    s = s_, x = 0;
    while (len[s] > 0) {
      int f = ff[s], f_ = ff_[s];
      dp_[s] = ((diff[f] == diff[s] ? dp_[f] : 0) + dp[m - len[f_] - diff[s]]) %
               1000000007;
      x = (x + dp_[s]) % 1000000007, s = f_;
    }
    if (m % 2 == 0) dp[m] = x;
  }
  printf("%d\n", dp[n]);
  return 0;
}