#include <bits/stdc++.h>
using namespace std;
const int N = 8e6 + 10, mod = 51123987;
int n, len, p[N], pos, mx, l[N], r[N];
long long ans, sum;
char a[N], s[N];
void manacher() {
  for (int i = 1; i <= n; i++) {
    if (i < mx)
      p[i] = min(p[pos * 2 - i], mx - i);
    else
      p[i] = 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (mx < i + p[i]) mx = i + p[i], pos = i;
    ++l[i - p[i] + 1], --l[i + 1];
    ++r[i], --r[i + p[i]];
    ans = (ans + (p[i] >> 1)) % mod;
  }
  ans = (ans * (ans - 1) / 2) % mod;
}
int main() {
  scanf("%d%s", &n, a + 1);
  len = n;
  s[n = 1] = '#';
  for (int i = 1; i <= len; i++) s[++n] = a[i], s[++n] = '#';
  s[0] = '[', s[n + 1] = ']';
  manacher();
  for (int i = 1; i <= n; i++) {
    l[i] += l[i - 1], r[i] += r[i - 1];
    if (i % 2 == 0) {
      ans = (ans - (long long)l[i] * sum % mod + mod) % mod;
      sum = (sum + r[i]) % mod;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
