#include <bits/stdc++.h>
using namespace std;
const int N = 2001000;
const int S = 4001000;
char str[N];
char man[S];
int d[S];
int l[N];
int r[N];
long long t[N];
const int mod = 51123987;
int main() {
  long long resp = 0;
  int n;
  scanf("%d%s", &n, str);
  for (int i = 0; i < 2 * n + 1; i++) {
    if (i & 1)
      man[i] = str[i / 2];
    else
      man[i] = ' ';
  }
  int cen = 0;
  for (int i = 0; i < 2 * n + 1; i++) {
    d[i] = min(d[cen + cen - i], max(0, cen + d[cen] - i));
    while (i - d[i] >= 0 && i + d[i] < 2 * n + 1 &&
           man[i - d[i]] == man[i + d[i]])
      d[i]++;
    if (i + d[i] > cen + d[cen]) cen = i;
    resp += d[i] / 2;
    l[(i + 1) / 2]++;
    l[(i - d[i] + 1) / 2]--;
    r[i / 2 + 1]++;
    r[(i + d[i] + 1) / 2]--;
  }
  resp %= mod;
  resp = (resp * (resp - 1)) / 2 % mod;
  for (int i = n + 1; i--; t[i] = (t[i + 1] + l[i]) % mod) l[i] += l[i + 1];
  for (int i = 0; ++i <= n + 1; resp -= r[i] * t[i + 1] % mod) r[i] += r[i - 1];
  printf("%lld\n", (resp % mod + mod) % mod);
}
