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;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<pii>;
string s;
bool read() {
  if (!(cin >> s)) {
    return 0;
  }
  return 1;
}
const int mod = (int)1e9 + 7;
void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
void sub(int &a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
void kill(vi &v) {
  v.clear();
  v.shrink_to_fit();
}
struct gap_jumper {
  string s;
  vi value;
  int n;
  gap_jumper(string s_, int n_) {
    n = n_;
    value.resize(n + 1);
    s = s_;
    assert(int((s).size()) == 2 * n);
  }
  vi d_was;
  vvi next_, prev_, sum_;
  int get_id(int step) {
    int pos = find((d_was).begin(), (d_was).end(), step) - d_was.begin();
    if (pos != int((d_was).size())) return pos;
    d_was.push_back(step);
    next_.push_back(vi(2 * n)), prev_.push_back(vi(2 * n)),
        sum_.push_back(vi());
    sum_.back().reserve(n);
    vi &next = next_.back();
    vi &prev = prev_.back();
    for (int i = int(2 * n) - 1; i >= 0; --i) {
      if (i + step >= 2 * n)
        next[i] = 1;
      else
        next[i] = (s[i] != s[i + step] ? 1 : next[i + step] + 1);
    }
    for (int i = 0; i < int(2 * n); ++i) {
      if (i < step)
        prev[i] = 1;
      else
        prev[i] = (s[i] != s[i - step] ? 1 : prev[i - step] + 1);
    }
    return pos;
  }
  int first_left(int pos, int step, char what) {
    const int id = get_id(step);
    const vi &prev = prev_[id];
    if (what != s[pos]) return 0;
    return prev[pos];
  }
  int first_right(int pos, int step, char what) {
    const int id = get_id(step);
    const vi &next = next_[id];
    if (what != s[pos]) return 0;
    return next[pos];
  }
  int sum(int pos, int step, int len) {
    const int id = get_id(step);
    vi &sum = sum_[id];
    int to = pos + step * (len - 1);
    assert(0 <= pos && pos <= to && to < int((value).size()));
    while (int((sum).size()) <= to) {
      const int cur_id = int((sum).size());
      sum.push_back(value[cur_id]);
      if (cur_id >= step) add(sum.back(), sum[cur_id - step]);
    }
    int res = sum[to];
    if (pos - step >= 0) sub(res, sum[pos - step]);
    return res;
  }
  void purge(const vi &allowed) {
    vi to_del;
    for (int i = 0; i < int(int((d_was).size())); ++i) {
      const int id = d_was[i];
      if (!binary_search((allowed).begin(), (allowed).end(), id))
        to_del.push_back(i);
    }
    reverse((to_del).begin(), (to_del).end());
    for (int id : to_del) {
      d_was[id] = -1;
      kill(sum_[id]);
      kill(prev_[id]);
      kill(next_[id]);
    }
  }
};
struct prog {
  int start, diff, len;
  int get(int id) const { return start + diff * id; }
  int get_end() const { return start + diff * (len - 1); }
};
void relax(vector<prog> &v) {
  vector<prog> nv;
  for (const auto &pr : v) {
    if (pr.len == 0) continue;
    if (nv.empty())
      nv.push_back(pr);
    else {
      auto &top = nv.back();
      if (top.len == 1 && pr.len == 1)
        top = prog{top.start, pr.start - top.start, 2};
      else if (top.len == 1 && pr.start - top.start == pr.diff) {
        top = prog{top.start, pr.diff, pr.len + 1};
      } else if (pr.len == 1 && pr.start - top.get_end() == top.diff) {
        top.len++;
      } else if (pr.diff == top.diff && pr.start - top.get_end() == top.diff) {
        top.len += pr.len;
      } else {
        nv.push_back(pr);
      }
    }
  }
  v.swap(nv);
}
void incr_all(vector<prog> &v, int delta) {
  for (auto &pr : v) pr.start += delta;
}
void add_start(vector<prog> &v, int num) {
  assert(v.empty() || num < v.front().start);
  v.insert(v.begin(), prog{num, 1, 1});
}
void del(vector<prog> &v, const vi &who) {
  int ptr = 0;
  vector<prog> nv;
  for (const auto &pr : v) {
    int last_alive = 0;
    while (ptr < int((who).size()) && pr.start <= who[ptr] &&
           who[ptr] <= pr.get_end()) {
      assert((who[ptr] - pr.start) % pr.diff == 0);
      int cur_id = (who[ptr] - pr.start) / pr.diff;
      if (last_alive < cur_id)
        nv.push_back(prog{pr.get(last_alive), pr.diff, cur_id - last_alive});
      assert(last_alive <= cur_id);
      last_alive = cur_id + 1;
      ptr++;
    }
    const int total = pr.len;
    if (last_alive < total)
      nv.push_back(prog{pr.get(last_alive), pr.diff, total - last_alive});
  }
  v.swap(nv);
  relax(v);
}
void print(const vector<prog> &v) {
  for (const auto &pr : v) {
    for (int i = 0; i < int(pr.len); ++i)
      ;
    ;
  };
  ;
}
double time() { return (double)clock() / CLOCKS_PER_SEC; }
int work_old() {
  const int n = int((s).size()) / 2;
  assert(int((s).size()) == 2 * n);
  vi dp(n + 1);
  dp[0] = 1;
  vi pref;
  for (int len = 0; len < int(n + 1); ++len)
    if (len) {
      if (int((pref).size()) >= 50) return -1;
      const int l = n - len, r = n + len;
      vi npref;
      for (int i : pref) {
        if (s[l] == s[r - i - 2] && s[l + i + 1] == s[r - 1] && i + 2 <= len)
          npref.push_back(i + 2);
      }
      if (s[l] == s[r - 1]) npref.push_back(1);
      if (len >= 2 && s[l] == s[r - 2] && s[l + 1] == s[r - 1])
        npref.push_back(2);
      pref = npref;
      for (int i : pref) add(dp[len], dp[len - i]);
    }
  return dp[n];
}
void solve() {
  const int n = int((s).size()) / 2;
  assert(int((s).size()) == 2 * n);
  int ans = work_old();
  if (ans != -1) {
    cout << ans << endl;
    return;
  }
  gap_jumper info(s, n);
  vi dp(n + 1);
  dp[0] = 1;
  info.value[0] = 1;
  vector<prog> pref;
  for (int len = 0; len < int(n + 1); ++len)
    if (len) {
      const int l = n - len, r = n + len;
      vi to_del;
      for (const auto &pr : pref) {
        for (int i = 0; i < pr.len;) {
          int cur = pr.get(i);
          const int left_steps = info.first_left(r - cur - 2, pr.diff, s[l]);
          const int right_steps =
              info.first_right(l + cur + 1, pr.diff, s[r - 1]);
          const int steps = min(left_steps, right_steps);
          i += steps;
          if (i >= pr.len) break;
          cur = pr.get(i);
          assert(!(s[l] == s[r - cur - 2] && s[l + cur + 1] == s[r - 1]));
          to_del.push_back(cur);
          i++;
        }
      }
      if (!pref.empty() && pref.back().get_end() == len - 1 &&
          !count((to_del).begin(), (to_del).end(), len - 1))
        to_del.push_back(len - 1);
      del(pref, to_del);
      incr_all(pref, 2);
      if (len >= 2 && s[l] == s[r - 2] && s[l + 1] == s[r - 1])
        add_start(pref, 2);
      if (s[l] == s[r - 1]) add_start(pref, 1);
      relax(pref);
      assert(int((pref).size()) <= 20);
      for (const auto &pr : pref) {
        int start = len - pr.get_end();
        int cur_sum = info.sum(start, pr.diff, pr.len);
        add(dp[len], cur_sum);
      }
      vi allowed;
      for (const auto &pr : pref) allowed.push_back(pr.diff);
      sort((allowed).begin(), (allowed).end());
      allowed.resize(unique((allowed).begin(), (allowed).end()) -
                     allowed.begin());
      info.value[len] = dp[len];
    }
  cout << dp[n] << endl;
}
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  while (read()) {
    solve();
  }
  return 0;
}