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 MAXN = 1000010;
const int MOD = 1e9 + 7;
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline void inc(int& a, int b) { a = add(a, b); }
struct PAM {
  struct node {
    int ch[26], fail, len, dif, anc;
  } t[MAXN];
  int totn, lst;
  inline int newnode(int nl) {
    int u = ++totn;
    t[u].len = nl;
    t[u].fail = t[u].dif = t[u].anc = 0;
    memset(t[u].ch, 0, sizeof t[u].ch);
    return u;
  }
  inline void reset() {
    totn = -1;
    newnode(0);
    newnode(-1);
    t[0].fail = 1;
    t[1].fail = 1;
    lst = 1;
  }
  char s[MAXN];
  inline int getFail(int u, int x) {
    while (s[x - t[u].len - 1] != s[x]) u = t[u].fail;
    return u;
  }
  int f[MAXN], g[MAXN];
  inline void extend(int c, int pos) {
    int cur = getFail(lst, pos);
    if (!t[cur].ch[c]) {
      int now = newnode(t[cur].len + 2);
      t[now].fail = t[getFail(t[cur].fail, pos)].ch[c];
      t[now].dif = t[now].len - t[t[now].fail].len;
      t[now].anc =
          t[now].dif == t[t[now].fail].dif ? t[t[now].fail].anc : t[now].fail;
      t[cur].ch[c] = now;
    }
    lst = t[cur].ch[c];
    for (int p = lst; p > 1; p = t[p].anc) {
      g[p] = f[pos - t[t[p].anc].len - t[p].dif];
      if (t[p].fail != t[p].anc) inc(g[p], g[t[p].fail]);
      if (!(pos & 1)) inc(f[pos], g[p]);
    }
  }
  inline void build(char* ns, int len) {
    for (int i = 1; i <= len; i++) s[i] = ns[i];
    reset();
    f[0] = 1;
    for (int i = 1; i <= len; i++) extend(s[i] - 'a', i);
  }
} S;
char s[MAXN], t[MAXN];
int main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  for (int i = 1; i <= (n >> 1); i++)
    t[(i << 1) - 1] = s[i], t[i << 1] = s[n - i + 1];
  S.build(t, n);
  printf("%d\n", S.f[n]);
  return 0;
}