#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
const int SIZE = 26;
const int mod = 51123987;
int val[2][maxn];
struct Edge {
  int nxt, to, v;
} edge[2 * maxn];
struct Palindromic_Tree {
  int head[maxn], TOT;
  int fail[maxn];
  int cnt[maxn];
  int num[maxn];
  int len[maxn];
  int S[maxn];
  int last;
  int n;
  int tot;
  int newnode(int l) {
    cnt[tot] = 0;
    num[tot] = 0;
    len[tot] = l;
    return tot++;
  }
  void addedge(int u, int v, int w) {
    TOT++;
    edge[TOT].to = v;
    edge[TOT].v = w;
    edge[TOT].nxt = head[u];
    head[u] = TOT;
  }
  int find(int u, int v) {
    for (int i = head[u]; i; i = edge[i].nxt) {
      if (v == edge[i].to) {
        return edge[i].v;
      }
    }
    return 0;
  }
  void init() {
    tot = 0;
    TOT = 0;
    memset(head, 0, sizeof(head));
    newnode(0);
    newnode(-1);
    last = 0;
    n = 0;
    S[n] = -1;
    fail[0] = 1;
  }
  int getfail(int x) {
    while (S[n - len[x] - 1] != S[n]) x = fail[x];
    return x;
  }
  void add(int c, int id) {
    c -= 'a';
    S[++n] = c;
    int cur = getfail(last);
    int tt = find(cur, c);
    if (!tt) {
      int now = newnode(len[cur] + 2);
      fail[now] = find(getfail(fail[cur]), c);
      addedge(cur, c, now);
      num[now] = num[fail[now]] + 1;
    }
    last = find(cur, c);
    val[id][n] = num[last];
    cnt[last]++;
  }
  void count() {
    for (int i = tot - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
  }
} T;
char s[maxn];
int main() {
  int len;
  cin >> len;
  T.init();
  scanf("%s", s);
  for (int i = 0; i < len; i++) {
    T.add(s[i], 0);
  }
  T.count();
  long long ans = 0;
  for (int i = 2; i < T.tot; i++) {
    ans += T.cnt[i];
    ans %= mod;
  }
  ans = ans * (ans - 1) / 2 % mod;
  T.init();
  for (int i = len - 1; i >= 0; i--) {
    T.add(s[i], 1);
  }
  for (int i = 1; i <= len; i++) {
    val[1][i] += val[1][i - 1];
    val[1][i] %= mod;
  }
  long long ret = 0;
  for (int i = 1; i <= len; i++) {
    ret += (long long)val[0][i] * val[1][len - i] % mod;
    ret %= mod;
  }
  ans = (ans - ret + mod) % mod;
  printf("%lld\n", ans);
  return 0;
}
