#include <bits/stdc++.h>
using namespace std;
const int N = 5000010;
const int mod = 51123987;
int n, m, p[N], le[N], ri[N], ss[N];
char c[N], s[N];
void manacher() {
  int i, ri, pos, ans;
  ri = pos = ans = 0;
  for (i = 1; i <= n * 2; i++) {
    if (ri > i)
      p[i] = min(p[pos * 2 - i], ri - i);
    else
      p[i] = 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > ri) ri = i + p[i], pos = i;
  }
}
void iWork() {
  cin >> n;
  scanf("%s", c);
  int i;
  m = 0;
  for (i = 0; i < n; i++) s[++m] = '@', s[++m] = c[i];
  s[0] = '#';
  s[++m] = '@';
  s[++m] = '*';
  manacher();
  for (i = 1; i <= n; i++) {
    int r = p[i << 1] - 1;
    le[i]++;
    le[i + r / 2 + 1]--;
    ri[i]++;
    ri[i - r / 2 - 1]--;
    r = p[i << 1 | 1] - 1;
    le[i + 1]++;
    le[i + r / 2 + 1]--;
    ri[i]++;
    ri[i - r / 2]--;
  }
  for (i = 1; i <= n; i++) le[i] += le[i - 1];
  for (i = n; i >= 1; i--)
    ri[i] += ri[i + 1], ss[i] = (ss[i + 1] + ri[i]) % mod;
  long long ans = (long long)ss[1] * (ss[1] - 1) >> 1;
  ans %= mod;
  for (i = 1; i <= n; i++) ans = (ans - (long long)le[i] * ss[i + 1]) % mod;
  ans = (ans + mod) % mod;
  cout << ans << endl;
}
int main() {
  iWork();
  return 0;
}
