#include <bits/stdc++.h>
using namespace std;
const int MOD = 51123987;
int n, r[2100000 * 2];
char s[2100000 * 2], s1[2100000];
long long a[2100000 * 2], b[2100000 * 2];
void palindrome(int n) {
  int i = 1, j = 0;
  while (i <= n) {
    while (i - j > 0 && i + j <= n && s[i - j] == s[i + j]) j++;
    r[i] = j;
    int k = 1;
    while (k < j && r[i - k] != j - k) r[i + k] = min(r[i - k], j - k), k++;
    i = i + k;
    j = max(0, j - k);
  }
}
int main() {
  cin >> n;
  scanf("%s", s1 + 1);
  for (int i = (1); i <= (n * 2 + 1); i++)
    if (i & 1)
      s[i] = '?';
    else
      s[i] = s1[i / 2];
  palindrome(n * 2 + 1);
  long long ans0 = 0, ans1 = 0;
  for (int i = (1); i <= (n * 2 + 1); i++)
    if (!(i % 2)) {
      ans0 += (r[i] + 1) / 2;
      a[i / 2 - (r[i] + 1) / 2 + 1]++;
      a[i / 2 + 1]--;
      b[i / 2]++;
      b[i / 2 + (r[i] + 1) / 2]--;
    } else {
      ans0 += r[i] / 2;
      a[i / 2 - r[i] / 2 + 1]++;
      a[i / 2 + 1]--;
      b[i / 2 + 1]++;
      b[i / 2 + r[i] / 2 + 1]--;
    }
  for (int i = (1); i <= (n); i++)
    (a[i] += a[i - 1]) %= MOD, (b[i] += b[i - 1]) %= MOD;
  for (int i = (1); i <= (n); i++) (b[i] += b[i - 1]) % MOD;
  for (int i = (1); i <= (n); i++) ans1 = (ans1 + a[i] * b[i - 1]) % MOD;
  if (ans0 % 2 == 0)
    ans0 = ans0 / 2 % MOD * ((ans0 - 1) % MOD) % MOD;
  else
    ans0 = (ans0 - 1) / 2 % MOD * (ans0 % MOD) % MOD;
  cout << (ans0 - ans1 + MOD) % MOD << endl;
  return 0;
}
