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 INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 1000007;
const int MOD = 1e9 + 7;
struct sT {
  sT() : s(0), d(0), k(0) {}
  sT(int _s, int _d, int _k) : s(_s), d(_d), k(_k) {}
  int s, d, k;
};
int n;
char os[MAXN], s[MAXN];
int dp[MAXN], gpl[MAXN];
vector<sT> g, g1;
void init();
void input();
void work();
int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  return x;
}
void addv(int &x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() { scanf("%s", os); }
void work() {
  n = strlen(os);
  int ttk = 0;
  for (int i = 0; i < n >> 1; ++i) s[++ttk] = os[i], s[++ttk] = os[n - i - 1];
  dp[0] = 1;
  int pre, size, cv;
  for (int i = 1; i <= n; ++i) {
    g1.clear();
    pre = -i;
    for (auto &x : g) {
      if (x.s > 1 && s[x.s - 1] == s[i]) {
        if ((x.s - 1 - pre) ^ x.d) {
          g1.push_back(sT(x.s - 1, x.s - 1 - pre, 1));
          if (x.k > 1) g1.push_back(sT(x.s - 1 + x.d, x.d, x.k - 1));
        } else
          g1.push_back(sT(x.s - 1, x.d, x.k));
        pre = g1.back().s + g1.back().d * (g1.back().k - 1);
      }
    }
    if (i > 1 && s[i] == s[i - 1]) g1.push_back(sT(i - 1, i - 1 - pre, 1));
    g.clear();
    if (!g1.empty()) {
      g.push_back(g1.front());
      size = g1.size();
      for (int i = 1; i < size; ++i) {
        if (g1[i].d == g.back().d)
          g.back().k += g1[i].k;
        else
          g.push_back(g1[i]);
      }
    }
    dp[i] = 0;
    for (auto x : g) {
      cv = dp[x.s + x.d * (x.k - 1) - 1];
      if (x.k > 1) addv(cv, gpl[x.s - x.d]);
      if (x.s - x.d >= 0) gpl[x.s - x.d] = cv;
      addv(dp[i], cv);
    }
  }
  printf("%d\n", dp[n]);
}