#include <bits/stdc++.h>
using namespace std;
const int MOD = 51123987;
int n;
char dat[2000001];
vector<int> manacher(const string& s) {
  int r, p;
  r = p = -1;
  vector<int> a(s.size());
  for (int i = 0; i < s.size(); ++i) {
    if (r < i)
      a[i] = 0;
    else
      a[i] = min(r - i, a[2 * p - i]);
    while (i > a[i] && s[i - a[i] - 1] == s[i + a[i] + 1]) ++a[i];
    if (i + a[i] > r) r = i + a[i], p = i;
  }
  return a;
}
int main() {
  scanf("%d %s", &n, dat);
  string s(2 * n + 1, ' ');
  for (int i = 0; i < n; ++i) s[2 * i + 1] = dat[i];
  vector<int> a = manacher(s);
  long long ans = n;
  for (int t : a) ans += t / 2;
  ans %= MOD;
  ans = (ans * (ans - 1) / 2) % MOD;
  vector<long long> start(n + 1), finish(n + 1);
  for (int i = 0; i < a.size(); ++i) {
    start[(i - a[i]) / 2]++;
    start[(i - 1) / 2 + 1]--;
    finish[(i + a[i]) / 2]--;
    finish[i / 2]++;
  }
  for (int i = 1; i < n; ++i) {
    start[i] += start[i - 1];
    finish[i] += finish[i - 1];
  }
  for (int i = 1; i < n; ++i) finish[i] = (finish[i] + finish[i - 1]) % MOD;
  for (int i = 1; i < n; ++i) ans = (ans - start[i] * finish[i - 1]) % MOD;
  ans = (ans + MOD) % MOD;
  printf("%I64d\n", ans);
  return 0;
}
