#include <bits/stdc++.h>
using namespace std;
const int M = 5000005;
const int MOD = 51123987;
int n, p[M];
char s[M];
long long ans, tot;
unsigned long long pre[M], suf[M];
inline void deal(char *s) {
  int len = strlen(s);
  for (int i = len * 2; i >= 2; i -= 2) s[i] = s[i / 2 - 1];
  s[0] = '&';
  for (int i = 1; i <= len * 2 + 1; i += 2) s[i] = '#';
}
inline void manacher(char *s, int *p) {
  int len = strlen(s);
  for (int i = 0, mid = 0, r = 0; i < len; i++) {
    p[i] = min(p[mid * 2 - i], r - i + 1);
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] - 1 > r) mid = i, r = i + p[i] - 1;
  }
}
inline void prepare(int *p, int len, unsigned long long *pre,
                    unsigned long long *suf) {
  for (int i = 0; i < len; i++) {
    pre[i]++;
    suf[i]++;
    if (i + p[i] < len) pre[i + p[i]]--;
    if (i - p[i] >= 0) suf[i - p[i]]--;
  }
  for (int i = 0; i < len; i++)
    if (i > 0) pre[i] += pre[i - 1];
  for (int i = len - 1; i >= 0; i--) suf[i] += suf[i + 1];
}
void write(long long x) {
  if (x > 9) write(x / 10);
  putchar('0' + x % 10);
}
int main() {
  scanf("%d", &n);
  scanf("%s", s);
  deal(s);
  manacher(s, p);
  prepare(p, 2 * n + 2, pre, suf);
  for (int i = n; i >= 1; i--) suf[i * 2] += suf[(i + 1) * 2];
  for (int i = 1; i < n * 2 + 2; i++) {
    if (s[i] == '#')
      (tot += floor(p[i] * 1.0 / 2)) %= MOD;
    else
      (tot += ceil(p[i] * 1.0 / 2)) %= MOD;
  }
  tot = tot * (tot - 1) / 2 % MOD;
  for (int i = 1; i < n; i++)
    (ans += pre[i * 2] * suf[(i + 1) * 2] % MOD) %= MOD;
  write((tot - ans + MOD) % MOD);
  return 0;
}
