#include <bits/stdc++.h>
using namespace std;
const int u = 2000010, mod = 51123987;
char s[2 * u], str[u];
int p[2 * u], a[u], b[u], c[u], n, m, i, ans;
void manacher() {
  for (int i = 0, j = 0, k = 0, l; i < m; i++) {
    l = (i <= j) * min(j - i, p[2 * k - i]);
    while (i - l > 0 && i + l + 1 < m && s[i - l - 1] == s[i + l + 1]) l++;
    p[i] = l;
    if (i + l > j) j = i + l, k = i;
  }
}
void add(int j, int k) {
  a[i - j + 1]++, a[i + 1]--, b[i + k]++, b[i + j + k]--;
}
int main() {
  cin >> n;
  scanf("%s", str);
  for (i = 0; i < n; i++) s[m++] = '*', s[m++] = str[i];
  s[m++] = '*';
  manacher();
  for (i = 0; i < n; i++)
    add(p[i * 2 + 1] + 1 >> 1, 0), add(p[i * 2 + 2] >> 1, 1);
  for (i = 1; i <= n; i++)
    a[i] += a[i - 1], b[i] += b[i - 1], c[i] = (c[i - 1] + b[i - 1]) % mod;
  ans = (long long)c[n] * (c[n] - 1) / 2 % mod;
  for (i = 0; i < n; i++) ans = (ans - (long long)c[i] * a[i]) % mod;
  cout << (ans + mod) % mod << endl;
  return 0;
}
