#include <bits/stdc++.h>
using namespace std;
int read() {
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    xx = xx * 10 + ch - '0';
    ch = getchar();
  }
  return xx * ff;
}
const int MOD = 51123987;
const int maxn = 2000010, SIZ = 26;
struct Pal_Tree {
  int fail[maxn], num[maxn], len[maxn], S[maxn];
  int last, p, tot;
  vector<pair<int, int> > next[maxn];
  int insert(int x) {
    next[tot].clear();
    num[tot] = 0;
    len[tot] = x;
    return tot++;
  }
  void init() {
    tot = 0;
    insert(0), insert(-1);
    last = p = 0;
    S[p] = -1;
    fail[0] = 1;
  }
  int get_fail(int x) {
    while (S[p - len[x] - 1] != S[p]) x = fail[x];
    return x;
  }
  int find(int x, int y) {
    int siz = next[x].size();
    for (int i = 0; i < siz; i++)
      if (next[x][i].first == y) return next[x][i].second;
    return 0;
  }
  void add(int c) {
    c -= 'a';
    S[++p] = c;
    int cur = get_fail(last);
    int res = find(cur, c);
    if (!res) {
      int now = insert(len[cur] + 2);
      fail[now] = find(get_fail(fail[cur]), c);
      next[cur].push_back(make_pair(c, now));
      num[now] = num[fail[now]] + 1;
      last = now;
    } else
      last = res;
  }
} T;
char s[maxn];
int N;
int tail[maxn], sum[maxn];
int main() {
  N = read();
  gets(s + 1);
  T.init();
  for (int i = 1; i <= N; i++) {
    T.add(s[i]);
    tail[i] = T.num[T.last];
  }
  T.init();
  for (int i = N; i >= 1; i--) {
    T.add(s[i]);
    sum[i] = sum[i + 1] + T.num[T.last];
    if (sum[i] >= MOD) sum[i] -= MOD;
  }
  int ans = 1LL * sum[1] * (sum[1] - 1) / 2 % MOD;
  for (int i = 1; i < N; i++) {
    ans -= 1LL * tail[i] * sum[i + 1] % MOD;
    if (ans < 0) ans += MOD;
  }
  printf("%d\n", ans);
  return 0;
}
