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 state {
  state *p, *go[27], *slink;
  int len, diff, dp;
  state() {}
  state(int length, state *fail)
      : p(fail), slink(0), len(length), diff(0), dp(0) {
    memset(go, 0, sizeof go);
  }
  void setDiff(int x) {
    diff = x;
    if (diff == p->diff)
      slink = p->slink;
    else
      slink = p;
  }
} pool[1100001];
int tot = 0;
inline state *new_state(int length, state *fail) {
  return &(pool[tot++] = state(length, fail));
}
struct PAM {
  state *oroot, *eroot, *last;
  char s[1100001];
  int length;
  PAM()
      : oroot(new_state(-1, pool)),
        eroot(new_state(0, oroot)),
        last(eroot),
        length(0) {
    oroot->setDiff(0);
    eroot->setDiff(0);
  }
  static int ID(char x) { return x - 'a'; }
  void extend(char ch) {
    int x = ID(s[++length] = ch);
    state *p = last;
    while (s[length - p->len - 1] != ch) p = p->p;
    if (p->go[x]) {
      last = p->go[x];
      return;
    } else
      p->go[x] = new_state(p->len + 2, 0);
    state *q = last = p->go[x];
    p = p->p;
    while (s[length - p->len - 1] != ch) p = p->p;
    q->p = (q->len == 1 ? eroot : p->go[x]);
    q->setDiff(q->len - q->p->len);
  }
};
const int mod = 1e9 + 7;
inline void add(int &a, int b) {
  if ((a += b) >= mod) a -= mod;
}
char t[1100001], s[1100001];
int n, dp[1100001];
int main() {
  scanf("%s", t + 1);
  n = strlen(t + 1);
  for (int i = 1, j = n, k = 1; i < j; i++, j--, k += 2)
    s[k] = t[i], s[k + 1] = t[j];
  PAM pam;
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    pam.extend(s[i]);
    for (state *T = pam.last; T->len > 0; T = T->slink) {
      T->dp = dp[i - T->slink->len - T->diff];
      if (T->diff == T->p->diff) add(T->dp, T->p->dp);
      if (i % 2 == 0) add(dp[i], T->dp);
    }
  }
  printf("%d\n", dp[n]);
}