#include <bits/stdc++.h>
using namespace std;
long long n, len, ans, sum, cnt, p[4000005], l[4000005], r[4000005];
char st[4000005], s[4000005];
long long Change(char* st) {
  long long j = 2;
  s[0] = '^';
  s[1] = '$';
  for (long long i = 0; i < n; i++) {
    s[j++] = st[i];
    s[j++] = '$';
  }
  s[j] = '%';
  return j;
}
void Manachar() {
  len = Change(st);
  long long mid = 1, mx = 1;
  for (long long i = 1; i < len; i++) {
    if (i < mx)
      p[i] = min(mx - i, p[mid * 2 - i]);
    else
      p[i] = 1;
    while (s[i - p[i]] == s[i + p[i]]) p[i]++;
    if (mx < i + p[i]) {
      mid = i;
      mx = i + p[i];
    }
    l[i - p[i] + 1]++;
    l[i + 1]--;
    r[i]++;
    r[i + p[i]]--;
    ((cnt += (p[i] >> 1)) %= 51123987ll);
  }
}
signed main() {
  cin >> n;
  scanf("%s", st);
  Manachar();
  ((ans = cnt * (cnt - 1) / 2) %= 51123987ll);
  for (long long i = 1; i <= len; i++) {
    l[i] += l[i - 1];
    r[i] += r[i - 1];
    if (!(i & 1)) {
      ((ans -= sum * l[i]) %= 51123987ll);
      ((sum += r[i]) %= 51123987ll);
    }
  }
  cout << (ans + 51123987ll) % 51123987ll;
  return 0;
}
