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 mod = 1000000007;
inline int add(int a, int b) {
  if ((a += b) >= mod) a -= mod;
  return a;
}
namespace PAM {
char buf[1000010];
class node {
 public:
  int fail, nxt[26], len, num, cnt, diff, anc;
};
class PAM {
 public:
  node t[1000010];
  int s[1000010];
  int nodecnt, last, n;
  int newnode(int l) {
    int p = nodecnt++;
    memset(t[p].nxt, 0, sizeof(t[p].nxt));
    t[p].num = t[p].cnt = 0;
    t[p].len = l;
    return p;
  }
  void init() {
    nodecnt = 0;
    newnode(0);
    newnode(-1);
    last = n = 0;
    s[n] = -1;
    t[0].fail = 1;
    t[0].anc = 1;
  }
  inline int getfail(int x) {
    while (s[n - t[x].len - 1] != s[n]) x = t[x].fail;
    return x;
  }
  void insert(int c) {
    s[++n] = c;
    int cur = getfail(last);
    if (!t[cur].nxt[c]) {
      int now = newnode(t[cur].len + 2);
      t[now].fail = t[getfail(t[cur].fail)].nxt[c];
      t[cur].nxt[c] = now;
      t[now].num = t[t[now].fail].num + 1;
      t[now].diff = t[now].len - t[t[now].fail].len;
      t[now].anc = (t[now].diff == t[t[now].fail].diff) ? t[t[now].fail].anc
                                                        : t[now].fail;
    }
    last = t[cur].nxt[c];
    ++t[last].cnt;
  }
  void count() {
    for (int i = nodecnt - 1; i > 0; i--) t[t[i].fail].cnt += t[i].cnt;
  }
} p;
}  // namespace PAM
int n;
char s[1000010], s2[1000010];
int f[1000010], g[1000010];
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  PAM::p.init();
  for (int i = 1; i <= n; i++) {
    if (i > n + 1 - i) break;
    s2[i * 2 - 1] = s[i];
    if (i != n + 1 - i) s2[i * 2] = s[n + 1 - i];
  }
  memcpy(s, s2, sizeof(s2));
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    PAM::p.insert(s[i] - 'a');
    int pos = PAM::p.last;
    for (int j = pos; j; j = PAM::p.t[j].anc) {
      g[j] = f[i - PAM::p.t[PAM::p.t[j].anc].len - PAM::p.t[j].diff];
      if (PAM::p.t[j].anc != PAM::p.t[j].fail)
        g[j] = add(g[j], g[PAM::p.t[j].fail]);
      if (!(i & 1)) f[i] = add(f[i], g[j]);
    }
  }
  printf("%d\n", f[n]);
  return 0;
}