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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXLEN = 1000000;
const int MOD = 1000000007;
const int MAXALPH = 26;
struct ETNode {
  int len, suff, idx, diff, slink;
  int nxt[MAXALPH];
  ETNode(int len, int suff, int idx) : len(len), suff(suff), idx(idx) {
    memset(nxt, -1, sizeof(nxt));
  }
};
struct EERTREE {
  int IMAG, ZERO, at;
  char *s;
  int idx;
  vector<ETNode> nodes;
  void init(char *_s) {
    s = _s;
    idx = 0;
    nodes.clear();
    IMAG = 0, ZERO = 1, at = ZERO;
    nodes.push_back(ETNode(-1, IMAG, -1));
    nodes.push_back(ETNode(0, IMAG, -1));
    nodes[IMAG].diff = -1, nodes[IMAG].slink = IMAG, nodes[ZERO].diff = -1,
    nodes[ZERO].slink = IMAG;
  }
  void grow() {
    while (s[idx] != s[idx - 1 - nodes[at].len]) at = nodes[at].suff;
    int x = s[idx] - 'a';
    if (nodes[at].nxt[x] == -1) {
      int suff = nodes[at].suff;
      while (s[idx] != s[idx - 1 - nodes[suff].len]) suff = nodes[suff].suff;
      int to = ((int)(nodes).size());
      nodes.push_back(ETNode(nodes[at].len + 2,
                             at == IMAG ? ZERO : nodes[suff].nxt[x], idx));
      nodes[to].diff = nodes[to].len - nodes[nodes[to].suff].len;
      nodes[to].slink = nodes[to].diff == nodes[nodes[to].suff].diff
                            ? nodes[nodes[to].suff].slink
                            : nodes[to].suff;
      nodes[at].nxt[x] = to;
    }
    at = nodes[at].nxt[x], ++idx;
  }
  void print(int at, int dep = 0) {
    for (int i = (0); i < (dep); ++i) printf("  ");
    printf("%d=", at);
    if (at == IMAG)
      printf("IMAG");
    else if (at == ZERO)
      printf("ZERO");
    else
      for (int i = (0); i < (nodes[at].len); ++i)
        printf("%c", s[nodes[at].idx - i]);
    printf(" [%d,%d,%d]\n", nodes[at].suff, nodes[at].diff, nodes[at].slink);
    for (int x = (0); x < (MAXALPH); ++x)
      if (nodes[at].nxt[x] != -1) print(nodes[at].nxt[x], dep + 1);
  }
  void print() {
    print(IMAG);
    print(ZERO);
  }
};
char s[MAXLEN + 1];
int slen;
char t[MAXLEN + 1];
EERTREE et;
int dp[MAXLEN + 1];
int sdp[MAXLEN + 2];
void inc(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
void run() {
  scanf("%s", s);
  slen = strlen(s);
  assert(slen % 2 == 0);
  for (int i = (0); i < (slen / 2); ++i)
    t[2 * i + 0] = s[i], t[2 * i + 1] = s[slen - i - 1];
  t[slen] = '\0';
  dp[0] = 1;
  et.init(t);
  for (int i = (0); i < (slen); ++i) {
    et.grow();
    dp[i + 1] = 0;
    for (int x = et.at; et.nodes[x].len > 0; x = et.nodes[x].slink) {
      sdp[x] = 0;
      inc(sdp[x],
          dp[i + 1 - et.nodes[et.nodes[x].slink].len - et.nodes[x].diff]);
      if (et.nodes[x].diff == et.nodes[et.nodes[x].suff].diff)
        inc(sdp[x], sdp[et.nodes[x].suff]);
      if ((i + 1) % 2 == 0) inc(dp[i + 1], sdp[x]);
    }
  }
  printf("%d\n", dp[slen]);
}
int main() {
  run();
  return 0;
}