HashString

#include<bits/stdc++.h>
using namespace std;

struct HashString
{
  const int BASE = 1e9 + 7;
  const int P = 127;

  string s;
  size_t n;

  vector<int> power;
  vector<int> phash;

  HashString(string ps): s(ps), n(ps.size()) { init(); }

  void init()
  {
    phash.assign(n + 1, 0);
    power.assign(n + 1, 1);
    for(size_t i=1; i<=n; ++i)
    {
      phash[i] = (1LL * phash[i-1] * P + s[i-1]) % BASE;
      power[i] = (1LL * power[i-1] * P) % BASE;
    }
  }

  /** hash, power */
  inline pair<int, size_t> sub_hash(int i, int j)
  {
    return { phash[j+1] - phash[i], j - i };
  }
};

bool isPrime(int x)
{
  int p=2;
  while(p * p <= x && x % p != 0) ++p;
  return ( x > 1 && p * p > x );
}

int max_len_preifx(const HashString &s1, const HashString &s2)
{
  int left = 0, right = min(s1.n, s2.n) + 1;
  while (right - left > 1)
  {
    int mid = (left + right) / 2;
    if ( s1.phash[mid] == s2.phash[mid] )
      left = mid;
    else
      right = mid;
  }
  return left;
}

int main()
{
  #ifdef AZHUKOV
  freopen("input.txt", "r", stdin);
  #endif // AZHUKOV

  string s;
  cin >> s;
  HashString s1(s);
  reverse(s.begin(), s.end());
  HashString s2(s);
  int n = s1.n;

  int ans = 0;
  for(int i=1; i<n-1; ++i)
  {
    /** чётная длина */
    int h1, h2, p1, p2;
    tie(h1, p1) = s2.sub_hash(n-1-i+1, n-1);
    tie(h2, p2) = s1.sub_hash(i, n-1);



  }
}