ps

#define ll                       long long int
#define loop(i,a,b)              for(int i=(a);i<=(b);i++)
#define vi                       vector<ll>
#define mod                      1000000007

class Solution {
public:

vi pre,suf;
ll binpow(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
bool check (ll i,ll j, ll len, ll n) {
    ll left,right,pow_31=1;
    if (i-len+1 >= 0 && j+len <= n) {
        if (i-len+1 == 0) left = pre[i];
        else {
            left = pre[i] - pre[i-len];
            pow_31 = binpow(31,i-len+1,mod);
            left = left*binpow(pow_31,mod-2,mod);
            left %= mod;
        }
        if (j+len == n) right = suf[j];
        else {
            right = suf[j] - suf[j+len];
            pow_31 = binpow(31,(n-j-len),mod);
            right = right*binpow(pow_31,mod-2,mod);
            right %= mod;
        }
        if (left == right)
            return true;
    }
    return false;
}

int countSubstrings(string s) {
    ll n = s.size(),pow_31=31,ans=0;
    pre.assign(n,0), suf.assign(n,0);
    pre[0] = s[0] - 'a'+1;
    suf[n-1] = s[n-1] - 'a'+1;
    loop (i,1,n-1) {
        pre[i] = pow_31*(s[i] - 'a' + 1) + pre[i-1];
        pre[i] %= mod;
        suf[n-i-1] = pow_31*(s[n-i-1] - 'a' + 1) + suf[n-i];
        suf[n-i-1] %= mod;
        pow_31 = pow_31*31;
        pow_31 %= mod;
    }
    loop (i,0,n-1) {
        ll l = 0,r=n,a=0;
        while (r >= l) {
            ll mid = l + (r-l)/2;
            if (check(i-1,i+1,mid,n))
                a=mid,l = mid+1;
            else
                r = mid-1;
        }
        ans += (a+1);
        //cout << l << " ";
    }
    //cout << ans << " ";

    loop (i,0,n-1) {
        ll l = 0,r=n,a=0;
        while (r > l+1) {
            ll mid = l + (r-l)/2;
            if (check(i-1,i,mid,n))
               a=mid, l = mid+1;
            else
                r = mid-1;
        }
        ans += a;
    }
    //cout << ans << " ";
    return ans;
}

};