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 alpha = 26;
typedef class TrieNode {
 public:
  int len, dif, g;
  TrieNode *ch[alpha];
  TrieNode *fail, *slink;
} TrieNode;
typedef class PalindromeTree {
 public:
  int len;
  TrieNode *pool;
  TrieNode *top;
  TrieNode *odd, *even;
  TrieNode *last;
  char *str;
  TrieNode *newnode(int len) {
    top->len = len, top->dif = -1, top->g = 0;
    memset(top->ch, 0, sizeof(top->ch));
    top->fail = top->slink = NULL;
    return top++;
  }
  PalindromeTree() {}
  PalindromeTree(int n) {
    pool = new TrieNode[(n + 5)];
    str = new char[(n + 5)];
    top = pool, len = 0;
    odd = newnode(-1), even = newnode(0);
    odd->fail = odd, even->fail = odd;
    odd->dif = even->dif = -1, last = even, str[0] = 0;
  }
  TrieNode *extend(TrieNode *p) {
    while (str[len - p->len - 1] != str[len]) p = p->fail;
    return p;
  }
  void append(char x) {
    str[++len] = x;
    int c = x - 'a';
    last = extend(last);
    if (!last->ch[c]) {
      TrieNode *p = newnode(last->len + 2);
      p->fail = extend(last->fail)->ch[c];
      if (!p->fail) p->fail = even;
      last->ch[c] = p;
      p->dif = p->len - p->fail->len;
      if (p->dif == p->fail->dif)
        p->slink = p->fail->slink;
      else
        p->slink = p->fail;
    }
    last = last->ch[c];
  }
} PalindromeTree;
const int M = 1e9 + 7;
int n;
char bstr[1000005], str[1000005];
PalindromeTree pt;
int *f;
inline void init() {
  gets(bstr + 1);
  n = strlen(bstr + 1);
  for (int i = 1; i <= n; i++) {
    if (i & 1)
      str[i] = bstr[(i + 1) >> 1];
    else
      str[i] = bstr[n - (i >> 1) + 1];
  }
  f = new int[(n + 1)];
  memset(f, 0, sizeof(int) * (n + 1));
}
inline void solve() {
  pt = PalindromeTree(n);
  f[0] = 1;
  for (int i = 1; i <= n; i++) {
    pt.append(str[i]);
    for (TrieNode *p = pt.last; p && p->len > 0; p = p->slink) {
      p->g = f[i - p->slink->len - p->dif];
      if (p->fail->dif == p->dif) p->g = (p->g + p->fail->g) % M;
      if (!(i & 1)) f[i] = (f[i] + p->g) % M;
    }
  }
  printf("%d", f[n]);
}
int main() {
  init();
  solve();
  return 0;
}