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 palindromic_tree {
  static const int SIGMA = 26;
  struct Node {
    int len, link, slink, diff, to[SIGMA];
    long long cnt;
    Node(int len, int link = 0, int slink = -1, long long cnt = 1, int diff = 0)
        : len(len), link(link), slink(slink), cnt(cnt), diff(diff) {
      memset(to, 0, sizeof(to));
    }
  };
  vector<Node> ns;
  int last;
  palindromic_tree() : last(0) {
    ns.push_back(Node(-1));
    ns.push_back(Node(0));
  }
  void add(int i, string &s) {
    int p = last, c = s[i] - 'a';
    while (s[i - ns[p].len - 1] != s[i]) p = ns[p].link;
    if (ns[p].to[c]) {
      last = ns[p].to[c];
      ns[last].cnt++;
    } else {
      int q = ns[p].link;
      while (s[i - ns[q].len - 1] != s[i]) q = ns[q].link;
      q = max(1, ns[q].to[c]);
      last = ns[p].to[c] = int(ns.size());
      int sl, mydiff = ns[p].len + 2 - ns[q].len;
      if (mydiff == ns[q].diff)
        sl = ns[q].slink;
      else
        sl = q;
      ns.push_back(Node(ns[p].len + 2, q, sl, 1, mydiff));
    }
  }
};
int MOD = 1e9 + 7;
int sum(int a, int b) {
  int ans = a + b;
  if (ans >= MOD) ans -= MOD;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s, t;
  cin >> t;
  int n = int(t.size());
  for (int i = 0, ThxDem = int(t.size()); i < ThxDem; ++i) {
    if (i & 1)
      s.push_back(t[n - i / 2 - 1]);
    else
      s.push_back(t[i / 2]);
  }
  palindromic_tree p;
  vector<int> dp(n + 10), sdp(n + 10);
  dp[0] = 1;
  for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
    p.add(i, s);
    for (int v = p.last; v > 1; v = p.ns[v].slink) {
      int sl = p.ns[v].slink;
      sdp[v] = dp[i + 1 - (p.ns[sl].len + p.ns[v].diff)];
      if (p.ns[v].link != sl) {
        sdp[v] = sum(sdp[v], sdp[p.ns[v].link]);
      }
      dp[i + 1] = sum(dp[i + 1], sdp[v]);
    }
    if (i % 2 == 0) dp[i + 1] = 0;
  }
  cout << dp[n] << "\n";
}