#include <bits/stdc++.h>
const int p = 51123987, N = 4e6 + 7;
using namespace std;
int n, m = 1, f[N], l[N], r[N], ans;
char a[N], b[N];
int main() {
  scanf("%d%s", &n, a), b[0] = 1;
  for (int i = 0; i < n; i++, m++) b[++m] = a[i];
  for (int i = 1, p = 0, q = 0; i <= m; i++) {
    f[i] = q > i ? min(f[2 * p - i], q - i) : 1;
    while (b[i + f[i]] == b[i - f[i]]) f[i]++;
    if (i + f[i] > q) p = i, q = i + f[i];
  }
  for (int i = 1; i <= m; i++)
    l[i - f[i] + 1]++, l[i + 1]--, r[i]++, r[i + f[i]]--,
        (ans += f[i] / 2) %= p;
  ans = 1ll * ans * (ans - 1) / 2 % p;
  for (int i = 1, s = 0; i <= m; i++) {
    l[i] += l[i - 1], r[i] += r[i - 1];
    if (i % 2 == 0) (ans -= 1ll * s * l[i] % p) %= p, (s += r[i]) %= p;
  }
  printf("%d\n", (ans + p) % p);
}
