#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000000 + 10;
const int mod = 51123987;
int n;
long long p[maxn], sum;
char s1[maxn], s[maxn];
long long min(int a, int b) { return a < b ? a : b; }
inline void init() {
  s[0] = '$';
  for (int i = 1; i <= n; ++i) s[2 * i] = s1[i], s[2 * i - 1] = '#';
  s[2 * n + 1] = '#';
  n = 2 * n + 1;
}
inline void manacher() {
  init();
  p[0] = 0;
  for (int i = 1, id = 0, mx = 0; i <= n; ++i) {
    if (mx > i)
      p[i] = min(mx - i + 1, p[2 * id - i]);
    else
      p[i] = 0;
    while (s[i - p[i]] == s[i + p[i]]) ++p[i];
    if (i + p[i] - 1 > mx) id = i, mx = i + p[i] - 1;
    sum += (p[i] - 1) / 2;
    if (i % 2 == 0) ++sum;
  }
}
long long f[maxn], g[maxn];
inline void solve() {
  sum %= mod;
  sum = sum * (sum - 1) / 2;
  sum %= mod;
  for (int i = 2; i <= n; i += 2) {
    ++f[i - p[i] + 2];
    --f[i + 2];
    ++g[i];
    --g[i + p[i]];
  }
  for (int i = 1; i <= n; i += 2) {
    ++f[i - p[i] + 2];
    --f[i + 1];
    ++g[i + 1];
    --g[i + p[i]];
  }
  for (int i = 2; i <= n; i += 2) {
    f[i] += f[i - 2];
    f[i] %= mod;
    g[i] += g[i - 2];
    g[i] %= mod;
  }
  f[n + 1] = 0;
  for (int i = n - 1; i >= 1; i -= 2) f[i] += f[i + 2];
  for (int i = 2; i <= n; i += 2) {
    sum = sum - (g[i] * f[i + 2]) % mod;
    sum = (sum + mod) % mod;
  }
  sum = (sum + mod) % mod;
  printf("%I64d\n", sum);
}
int main() {
  scanf("%d%s", &n, s1 + 1);
  manacher();
  solve();
  return 0;
}
