#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 3;
const int md = 51123987;
int n;
int r[maxn << 1], f[maxn], g[maxn];
string s, str;
inline void Manacher(int* h) {
  str = "@";
  for (int i = 0; s[i]; ++i) str += s[i], str += '#';
  str[n << 1] = '$';
  int mid = 0, mx = 0, m = 2 * n - 1;
  for (int i = (1); i <= (m); ++i) {
    int x = mx < i ? 1 : min(mx - i, r[2 * mid - i]);
    while (str[i - x] == str[i + x]) ++x;
    if (x + i > mx) mx = x + i, mid = i;
    r[i] = x;
  }
  for (int i = (1); i <= (m); ++i) ++h[(i >> 1) + 1], --h[(i + r[i] >> 1) + 1];
  for (int i = (2); i <= (n); ++i) (h[i] += h[i - 1]) %= md;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> s;
  Manacher(f);
  reverse(s.begin(), s.end());
  memset(r, 0, sizeof r);
  Manacher(g);
  reverse(g + 1, g + n + 1);
  for (int i = (n - 1); i >= (1); --i) (g[i] += g[i + 1]) %= md;
  int ans = (1ll * g[1] * g[1] % md - g[1] + md) % md * ((md + 1) >> 1) % md;
  for (int i = (1); i <= (n - 1); ++i)
    (ans -= 1ll * f[i] * g[i + 1] % md - md) %= md;
  cout << ans << '\n';
  return 0;
}
