#include <bits/stdc++.h>
using namespace std;
const long long mod = 51123987;
char s[4000100], S[4000100];
long long len, p[4000100], cnt, st[4000100], en[4000100];
long long ans, tot;
inline void init() {
  S[0] = '!', S[++cnt] = '#';
  for (int i = 1; i <= len; i++) S[++cnt] = s[i], S[++cnt] = '#';
}
inline void Manacher() {
  long long mx = 0, id = 0;
  for (int i = 1; i <= cnt; i++) {
    if (i < mx)
      p[i] = min(p[2 * id - i], mx - i);
    else
      p[i] = 1;
    while (S[i + p[i]] == S[i - p[i]]) p[i]++;
    if (i + p[i] > mx) mx = i + p[i], id = i;
  }
}
int main() {
  scanf("%d %s", &len, s + 1);
  init();
  Manacher();
  for (int i = 1; i <= cnt; i++) {
    st[i - p[i] + 1]++, st[i + 1]--;
    en[i]++, en[i + p[i]]--;
    ans += (p[i] / 2), ans %= mod;
  }
  ans = (ans * (ans - 1) / 2), ans %= mod;
  for (int i = 1; i <= cnt; i++) {
    st[i] += st[i - 1], en[i] += en[i - 1];
    if (!(i % 2))
      ans = (ans - tot * st[i] % mod) % mod, tot = (tot + en[i]) % mod;
  }
  printf("%lld\n", (ans % mod + mod) % mod);
  return 0;
}
