#include <bits/stdc++.h>
using namespace std;
const int p = 90000007;
const long long MOD = 51123987;
string nap1, nap2;
int n;
void prepare(vector<int>& H, vector<int>& P, string nap) {
  P[0] = 1;
  for (int i = 1; i < n + 1; ++i) P[i] = P[i - 1] * p;
  H[n] = 0;
  for (int i = n - 1; i >= 0; --i) H[i] = H[i + 1] * p + nap[i];
}
int Hasz(vector<int>& H, vector<int>& P, int l, int p) {
  return H[l] - P[p - l + 1] * H[p + 1];
}
void Nieparz(vector<int>& H1, vector<int>& H2, vector<int>& P,
             vector<long long>& nieparz) {
  for (int i = 0; i < n; ++i) {
    int le = 1, pr = min(i + 1, n - i), s, r = 0;
    while (le <= pr) {
      s = (le + pr) / 2;
      if (Hasz(H1, P, i, i + s - 1) ==
          Hasz(H2, P, n - i - 1, n - i - 1 + s - 1)) {
        r = s;
        le = s + 1;
      } else
        pr = s - 1;
    }
    nieparz[i] = r;
  }
}
void Parz(vector<int>& H1, vector<int>& H2, vector<int>& P,
          vector<long long>& parz) {
  for (int i = 0; i < n; ++i) {
    int le = 1, pr = min(i + 1, n - (i + 1)), s, r = 0;
    while (le <= pr) {
      s = (le + pr) / 2;
      if (Hasz(H1, P, i + 1, i + s) ==
          Hasz(H2, P, n - i - 1, n - i - 1 + s - 1)) {
        r = s;
        le = s + 1;
      } else
        pr = s - 1;
    }
    parz[i] = r;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> nap1;
  nap2 = nap1;
  reverse(nap2.begin(), nap2.end());
  vector<int> H1(n + 1), H2(n + 1);
  vector<int> P(n + 1);
  prepare(H1, P, nap1);
  prepare(H2, P, nap2);
  vector<long long> parz(n), nieparz(n);
  Nieparz(H1, H2, P, nieparz);
  Parz(H1, H2, P, parz);
  vector<long long> pocz(n + 1, 0), kon(n + 1, 0);
  for (int i = 0; i < n; ++i) {
    long long L = i - nieparz[i] + 1;
    long long P = i;
    ++pocz[L];
    --pocz[P + 1];
    L = i - parz[i] + 1;
    P = i;
    if (parz[i] != 0) {
      ++pocz[L];
      --pocz[P + 1];
    }
    L = i;
    P = i + nieparz[i] - 1;
    ++kon[L];
    --kon[P + 1];
    L = i + 1;
    P = i + parz[i];
    if (parz[i] != 0) {
      ++kon[L];
      --kon[P + 1];
    }
  }
  for (int i = 1; i < n + 1; ++i) {
    pocz[i] = (pocz[i] + pocz[i - 1]) % MOD;
    kon[i] = (kon[i] + kon[i - 1]) % MOD;
  }
  long long odp;
  long long zle = 0;
  vector<long long> pref(n, 0);
  pref[0] = kon[0];
  for (int i = 1; i < n; ++i) pref[i] = (pref[i - 1] + kon[i]) % MOD;
  for (int i = 1; i < n; ++i) zle = (zle + pocz[i] * pref[i - 1]) % MOD;
  long long wsz = 0;
  for (int i = 0; i < n; ++i) wsz = (wsz + parz[i] + nieparz[i]) % MOD;
  odp = (wsz * (wsz - 1) / 2) % MOD - zle;
  if (odp < 0) odp += MOD;
  odp %= MOD;
  cout << odp;
  return 0;
}
