Untitled

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const long long int MOD = 1e9+7;
const int b = 47;
 
vector<long long int> h;
vector<long long int>h2;
vector<long long int> pw;
 
int sub(int a, int b) {
    if (a - b < 0) {
        return a - b + MOD;
    } else {
        return a - b;
    }
}
 
int add(int a, int b) {
    if (a + b >= MOD) {
        return a + b - MOD;
    } else {
        return a + b;
    }
}
 
long long int mul(int a, int b) {
    return 1ll * a * b % MOD;
}
 
void power(int n) {
    pw.push_back(1);
    for (int i=1; i <= n; i++) {
        pw.push_back(mul(pw[i-1], b));
    }
}
 
void build_hash(string &s) {
    h.push_back(0);
    for (int i=1; i <= s.size(); i++) {
        h.push_back(add(mul(h[i - 1], b), (s[i - 1] - 'a' + 1)));
    }
    reverse(s.begin(), s.end());
    h2.push_back(0);
    for (int i=1; i <= s.size(); i++) {
        h2.push_back(add(mul(h2[i - 1], b), (s[i - 1] - 'a' + 1)));
    }
}
 
int get_hash(int l, int r, bool f) {
    if (f) return sub(h[r], mul(h[l], pw[r - l]));
    if (!f) return sub(h2[r], mul(h2[l], pw[r - l]));
}
 
int main() {
    string s;
    long long l, r, mid, c = 0;
    cin >> s;
    build_hash(s);
    power(s.size() + 2);
    for (int i=1; i < s.size(); i++) {
        l = 0;
        r = min(i+1, (int)s.size() - i);
        while (l + 1 < r) {
            mid = (l + r) / 2;
            if (get_hash(i-mid, i+1, 1) == get_hash(s.size() - mid - i - 1, s.size() - i, 0)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        c += l;
    }
    for (int i=0; i < s.size(); i++) {
        l = 0;
        r = min(i+1, (int)s.size() - i - 1) + 1;
        while (l + 1 < r) {
            mid = (l + r) / 2;
            if (get_hash(i - mid + 1, i + 1, 1) == get_hash(s.size() - i - 1 - mid,s.size() - i - 1,  0)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        c += l;
    }
    cout << c + s.size();
    return 0;
}