#include <bits/stdc++.h>
using namespace std;
const int MOD = 51123987;
void manacher(const string &s, vector<int> &p) {
  int n = s.length();
  int mx = -1, id = -1;
  for (int i = 0; i < n; ++i) {
    if (mx > i)
      p[i] = min(p[2 * id - i], mx - i);
    else
      p[i] = 1;
    while (i + p[i] < n && i - p[i] >= 0 && s[i - p[i]] == s[i + p[i]]) ++p[i];
    if (i + p[i] > mx) {
      mx = p[i] + i;
      id = i;
    }
  }
}
long long solve(vector<int> &p) {
  int n = p.size() / 2;
  vector<long long> lp(n + 1, 0), rp(n + 1, 0);
  for (int i = 0; i < n; ++i) {
    int t = (p[i * 2 + 1] + 1) >> 1;
    ++lp[i - t + 1], --lp[i + 1];
    ++rp[i], --rp[i + t];
    t = p[i * 2 + 2] >> 1;
    ++lp[i - t + 1], --lp[i + 1];
    ++rp[i + 1], --rp[i + t + 1];
  }
  vector<long long> cntl(n + 1, 0), cntr(n + 1, 0), sum(n + 1, 0);
  cntl[0] = lp[0];
  cntr[0] = rp[0];
  for (int i = 1; i <= n; ++i) {
    cntl[i] = cntl[i - 1] + lp[i];
    cntr[i] = cntr[i - 1] + rp[i];
    sum[i] = (sum[i - 1] + cntr[i - 1]) % MOD;
  }
  long long ans = sum[n] * (sum[n] - 1) / 2 % MOD;
  for (int i = 0; i < n; ++i) ans = (ans - sum[i] * cntl[i]) % MOD;
  return (ans + MOD) % MOD;
}
int main() {
  int n;
  string t;
  cin >> n >> t;
  string s(2 * n + 1, '#');
  for (int i = 0; i < n; ++i) s[2 * i + 1] = t[i];
  vector<int> p(2 * n + 1, 0);
  manacher(s, p);
  cout << solve(p) << endl;
  return 0;
}
