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 long long mod = 1000000007;
int n;
long long ans[1000005], g[1000005];
char a[1000005], s[1000005];
struct PAM {
  int s[1000005], n;
  int root, las, ndsum;
  int ch[1000005][26], fail[1000005], len[1000005], pre[1000005], dif[1000005];
  void init() {
    fail[0] = pre[0] = 1;
    fail[1] = 1;
    len[1] = -1;
    pre[0] = 1;
    s[0] = 26;
    ndsum = 1;
    las = 0;
  }
  int getfail(int x) {
    while (s[n] != s[n - len[x] - 1]) x = fail[x];
    return x;
  }
  void add_pam(int w) {
    s[++n] = w;
    int tmp = getfail(las);
    if (!ch[tmp][w]) {
      int x = ++ndsum;
      len[x] = len[tmp] + 2;
      fail[x] = ch[getfail(fail[tmp])][w];
      ch[tmp][w] = x;
      dif[x] = len[x] - len[fail[x]];
      pre[x] = (dif[x] == dif[fail[x]]) ? pre[fail[x]] : fail[x];
    }
    las = ch[tmp][w];
  }
} pam;
int main() {
  scanf("%s", a + 1);
  n = strlen(a + 1);
  for (int i = 1; i <= n; ++i) s[i] = i % 2 ? a[i / 2 + 1] : a[n - i / 2 + 1];
  pam.init();
  ans[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pam.add_pam(s[i] - 'a');
    for (int j = pam.las; j; j = pam.pre[j]) {
      g[j] = ans[i - pam.len[pam.pre[j]] - pam.dif[j]];
      if (pam.pre[j] != pam.fail[j]) g[j] = (g[j] + g[pam.fail[j]]) % mod;
      if (i % 2 == 0) ans[i] = (ans[i] + g[j]) % mod;
    }
  }
  printf("%d\n", ans[n]);
  return 0;
}