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>
char zf[1000010];
int fa[1000010], trs[1000010][26], len[1000010], la = 1, sl = 2, tp[1000010],
                                                 cz[1000010];
int insert(int i, char c) {
  int x = int(c - 'a');
  while (i - len[la] - 1 <= 0 || zf[i - len[la] - 1] != c) la = fa[la];
  if (trs[la][x]) {
    la = trs[la][x];
    return la;
  }
  int w = trs[la][x] = ++sl, t = fa[la];
  len[w] = len[la] + 2;
  while (t &&
         (trs[t][x] == 0 || i - len[t] - 1 <= 0 || zf[i - len[t] - 1] != c))
    t = fa[t];
  if (trs[t][x]) {
    int f = trs[t][x];
    cz[w] = len[w] - len[f];
    if (cz[w] == cz[f])
      tp[w] = tp[f];
    else
      tp[w] = f;
    fa[w] = f;
  } else {
    tp[w] = fa[w] = 2;
    cz[w] = len[w];
  }
  return la = w;
}
char sr[1000010];
int dp[1000010], he[1000010], wz[1000010];
int main() {
  len[1] = -1;
  fa[2] = tp[2] = 1;
  scanf("%s", sr);
  int n = strlen(sr);
  for (int i = 0; i < n / 2; i++) {
    zf[i * 2 + 1] = sr[i];
    zf[i * 2 + 2] = sr[n - 1 - i];
  }
  for (int i = 1; i <= n; i++) wz[i] = insert(i, zf[i]);
  dp[0] = 1;
  for (int i = 1; i <= n; i++) {
    int u = wz[i];
    while (u != 2) {
      he[u] = dp[i - len[tp[u]] - cz[u]];
      if (tp[u] != fa[u]) he[u] = (he[u] + he[fa[u]]) % 1000000007;
      if (i % 2 == 0) dp[i] = (dp[i] + he[u]) % 1000000007;
      u = tp[u];
    }
  }
  printf("%d", dp[n]);
  return 0;
}