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;
#pragma GCC optimize("-Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
const int N = 1e6 + 17;
const int mod = 1e9 + 7;
int n;
const int base = 313;
int makeH(char c) { return c; }
vector<int> pows = {1};
int Add(int x, int y) {
  x = (x + y);
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  return x;
}
int Mul(int x, int y) { return 1ll * x * y % mod; }
struct HashRange {
  string s;
  vector<int> cum = {0};
  void add(char c) {
    s += c;
    cum.push_back(Add(Mul(cum.back(), base), makeH(c)));
  }
  void add(string x) {
    for (auto u : x) add(u);
  }
  void extend(int len) {
    while ((int)pows.size() < (int)s.size()) {
      pows.push_back(Mul(base, pows.back()));
    }
  }
  int hash(int l, int r) {
    int len = r - l + 1;
    extend(len);
    return Add(cum[r + 1], -Mul(cum[l], pows[len]));
  }
  bool operator==(HashRange &rhs) { return cum.back() == rhs.cum.back(); }
};
HashRange hr;
string st;
unordered_map<int, int> msi;
vector<int> v = {-1};
int t;
struct node {
  map<int, int> nxt, prv;
  int link = 0, len = 0;
  int acc = 0;
  int diff = 0;
  int slink = 0;
  node() {}
};
vector<node> eer;
int suff;
int series_ans[N], dp[N];
int s[N];
int c = 0;
int get_link(int x) {
  while (s[c - eer[x].len - 2] != s[c - 1]) {
    x = eer[x].link;
  }
  return x;
}
bool extend(int ch) {
  s[c++] = ch;
  suff = get_link(suff);
  if (eer[suff].nxt[ch]) {
    suff = eer[suff].nxt[ch];
    return 0;
  }
  int lst = suff;
  suff = eer.size();
  eer.push_back(node());
  eer[suff].len = 2 + eer[lst].len;
  eer[suff].link = eer[get_link(eer[lst].link)].nxt[ch];
  eer[lst].nxt[ch] = suff;
  eer[suff].diff = eer[suff].len - eer[eer[suff].link].len;
  if (eer[suff].diff == eer[eer[suff].link].diff)
    eer[suff].slink = eer[eer[suff].link].slink;
  else
    eer[suff].slink = eer[suff].link;
  return 1;
}
void process() {
  eer.push_back(node()), eer.push_back(node());
  eer[0].link = 1;
  eer[1].len = -1;
  s[c++] = -1;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> st;
  hr.add(st);
  n = st.size();
  int l = 0;
  for (int i = 0; i < n / 2; ++i) {
    int lhs = hr.hash(l, i);
    if (lhs == hr.hash(n - i - 1, n - l - 1)) {
      if (msi[lhs] == 0) {
        msi[lhs] = ++t;
      }
      v.push_back(msi[lhs]);
      l = i + 1;
    }
  }
  if (l != st.size() / 2) {
    return cout << 0, 0;
  }
  dp[0] = 1;
  process();
  for (int i = 1; i < v.size(); ++i) {
    extend(v[i]);
    for (int u = suff; eer[u].len > 0; u = eer[u].slink) {
      series_ans[u] = (dp[i - (eer[eer[u].slink].len + eer[u].diff)]) % mod;
      if (eer[u].diff == eer[eer[u].link].diff)
        series_ans[u] = (series_ans[u] + series_ans[eer[u].link]) % mod;
      dp[i] = (dp[i] + series_ans[u]) % mod;
    }
  }
  cout << dp[v.size() - 1];
  return 0;
}