#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
char s[2000010], ss[2000010 << 1];
int r[2000010 << 1], len;
long long s1[2000010];
int Init() {
  int len = strlen(s);
  ss[0] = '$';
  ss[1] = '#';
  int j = 2;
  for (int i = 0; i < len; i++) ss[j++] = s[i], ss[j++] = '#';
  ss[j] = '\0';
  return j;
}
void Manacher() {
  len = Init();
  int p, mx = 0;
  for (int i = 1; i < len; i++) {
    if (i < mx)
      r[i] = min(r[2 * p - i], mx - i);
    else
      r[i] = 1;
    while (ss[i - r[i]] == ss[i + r[i]]) r[i]++;
    if (mx < i + r[i]) p = i, mx = i + r[i];
  }
}
int main() {
  int n;
  while (~scanf("%d%s", &n, s)) {
    Manacher();
    long long tot = 0;
    memset(s1, 0, sizeof s1);
    for (int i = 1; i <= n * 2; i++) {
      s1[i / 2 + (i & 1)]++;
      s1[i / 2 + (i & 1) + r[i] / 2]--;
      tot += r[i] / 2;
      tot %= 51123987;
    }
    tot = tot * (tot - 1) / 2;
    tot %= 51123987;
    for (int i = 2; i <= n; i++) s1[i] += s1[i - 1];
    for (int i = 2; i <= n; i++) s1[i] += s1[i - 1];
    for (int i = 2; i <= n; i++) s1[i] += s1[i - 1];
    long long ans = 0;
    for (int i = 2; i <= n * 2; i++)
      ans += s1[i / 2 - 1] - s1[i / 2 - r[i] / 2 - 1], ans %= 51123987;
    printf("%I64d\n", (tot - ans + 51123987) % 51123987);
  }
}
