#include <bits/stdc++.h>
int N, M = 1, f[4000005], l[4000005], r[4000005], ans;
char a[4000005], b[4000005];
int main() {
  scanf("%d%s", &N, a), b[0] = 1;
  for (int i = 0; i < N; i++) b[++M] = a[i], M++;
  for (int i = 1, p = 0, q = 0; i <= M; i++) {
    f[i] = q > i ? std::min(f[2 * p - i], q - i) : 1;
    for (; 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) %= 51123987;
  ans = 1ll * ans * (ans - 1) / 2 % 51123987;
  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] % 51123987) %= 51123987, (s += r[i]) %= 51123987;
  }
  printf("%d\n", (ans + 51123987) % 51123987);
}
