#include <bits/stdc++.h>
using namespace std;
const int NR = 4e6 + 5;
int n;
long long P = 51123987;
char s[NR];
int d[NR];
long long f[NR], g[NR];
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = n; i >= 1; i--) {
    s[i * 2] = s[i];
    s[i * 2 - 1] = '#';
  }
  s[n * 2 + 1] = '#';
  n = n * 2 + 1;
  int p = 0, maxr = 0;
  for (int i = 1; i <= n; i++) {
    if (i <= maxr) d[i] = min(d[p + maxr - i], maxr - i + 1);
    while (i - d[i] >= 1 && i + d[i] <= n && s[i - d[i]] == s[i + d[i]]) d[i]++;
    if (i + d[i] - 1 > maxr) {
      p = i - d[i] + 1;
      maxr = i + d[i] - 1;
    }
    if (s[i] == '#' && d[i] == 1) continue;
    f[(i - d[i] + 2) / 2]++;
    f[i / 2 + 1]--;
    if (s[i] == '#')
      g[i / 2 + 1]++;
    else
      g[i / 2]++;
    g[(i + d[i] - 1) / 2 + 1]--;
  }
  n = (n - 1) / 2;
  for (int i = 1; i <= n; i++) {
    f[i] += f[i - 1];
    f[i] %= P;
    g[i] += g[i - 1];
    g[i] %= P;
  }
  long long sum1 = 0, sum2 = 0, ans = 0;
  for (int i = 1; i <= n; i++) {
    sum1 += f[i];
    sum1 %= P;
    ans += f[i] * sum2;
    ans %= P;
    sum2 += g[i];
    sum2 %= P;
  }
  sum1 = sum1 * (sum1 - 1) / 2 % P;
  printf("%lld\n", (sum1 - ans + P) % P);
  return 0;
}
