#include <bits/stdc++.h>
const int N = 2000005;
char a[N];
int r[N];
int c[N], LSEG[N], RSEG[N], LMINUS[N], RMINUS[N];
int LSUM[N], RSUM[N];
int main(void) {
  int n, i, j, total = 0;
  int MOD = 51123987;
  scanf("%d", &n);
  scanf("%s", a);
  r[0] = 0;
  int last = 0, lasti = 0;
  for (i = 1; i < n; i++)
    if (last >= i && i + r[lasti * 2 - i] < last) {
      r[i] = r[lasti * 2 - i];
    } else {
      lasti = i;
      for (j = last + 1; j < n && i * 2 - j >= 0 && a[j] == a[i - (j - i)]; j++)
        ;
      r[i] = j - i - 1;
      last = j - 1;
    }
  for (i = 0; i < n; i++) {
    LSEG[i]++;
    LSEG[i + r[i] + 1]--;
    LMINUS[i + r[i] + 1] += r[i] + 1;
    RSEG[i]++;
    if (i - r[i] - 1 >= 0) RSEG[i - r[i] - 1]--;
    if (i - r[i] - 1 >= 0) RMINUS[i - r[i] - 1] += r[i] + 1;
    total = (total + r[i] + 1) % MOD;
  }
  r[0] = 0;
  last = 0;
  lasti = 0;
  for (i = 1; i < n; i++)
    if (last > i && i + r[lasti * 2 - i] < last) {
      r[i] = r[lasti * 2 - i];
    } else {
      lasti = i;
      for (j = last + (last < i);
           j < n && i * 2 - j - 1 >= 0 && a[j] == a[i * 2 - j - 1]; j++)
        ;
      r[i] = j - i;
      last = j;
    }
  for (i = 0; i < n; i++) {
    LSEG[i]++, LSEG[i + r[i]]--;
    LMINUS[i + r[i]] += r[i];
    if (i) RSEG[i - 1]++;
    if (i - r[i] - 1 >= 0) RSEG[i - r[i] - 1]--;
    if (i - r[i] - 1 >= 0) RMINUS[i - r[i] - 1] += r[i];
    total = (total + r[i]) % MOD;
  }
  LSUM[0] = LSEG[0];
  for (i = 1; i < n; i++) {
    LSEG[i] += LSEG[i - 1];
    LSUM[i] = LSUM[i - 1] + LSEG[i];
    LSUM[i] %= MOD;
  }
  for (i = n - 1; i >= 0; --i) {
    RSEG[i] += RSEG[i + 1];
    RSUM[i] = RSUM[i + 1] + RSEG[i];
    RSUM[i] %= MOD;
  }
  int ans = 0;
  for (i = 1; i < n; i++) ans = (ans + 1LL * LSEG[i - 1] * RSUM[i]) % MOD;
  ans = (1LL * total * (total - 1) / 2 - ans) % MOD;
  if (ans < 0) ans += MOD;
  printf("%d\n", ans);
}
