#include <bits/stdc++.h>
using namespace std;
inline long long myInt() {
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  int flag = 1;
  if (c == '-') flag = -1, c = getchar();
  long long x = 0;
  while (isdigit(c)) {
    x = (x * 10) + (c - '0');
    c = getchar();
  }
  if (-1 == flag) return -x;
  return x;
}
const int mod = 51123987;
const int N = 2000005;
struct PalindTeee {
  vector<pair<int, int> > next[N];
  int fail[N], cnt[N], num[N], len[N], S[N];
  int last, n, p;
  int newNode(int l) {
    next[p].clear();
    cnt[p] = num[p] = 0;
    len[p] = l;
    return p++;
  }
  void init() {
    p = 0;
    newNode(0);
    newNode(-1);
    last = 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;
  }
  int getId(int cur, int c) {
    for (int i = 0; i < next[cur].size(); i++)
      if (next[cur][i].first == c) {
        return next[cur][i].second;
      }
    return 0;
  }
  void add(int c) {
    c -= 'a';
    S[++n] = c;
    int cur = getFail(last);
    if (!getId(cur, c)) {
      int now = newNode(len[cur] + 2);
      fail[now] = getId(getFail(fail[cur]), c);
      next[cur].push_back(make_pair(c, now));
      num[now] = num[fail[now]] + 1;
    }
    last = getId(cur, c);
    cnt[last]++;
  }
  void count() {
    for (int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
  }
} A;
char S[N];
int n;
long long m;
long long dp[N];
int main() {
  A.init();
  n = myInt();
  scanf("%s", S);
  for (int i = 0; i < n; i++) {
    A.add(S[i]);
    dp[i] = A.num[A.last];
    if (i) dp[i] = (dp[i] + dp[i - 1]) % mod;
  }
  A.init();
  long long ans = 0;
  long long all = 0;
  for (int i = n - 1; i >= 0; i--) {
    A.add(S[i]);
    if (i) ans += A.num[A.last] * dp[i - 1] % mod;
    ans %= mod;
    all += A.num[A.last];
    all %= mod;
  }
  ans = all * (all - 1) / 2 - ans;
  ans %= mod;
  if (ans < 0) ans += mod;
  printf("%d\n", int(ans));
}
