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;
int n, m, i, j, ch[1000005][27], fa[1000005], tp[1000005], sum[1000005],
    dp[1000005], df[1000005], len[1000005], lst, cnt, mod = 1e9 + 7;
string s, t;
int gtpre(int x, int i) {
  while (t[i - len[x] - 1] != t[i]) {
    x = fa[x];
  }
  return x;
}
void ins(int i) {
  lst = gtpre(lst, i);
  if (!ch[lst][t[i] - 'a']) {
    fa[++cnt] = ch[gtpre(fa[lst], i)][t[i] - 'a'];
    ch[lst][t[i] - 'a'] = cnt;
    len[cnt] = len[lst] + 2;
    df[cnt] = len[cnt] - len[fa[cnt]];
    if (df[cnt] == df[fa[cnt]])
      tp[cnt] = tp[fa[cnt]];
    else
      tp[cnt] = cnt;
  }
  lst = ch[lst][t[i] - 'a'];
  int x = lst;
  while (x) {
    sum[x] = dp[i - len[tp[x]]];
    if (tp[x] != x) (sum[x] += sum[fa[x]]) %= mod;
    if (!(i & 1)) (dp[i] += sum[x]) %= mod;
    x = fa[tp[x]];
  }
}
int main() {
  cnt = 1;
  fa[0] = 1;
  len[1] = -1;
  lst = 0;
  {
    static char ss[1000005];
    scanf(" %s", ss);
    (s) = ss;
  };
  t = s;
  for ((i) = 0; (i) < (s.length()); (i)++)
    if (!(i & 1))
      t[i] = s[i / 2];
    else
      t[i] = s[s.length() - i / 2 - 1];
  t = " " + t;
  s = t;
  dp[0] = 1;
  for ((i) = 1; (i) <= (s.length() - 1); (i)++) ins(i);
  cout << dp[s.length() - 1] << endl;
  return 0;
}