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;
template <class T>
inline void read(T &x) {
  int f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const int mod = 1e9 + 7;
int fix(int x) { return x >= mod ? x - mod : x; }
const int N = 1e6 + 5;
namespace PAM {
int t[N][26], fa[N], anc[N], len[N], d[N];
int pos[N], sz, las;
void init(char s[], int n) {
  len[++sz] = -1, fa[1] = fa[0] = 1;
  for (int i = (1); i <= (n); i++) {
    int p = las, c = s[i] - 'a';
    for (; s[i - 1 - len[p]] != s[i]; p = fa[p])
      ;
    if (!t[p][c]) {
      int nw = ++sz, q = fa[p];
      for (; s[i - 1 - len[q]] != s[i]; q = fa[q])
        ;
      len[nw] = len[p] + 2;
      fa[nw] = t[q][c], t[p][c] = nw;
      d[nw] = len[nw] - len[fa[nw]];
      anc[nw] = (d[nw] == d[fa[nw]] ? anc[fa[nw]] : fa[nw]);
    }
    pos[i] = las = t[p][c];
  }
}
}  // namespace PAM
using namespace PAM;
char s[N], st[N];
int f[N], g[N], n;
int main() {
  scanf("%s", st + 1);
  n = strlen(st + 1);
  for (int i = 1, j = n, k = 1; i <= j; i++, j--)
    s[k++] = st[i], s[k++] = st[j];
  init(s, n), f[0] = 1;
  for (int i = (1); i <= (n); i++) {
    for (int u = pos[i]; len[u]; u = anc[u]) {
      g[u] = f[i - (len[anc[u]] + d[u])];
      if (d[u] == d[fa[u]]) g[u] = fix(g[u] + g[fa[u]]);
      if (!(i & 1)) f[i] = fix(f[i] + g[u]);
    }
  }
  cout << f[n] << endl;
  return 0;
}