#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 20;
const int mod = 51123987;
const int CHARN = 26;
bool flag;
long long qmul(long long a, long long b, long long mod) {
  long long res = 0;
  while (b) {
    if (b & 1ll) res = (res + a) % mod;
    a = (a + a) % mod;
    b >>= 1ll;
  }
  return res;
}
struct link_list {
  int u[MAXN], v[MAXN], nxt[MAXN], head[MAXN], tot, i;
  void _clear() {
    memset(head, -1, sizeof head);
    tot = 0;
  }
  void _clear(int x) { head[x] = -1; }
  int get(int x, int y) {
    for (i = head[x]; i != -1; i = nxt[i]) {
      if (u[i] == y) return v[i];
    }
    return 0;
  }
  void _insert(int x, int y, int z) {
    u[tot] = y, v[tot] = z;
    nxt[tot] = head[x];
    head[x] = tot++;
  }
};
struct Palindromic_Tree {
  link_list nxt;
  int fail[MAXN];
  int cnt[MAXN];
  int num[MAXN];
  int len[MAXN];
  int S[MAXN];
  int last;
  int n;
  int p;
  int newnode(int l) {
    nxt._clear(p);
    cnt[p] = 0;
    num[p] = 0;
    len[p] = l;
    return p++;
  }
  void init() {
    nxt._clear();
    p = 0;
    newnode(0);
    newnode(-1);
    last = 0;
    n = 0;
    S[n] = -1;
    fail[0] = 1;
  }
  int get_fail(int x) {
    while (S[n - len[x] - 1] != S[n]) x = fail[x];
    return x;
  }
  int add(int c) {
    S[++n] = c;
    int cur = get_fail(last);
    if (!nxt.get(cur, c)) {
      int now = newnode(len[cur] + 2);
      int tmp = get_fail(fail[cur]);
      fail[now] = nxt.get(tmp, c);
      nxt._insert(cur, c, now);
      num[now] = num[fail[now]] + 1;
    }
    last = nxt.get(cur, c);
    cnt[last]++;
    return last;
  }
  void count() {
    for (int i = p - 1; i >= 0; --i) cnt[fail[i]] += cnt[i];
  }
  void count2() {
    for (int i = 0; i <= p - 1; i++) cnt[i] += cnt[fail[i]];
  }
} pat;
char ss[MAXN];
long long pos[MAXN];
long long sum[MAXN];
long long fnum;
int main() {
  fnum = 0;
  int n;
  scanf("%d", &n);
  scanf("%s", ss);
  pat.init();
  for (int i = 0; i < n; i++) {
    int node = pat.add(ss[i] - 'a');
    if (i == 0) {
      sum[i] = 1;
      continue;
    }
    sum[i] = (sum[i - 1] + pat.num[node]) % mod;
  }
  fnum = sum[n - 1];
  pat.init();
  for (int i = n - 1; i >= 0; i--) {
    int now = pat.add(ss[i] - 'a');
    pos[i] = pat.num[now];
  }
  long long ans = 0;
  for (int i = 0; i < n - 1; i++) {
    ans = (ans + qmul(sum[i], pos[i + 1], mod)) % mod;
  }
  ans = ((qmul(qmul(fnum, (fnum - 1 + mod) % mod, mod), 25561994, mod) - ans) %
             mod +
         mod) %
        mod;
  printf("%lld\n", ans);
}
