#include <bits/stdc++.h>
using namespace std;
char a[4000010];
int len, p[4000010], bs[4000010], be[4000010];
long long tots[4000010], tote[4000010], sum;
void read() {
  a[0] = '$';
  int n;
  scanf("%d\n", &n);
  for (int i = 1; i <= n; i++) a[++len] = '*', a[++len] = getchar();
  a[++len] = '*', a[len + 1] = '#';
}
void Manacher() {
  int R = 0, id;
  for (int i = 1; i <= len; i++) {
    p[i] = R > i ? min(p[id * 2 - i], R - i) : 0;
    for (; a[i - p[i]] == a[i + p[i]]; p[i]++)
      ;
    p[i]--;
    if (R < i + p[i]) R = i + p[i], id = i;
    bs[i - p[i]]++, bs[i + 1]--;
    be[i]++, be[i + p[i] + 1]--;
  }
}
void work() {
  for (int i = 1; i <= len; i++) {
    tots[i] = tots[i - 1] + bs[i];
    tote[i] = tote[i - 1] + be[i];
  }
  for (int i = 1; i <= len; i++)
    if (a[i] != '*') sum += tots[i];
  sum %= 51123987;
  sum = sum % 2 ? (sum - 1) / 2 * sum : sum / 2 * (sum - 1);
  long long total = 0;
  for (int i = 1; i <= len; i++)
    if (a[i] != '*') {
      sum = (sum - total * tots[i] % 51123987 + 51123987) % 51123987;
      total = (total + tote[i]) % 51123987;
    }
}
int main() {
  read();
  Manacher();
  work();
  cout << sum << endl;
  return 0;
}
