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;
char c[2000010], a[2000010];
const int mod = 1e9 + 7;
int n, tot, last, top[2000010], diff[2000010], ans[2000010], f[2000010];
struct PT {
  int ch[26], len, fa;
} tr[2000010];
void init() {
  tr[++tot].len = -1;
  tr[0].fa = tr[1].fa = 1;
  top[0] = 1;
}
void insert(int now, int c) {
  int x = last;
  while (a[now] != a[now - tr[x].len - 1]) x = tr[x].fa;
  if (!tr[x].ch[c]) {
    int nx = ++tot, k = tr[x].fa;
    tr[nx].len = tr[x].len + 2;
    while (a[now] != a[now - tr[k].len - 1]) k = tr[k].fa;
    tr[nx].fa = tr[k].ch[c];
    tr[x].ch[c] = tot;
    diff[nx] = tr[nx].len - tr[tr[nx].fa].len;
    if (diff[nx] == diff[tr[nx].fa])
      top[nx] = top[tr[nx].fa];
    else
      top[nx] = tr[nx].fa;
  }
  last = tr[x].ch[c];
}
int main() {
  scanf("%s", c + 1);
  int len = strlen(c + 1);
  for (int i = 1; i <= len; i++) {
    if (i & 1)
      a[i] = c[(i + 1) / 2];
    else
      a[i] = c[(len - i / 2 + 1)];
  }
  init();
  ans[0] = 1;
  for (int i = 1; i <= len; i++) {
    insert(i, a[i] - 'a');
    int x = last;
    for (; x; x = top[x]) {
      f[x] = ans[i - tr[top[x]].len - diff[x]];
      if (top[x] != tr[x].fa) f[x] = (f[x] + f[tr[x].fa]) % mod;
      if (i % 2 == 0) ans[i] = (ans[i] + f[x]) % mod;
    }
  }
  cout << ans[len];
}