#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch - '0' < 0 || ch - '0' > 9) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch - '0' >= 0 && ch - '0' <= 9) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, len;
char s[2000010], t[2000010 * 2];
void prework() {
  for (int i = 1; i <= n * 2 + 1; i++) {
    if (i & 1)
      t[i] = '#';
    else
      t[i] = s[i / 2];
  }
  len = n * 2 + 1;
}
int R[2000010 * 2];
void manacher() {
  R[1] = 1;
  int p = 1, mx = 1;
  for (int i = 2; i <= len; i++) {
    if (mx < i)
      R[i] = 1;
    else {
      int j = 2 * p - i;
      if (mx - i > R[j])
        R[i] = R[j];
      else
        R[i] = mx - i;
    }
    while (t[i + R[i]] == t[i - R[i]] && i + R[i] <= len && i - R[i] > 0)
      R[i]++;
    if (i + R[i] - 1 > mx) {
      p = i;
      mx = i + R[i] - 1;
    }
  }
}
struct P {
  int l, r;
} p[2000010 * 2];
int top;
int sum[2000010];
int main() {
  n = read();
  scanf("%s", s + 1);
  prework();
  manacher();
  for (int i = 1; i <= len; i++) {
    int l = i - R[i] + 1, r = i + R[i] - 1;
    l = (l + 1) / 2;
    r = r / 2;
    if (l > r) continue;
    p[++top].l = l;
    p[top].r = r;
  }
  for (int i = 1; i <= top; i++) {
    int L = (p[i].l + p[i].r + 1) / 2;
    sum[L]++;
    sum[p[i].r + 1]--;
  }
  for (int i = 1; i <= n; i++) sum[i] = (sum[i] + sum[i - 1]) % 51123987;
  for (int i = 1; i <= n; i++) sum[i] = (sum[i] + sum[i - 1]) % 51123987;
  for (int i = 1; i <= n; i++) sum[i] = (sum[i] + sum[i - 1]) % 51123987;
  int res = 0;
  for (int i = 1; i <= top; i++) {
    int mid = (p[i].l + p[i].r) / 2;
    res = (res + sum[mid - 1] - sum[max(p[i].l - 2, 0)] + 51123987) % 51123987;
  }
  int now = 0;
  for (int i = 1; i <= top; i++)
    now = (now + (p[i].r - p[i].l + 2) / 2) % 51123987;
  now = 1ll * now * (now - 1) % 51123987 * 25561994 % 51123987;
  printf("%d\n", (now - res + 51123987) % 51123987);
  return 0;
}
