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 N = 1e6 + 7;
const int mod = 1e9 + 7;
int n;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() *
               ((uint64_t) new char | 1));
uniform_int_distribution<int> distr(0.1 * mod, 0.9 * mod);
const array<int, 2> base = {distr(rng), distr(rng)};
array<int, 2> operator+(array<int, 2> l, array<int, 2> r) {
  for (int i = 0; i < 2; i++) {
    if ((l[i] += r[i]) >= mod) l[i] -= mod;
  }
  return l;
}
array<int, 2> operator-(array<int, 2> l, array<int, 2> r) {
  for (int i = 0; i < 2; i++) {
    if ((l[i] -= r[i]) < 0) l[i] += mod;
  }
  return l;
}
array<int, 2> operator*(array<int, 2> l, array<int, 2> r) {
  for (int i = 0; i < 2; i++) {
    l[i] = 1ll * l[i] * r[i] % mod;
  }
  return l;
}
array<int, 2> makeH(char c) { return {c, c}; }
vector<array<int, 2> > pows = {{1, 1}};
struct HashRange {
  string s;
  vector<array<int, 2> > cum = {{0, 0}};
  void add(char c) {
    s += c;
    cum.push_back(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(base * pows.back());
    }
  }
  array<int, 2> hash(int l, int r) {
    int len = r - l + 1;
    extend(len);
    return cum[r + 1] - cum[l] * pows[len];
  }
  bool operator==(HashRange &rhs) { return cum.back() == rhs.cum.back(); }
};
HashRange hr;
string st;
map<array<int, 2>, 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) {
    array<int, 2> 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;
}