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 LETTER = 26, MOD = 1000000007;
int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }
struct PAMNode {
  int fail, len, go[LETTER], slink, diff;
  PAMNode(int f = 0, int l = 0) : fail(f), len(l), go{}, slink(0), diff(0) {}
};
struct PAM {
  vector<PAMNode> a;
  vector<int> s;
  int last, n;
  int dp[1000200], sum[1000020];
  PAM() : a(0), s(1, -1), last(0), n(1) {
    a.emplace_back(1, 0);
    a.emplace_back(1, -1);
    dp[0] = 1;
  }
  int getFail(int v) {
    while (s[n - a[v].len - 2] != s[n - 1]) v = a[v].fail;
    return v;
  }
  int insert(int x) {
    s.push_back(x), n++;
    last = getFail(last);
    if (!a[last].go[x]) {
      a.emplace_back(a[getFail(a[last].fail)].go[x], a[last].len + 2);
      a.back().diff = a.back().len - a[a.back().fail].len;
      a.back().slink = a.back().diff == a[a.back().fail].diff
                           ? a[a.back().fail].slink
                           : a.back().fail;
      a[last].go[x] = (int)a.size() - 1;
    }
    return last = a[last].go[x];
  }
  void trans(int i) {
    for (int p = last; a[p].len > 0; p = a[p].slink) {
      sum[p] = dp[i - a[a[p].slink].len - a[p].diff];
      if (a[p].diff == a[a[p].fail].diff) sum[p] = add(sum[p], sum[a[p].fail]);
      if (i % 2 == 0) dp[i] = add(dp[i], sum[p]);
    }
  }
} pam;
int main() {
  string s;
  deque<char> deq;
  char ch = getchar();
  while (isalpha(ch)) {
    deq.push_back(ch);
    ch = getchar();
  }
  int tot = 0;
  while (!deq.empty()) {
    if (++tot & 1)
      s += deq.front(), deq.pop_front();
    else
      s += deq.back(), deq.pop_back();
  }
  for (int i = 0; i < (int)s.length(); ++i) {
    pam.insert(s[i] - 'a');
    pam.trans(i + 1);
  }
  printf("%d\n", pam.dp[pam.n - 1]);
  return 0;
}