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 abc = 26, mod = 1e9 + 7, maxn = 1e6 + 79;
string s, a;
void add(int& a, const int& b) {
  a += b;
  if (a >= mod) a -= mod;
}
vector<int> slinkdp(maxn, 0), dp(maxn, 0);
class palindromic_tree {
 public:
  class node {
   public:
    int link, slink, len, dif;
    vector<int> s;
    node() : link(0), len(0), slink(0), dif(0), s(vector<int>(26, -1)) {}
  };
  vector<node> t;
  int size, last;
  palindromic_tree() : t(vector<node>(maxn)), size(2), last(0) {
    t[0].len = -1;
  }
  void add(int pos) {
    int v = last;
    for (;; v = t[v].link)
      if (pos - t[v].len - 1 >= 0 && a[pos] == a[pos - t[v].len - 1]) break;
    if (t[v].s[a[pos]] != -1) {
      last = t[v].s[a[pos]];
      return;
    }
    int nw = size++;
    t[v].s[a[pos]] = nw;
    t[nw].len = t[v].len + 2;
    last = nw;
    if (t[nw].len == 1) {
      t[nw].link = t[nw].slink = t[nw].dif = 1;
      return;
    }
    for (v = t[v].link; v; v = t[v].link)
      if (pos - t[v].len - 1 >= 0 && a[pos] == a[pos - t[v].len - 1]) break;
    t[nw].link = t[v].s[a[pos]];
    t[nw].dif = t[nw].len - t[t[nw].link].len;
    if (t[nw].dif != t[t[nw].link].dif)
      t[nw].slink = t[nw].link;
    else
      t[nw].slink = t[t[nw].link].slink;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  for (int i = 0; i < s.size() / 2; i++)
    a.push_back(s[i] - 'a'), a.push_back(s[s.size() - 1 - i] - 'a');
  dp[0] = 1;
  palindromic_tree p;
  for (int i = 0; i < a.size(); i++) {
    p.add(i);
    for (int j = p.last; j > 1; j = p.t[j].slink) {
      slinkdp[j] = dp[1 + i - (p.t[p.t[j].slink].len + p.t[j].dif)];
      if (p.t[j].dif == p.t[p.t[j].link].dif)
        add(slinkdp[j], slinkdp[p.t[j].link]);
      add(dp[i + 1], slinkdp[j]);
    }
    dp[i + 1] *= (i & 1);
  }
  cout << dp[a.size()] << "\n";
  return 0;
}