#include <bits/stdc++.h>
using namespace std;
char s[2222222];
int n, p[2222222], a[2222222], b[2222222], m;
int main() {
  scanf("%d%s", &n, s + 1);
  for (int i = 1, j = 0; i <= n; i++) {
    p[i] = 0;
    if (j + p[j] - 1 >= i) p[i] = min(p[2 * j - i], j + p[j] - i);
    if (i + p[i] - 1 >= j + p[j] - 1)
      for (j = i; i + p[i] <= n && i - p[i] > 0 && s[i - p[i]] == s[i + p[i]];
           p[i]++)
        ;
    a[i - p[i] + 1]++, a[i + 1]--, b[i + p[i] - 1]++, b[i - 1]--;
  }
  for (int i = 1, j = 0; i <= n; i++) {
    p[i] = 0;
    if (j + p[j] - 1 >= i) p[i] = min(p[2 * j - i], j + p[j] - i);
    if (i + p[i] >= j + p[j])
      for (j = i;
           i + p[i] + 1 <= n && i - p[i] > 0 && s[i - p[i]] == s[i + p[i] + 1];
           p[i]++)
        ;
    a[i - p[i] + 1]++, a[i + 1]--, b[i + p[i]]++, b[i]--;
  }
  for (int i = 1; i <= n; i++) a[i] = (a[i] + a[i - 1]) % 51123987;
  for (int i = n; i >= 1; i--) b[i] = (b[i] + b[i + 1]) % 51123987;
  int S = 0, T = 0;
  for (int i = 1; i <= n; i++)
    S = (S + (long long)a[i] * T % 51123987) % 51123987,
    T = (T + b[i]) % 51123987;
  printf("%d\n", (int)((long long)T * (T - 1) / 2 % 51123987 - S + 51123987) %
                     51123987);
  return 0;
}
