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 mo = 1e9 + 7;
template <typename _T>
_T Fabs(_T x) {
  return x > 0 ? x : -x;
}
template <typename _T>
void read(_T &x) {
  _T f = 1;
  x = 0;
  char s = getchar();
  while ('0' > s || '9' < s) {
    if (s == '-') f = -1;
    s = getchar();
  }
  while ('0' <= s && s <= '9') {
    x = (x << 3) + (x << 1) + (s ^ 48);
    s = getchar();
  }
  x *= f;
}
char str[1000100], astr[1000100];
int dp[1000100], g[1000100], n;
struct ming {
  int ch[30], len, fail, siz, eail, dif;
};
int add(int x, int y) { return x + y < mo ? x + y : x + y - mo; }
class PAM {
 public:
  ming a[1000100];
  int tot, las;
  int getfail(int x, int pos) {
    while (str[pos - a[x].len - 1] != str[pos]) x = a[x].fail;
    return x;
  }
  void init() {
    a[1].len = -1;
    a[0].fail = a[1].fail = 1;
    tot = 1;
    las = 0;
  }
  void extend(int x, int p) {
    int cur = getfail(las, p), now = a[cur].ch[x];
    if (!now) {
      now = ++tot;
      a[now].len = a[cur].len + 2;
      a[now].fail = a[getfail(a[cur].fail, p)].ch[x];
      a[cur].ch[x] = now;
      a[now].dif = a[now].len - a[a[now].fail].len;
      if (a[now].dif == a[a[now].fail].dif)
        a[now].eail = a[a[now].fail].eail;
      else
        a[now].eail = a[now].fail;
    }
    a[las = now].siz++;
    while (now > 1) {
      g[now] = dp[p - a[a[now].eail].len - a[now].dif];
      if (a[now].eail != a[now].fail) g[now] = add(g[now], g[a[now].fail]);
      if (!(p & 1)) dp[p] = add(dp[p], g[now]);
      now = a[now].eail;
    }
  }
} T;
signed main() {
  scanf("%s", str + 1);
  n = (int)strlen(str + 1);
  int l = 1, r = n, id = 0;
  while (l <= r) astr[++id] = str[l++], astr[++id] = str[r--];
  T.init();
  for (int i = 1; i <= n; i++) str[i] = astr[i];
  dp[0] = 1;
  for (int i = 1; i <= n; i++) T.extend(str[i] - 'a', i);
  printf("%d\n", dp[n]);
  return 0;
}