#include <bits/stdc++.h>
using namespace std;
const int N = 2.1e6, O = 51123987;
char s[N];
int n, a[N], b[N], p[N], q[N];
void manacher(int *a, int d) {
  int m = n - d;
  a[0] = s[0] == s[d];
  int k = 0;
  for (int i = 1; i < m; ++i) {
    int j = 2 * k - i;
    if (j <= k - a[k])
      a[i] = 0;
    else
      a[i] = max(0, min(a[j], k + a[k] - i));
    while (i - a[i] >= 0 && i + a[i] + d < n && s[i - a[i]] == s[i + a[i] + d])
      ++a[i];
    if (i + a[i] > k + a[k]) k = i;
  }
}
int main() {
  while (scanf("%d%s", &n, s) > 0) {
    manacher(a, 0);
    manacher(b, 1);
    int64_t ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += a[i];
      if (i < n - 1) ans += b[i];
    }
    if (ans % 2 == 0)
      ans = ans / 2 % O * ((ans - 1) % O) % O;
    else
      ans = (ans - 1) / 2 % O * (ans % O) % O;
    memset(p, 0, sizeof(p));
    memset(q, 0, sizeof(q));
    for (int i = 0; i < n; ++i) {
      p[i - a[i] + 1]++;
      p[i + 1]--;
      p[i - b[i] + 1]++;
      p[i + 1]--;
      q[i]++;
      q[i + a[i]]--;
      q[i + 1]++;
      q[i + b[i] + 1]--;
    }
    int64_t nowp = 0, sumq = 0, nowq = 0;
    for (int i = 0; i < n; ++i) {
      (nowp += p[i] + O) %= O;
      ans = (ans + O - sumq * nowp % O) % O;
      (nowq += q[i] + O) %= O;
      (sumq += nowq + O) %= O;
    }
    cout << ans << endl;
  }
  return 0;
}
