#include <bits/stdc++.h>
using namespace std;
const int mod = 51123987;
const int MAXN = 2e6 + 5;
template <typename T>
inline void read(T& x) {
  x = 0;
  char temp = getchar();
  bool f = false;
  while (!isdigit(temp)) {
    if (temp == '-') f = true;
    temp = getchar();
  }
  while (isdigit(temp)) {
    x = (x << 1) + (x << 3) + temp - '0';
    temp = getchar();
  }
  if (f) x = -x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar(x % 10 + '0');
}
int n;
char str[MAXN];
struct node {
  vector<pair<int, int> > son;
  int len, fail, dep;
  inline int Find(int tar) {
    int res = -1;
    for (register int i = 0; i < son.size(); i++)
      if (son[i].first == tar) {
        res = i;
        break;
      }
    return res;
  }
};
struct PAM {
  node a[MAXN];
  int last, now_len, size, res;
  inline void Init() {
    memset(a, 0, sizeof(a));
    a[1].len = -1, a[0].len = 0;
    a[1].fail = a[0].fail = 1;
    size = 1, last = 0, now_len = 0, res = 0;
  }
  inline int GetFail(int id) {
    while (str[now_len - a[id].len - 1] != str[now_len]) id = a[id].fail;
    return id;
  }
  inline void Insert(int s) {
    ++now_len;
    int pre = GetFail(last), tmp = a[pre].Find(s), now;
    if (tmp == -1)
      now = 0;
    else
      now = a[pre].son[tmp].second;
    if (!now) {
      now = ++size;
      tmp = a[GetFail(a[pre].fail)].Find(s);
      if (tmp == -1)
        a[now].fail = 0;
      else
        a[now].fail = a[GetFail(a[pre].fail)].son[tmp].second;
      a[now].len = a[pre].len + 2, a[now].dep = a[a[now].fail].dep + 1;
      a[pre].son.push_back(make_pair(s, now));
    }
    last = now, res = (res + a[now].dep) % mod;
  }
} tree;
int x[MAXN];
int main() {
  read(n);
  scanf("%s", str + 1);
  tree.Init();
  for (register int i = 1; i <= n; i++) tree.Insert(str[i]), x[i] = tree.res;
  for (register int i = 1; i * 2 <= n; i++) swap(str[i], str[n - i + 1]);
  tree.Init();
  int ans = (1ll * x[n] * (x[n] - 1) / 2) % mod, temp = 0;
  for (register int i = 1; i <= n; i++)
    tree.Insert(str[i]),
        ans = ((ans - 1ll * (tree.res - temp) * x[n - i] % mod) % mod + mod) %
              mod,
        temp = tree.res;
  print(ans), puts("");
  return 0;
}
