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 = 1e9;
const long long inf64 = 1e18;
const int mod = inf + 7;
inline int _sum(int a, int b) { return a + b < mod ? a + b : a + b - mod; }
inline int _mul(int a, int b) { return (1ll * a * b) % mod; }
inline int _sub(int a, int b) { return a >= b ? a - b : a - b + mod; }
inline void _inc(int& x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}
inline void _dec(int& x, int y) {
  if ((x -= y) < 0) {
    x += mod;
  }
}
inline int _binpow(int x, int pw) {
  int res = 1;
  int tmp = x;
  while (pw > 0) {
    if (pw & 1) {
      res = _mul(res, tmp);
    }
    tmp = _mul(tmp, tmp);
    pw >>= 1;
  }
  return res;
}
inline int _div(int a, int b) { return _mul(a, _binpow(b, mod - 2)); }
void read(string& s) { cin >> s; }
void gen(string& s) {
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
  int n = 2 * (rnd() % 3 + 1);
  s.resize(n, '?');
  for (int i = 0; i < n; i++) {
    s[i] = rnd() % 5 == 0 ? 'a' : 'b';
  }
}
string join_halfs(string s) {
  int n = (int)s.size();
  string t;
  for (int i = 0; i < n / 2; i++) {
    t.push_back(s[i]);
    t.push_back(s[n - 1 - i]);
  }
  return t;
}
int slow(string s) {
  s = join_halfs(s);
  int n = (int)s.size();
  s = "#" + s;
  vector<int> dp(n + 1);
  dp[0] = 1;
  cout << s << "\n";
  for (int i = 1; i <= n; i++) {
    for (int j = i; j >= 1; j--) {
      if ((i - j + 1) % 2) continue;
      string hlp = s.substr(j, i - j + 1);
      string rhlp = hlp;
      reverse(rhlp.begin(), rhlp.end());
      if (hlp == rhlp) {
        _inc(dp[i], dp[j - 1]);
      }
    }
  }
  return dp[n];
}
const int N = 2e6 + 5;
struct Node {
  map<int, int> nxt;
  int link = -1;
  int dp = 0;
  int slink = -1;
  int len = 0;
  int diff = 0;
  Node() = default;
};
Node t[N];
int sz, max_suff;
int fast(string s) {
  {
    sz = 0;
    t[sz++] = Node();
    t[sz++] = Node();
    max_suff = 1;
    t[0].link = 1;
    t[1].link = 0;
    t[0].len = -1;
    t[1].len = 0;
  }
  int n = (int)s.size();
  s = "#" + join_halfs(s);
  vector<int> dp(n + 1);
  dp[0] = 1;
  max_suff = 1;
  for (int i = 1; i <= n; i++) {
    {
      while (s[i] != s[i - t[max_suff].len - 1]) {
        max_suff = t[max_suff].link;
      }
      if (!t[max_suff].nxt.count(s[i])) {
        t[sz++] = Node();
        t[sz - 1].len = t[max_suff].len + 2;
        int next_max_suff = t[max_suff].link;
        while (s[i] != s[i - t[next_max_suff].len - 1]) {
          next_max_suff = t[next_max_suff].link;
        }
        t[sz - 1].link =
            t[next_max_suff].nxt.count(s[i]) ? t[next_max_suff].nxt[s[i]] : 1;
        t[sz - 1].diff = t[sz - 1].len - t[t[sz - 1].link].len;
        if (t[sz - 1].diff == t[t[sz - 1].link].diff) {
          t[sz - 1].slink = t[t[sz - 1].link].slink;
        } else {
          t[sz - 1].slink = t[sz - 1].link;
        }
        t[max_suff].nxt[s[i]] = sz - 1;
      }
      max_suff = t[max_suff].nxt[s[i]];
    }
    for (int x = max_suff; t[x].len > 0; x = t[x].slink) {
      {
        int j = i - t[t[x].slink].len - t[x].diff;
        t[x].dp = dp[j];
      }
      if (t[x].diff == t[t[x].link].diff) {
        _inc(t[x].dp, t[t[x].link].dp);
      }
      if (i % 2 == 0) {
        _inc(dp[i], t[x].dp);
      }
    }
  }
  return dp[n];
}
void WORK() {
  string s;
  read(s);
  cout << fast(s) << "\n";
}
void TEST() {
  while (1) {
    string s;
    gen(s);
    cout << "s = " << s << endl;
    int sl = slow(s);
    int fs = fast(s);
    if (sl == fs) {
      cout << "OK (" << fs << ")" << endl;
    } else {
      cout << "WA" << endl;
      cout << "exp = " << sl << endl;
      cout << "fnd = " << fs << endl;
      break;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  WORK();
  return 0;
}