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;
inline int read() {
  int s = 0, w = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
const int inf = 2e9 + 7;
double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
const double pi = acos(-1.0);
long long power(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
long long gcd(long long a, long long b) { return !b ? a : gcd(b, a % b); }
void add(long long& a, long long b) {
  a += b;
  ((a >= mod) && (a -= mod));
  ((a < 0) && (a += mod));
}
long long exgcd(long long a, long long b, long long& x, long long& y) {
  long long c;
  return !b ? (x = 1, y = 0, a)
            : (c = exgcd(b, a % b, y, x), y -= (a / b) * x, c);
}
long long INV(long long a) {
  long long x, y;
  exgcd(a, mod, x, y);
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
char s[N], t[N];
int dp[N], g[N];
class Pam {
 public:
  int sz, tot, last;
  int cnt[N], ch[N][26], len[N], fail[N], dif[N], slink[N];
  char s[N];
  int node(int l) {
    sz++;
    memset(ch[sz], 0, sizeof(ch[sz]));
    len[sz] = l;
    fail[sz] = cnt[sz] = 0;
    return sz;
  }
  void init() {
    sz = -1;
    last = 0;
    s[tot = 0] = '$';
    node(0);
    node(-1);
    fail[0] = 1;
  }
  int getfail(int x) {
    while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
    return x;
  }
  void insert(int c) {
    s[++tot] = c;
    int now = getfail(last);
    if (!ch[now][c]) {
      int x = node(len[now] + 2);
      fail[x] = ch[getfail(fail[now])][c];
      ch[now][c] = x;
      dif[x] = len[x] - len[fail[x]];
      if (dif[x] == dif[fail[x]])
        slink[x] = slink[fail[x]];
      else
        slink[x] = fail[x];
    }
    last = ch[now][c];
    cnt[last]++;
  }
  void addtimes() {
    for (int i = sz; i >= 2; --i) cnt[fail[i]] += cnt[i];
  }
  void work() {
    dp[0] = 1;
    int w = strlen(t + 1);
    for (int i = 1; i <= w; ++i) {
      insert(t[i] - 'a');
      for (int x = last; x > 1; x = slink[x]) {
        g[x] = dp[i - len[slink[x]] - dif[x]];
        if (dif[x] == dif[fail[x]]) g[x] = (g[x] + g[fail[x]]) % mod;
        if (i % 2 == 0) dp[i] = (dp[i] + g[x]) % mod;
      }
    }
    cout << dp[w];
  }
} pam;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s + 1;
  int w = strlen(s + 1);
  for (int i = 1; i <= w; ++i)
    t[i] = ((i & 1) ? s[(i + 1) / 2] : s[w + 1 - i / 2]);
  pam.init();
  pam.work();
}