Single_Hash_Palindrome

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
const int MAX = 1e6 + 10;
const int MOD = 1e9 + 7;
const ll base = 31;
ll p[MAX], rev_p[MAX], hsh[MAX], rev_hsh[MAX];
 
ll InverseMod(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res % MOD;
}
 
void pre() {
  p[0] = 1;
  rev_p[0] = 1;
  ll rev_base = InverseMod(base, MOD - 2);
  for (int i = 1; i < MAX; i++) {
    p[i] = p[i - 1] * base % MOD;
    rev_p[i] = rev_p[i - 1] * rev_base % MOD;
  }
}
 
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
 
  pre();
 
  string s, ans;
  cin >> s;
 
  int n = s.size();
 
  for (int i = 0; i < n; i++) {
    hsh[i + 1] = (hsh[i] + ((s[i] - 'a' + 1) * p[i]) % MOD) % MOD;
  }
 
  for(int i = n-1, j = 0; i >= 0; i--, j++){
    rev_hsh[j + 1] = (rev_hsh[j] + ((s[i]-'a' + 1) * p[j]) % MOD) % MOD;
  }
 
  int ans = 0;
 
  for(int i = 1; i <= n; i++){
    for(int j = 0; j < n; j++){
        int L = j;
        int R = j+i-1;
        ll pre_hash = (hsh[R+1]-hsh[L]+MOD)%MOD;
        pre_hash = (pre_hash * rev_p[L])%MOD;
        ll suf_hash = (rev_hsh[n-L]-rev_hsh[n-R-1]+MOD)%MOD;
        suf_hash = (suf_hash * rev_p[n-R-1])%MOD;
        if(pre_hash == suf_hash){
            ans++;
        }
    }
  }
 
  cout << ans << '\n';
 
  return 0;
}