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;
struct PalindromicTree {
  struct node {
    int nxt[30], len, st, en, link, diff, slink, cnt, oc;
  };
  string s;
  vector<node> t;
  int sz, last;
  PalindromicTree() {}
  PalindromicTree(string _s) {
    s = _s;
    int n = s.size();
    t.clear();
    t.resize(n + 9);
    sz = 2, last = 2;
    t[1].len = -1, t[1].link = 1;
    t[1].diff = t[2].diff = 0;
    t[2].len = 0, t[2].link = 1;
    t[1].slink = 1;
    t[2].slink = 2;
  }
  int extend(int pos) {
    int cur = last, curlen = 0;
    int ch = s[pos] - 'a';
    while (1) {
      curlen = t[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
      cur = t[cur].link;
    }
    if (t[cur].nxt[ch]) {
      last = t[cur].nxt[ch];
      t[last].oc++;
      return 0;
    }
    sz++;
    last = sz;
    t[sz].oc = 1;
    t[sz].len = t[cur].len + 2;
    t[cur].nxt[ch] = sz;
    t[sz].en = pos;
    t[sz].st = pos - t[sz].len + 1;
    if (t[sz].len == 1) {
      t[sz].link = 2;
      t[sz].cnt = 1;
      t[sz].diff = 1;
      t[sz].slink = 2;
      return 1;
    }
    while (1) {
      cur = t[cur].link;
      curlen = t[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
        t[sz].link = t[cur].nxt[ch];
        break;
      }
    }
    t[sz].cnt = 1 + t[t[sz].link].cnt;
    t[sz].diff = t[sz].len - t[t[sz].link].len;
    if (t[sz].diff == t[t[sz].link].diff)
      t[sz].slink = t[t[sz].link].slink;
    else
      t[sz].slink = t[sz].link;
    return 1;
  }
  void calc_orrurrences() {
    for (int i = sz; i >= 3; i--) t[t[i].link].oc += t[i].oc;
  }
};
int dp[4000005], series_ans[4000005], par[4000005];
void solve() {
  string s, t, st;
  int n;
  cin >> s;
  n = s.size();
  for (int i = 0; i < n / 2; i++) {
    st.push_back(s[i]);
    st.push_back(s[n - i - 1]);
  }
  PalindromicTree pal(st);
  dp[0] = 1;
  for (int i = 1; i <= st.size(); i++) {
    dp[i] = 0;
    pal.extend(i - 1);
    for (int v = pal.last; pal.t[v].len > 0; v = pal.t[v].slink) {
      series_ans[v] = dp[i - pal.t[pal.t[v].slink].len - pal.t[v].diff];
      if (pal.t[v].diff == pal.t[pal.t[v].link].diff) {
        if (pal.t[v].diff == pal.t[pal.t[v].link].diff)
          series_ans[v] =
              (series_ans[v] + series_ans[pal.t[v].link]) % 1000000007;
      }
    }
    if (i % 2 == 0)
      for (int v = pal.last; pal.t[v].len > 0; v = pal.t[v].slink) {
        dp[i] = (dp[i] + series_ans[v]) % 1000000007;
      }
  }
  cout << dp[st.size()] << endl;
  int i = st.size();
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}