#include <bits/stdc++.h>
using namespace std;
struct PTree {
  char S[2000005], nx[2000005];
  int head[2000005], nxt[2000005], ch[2000005], m, fail[2000005], len[2000005],
      cnt[2000005], lst, sz, n;
  inline int newnode(int L) {
    cnt[sz] = 0, len[sz] = L, head[sz] = 0;
    return sz++;
  }
  inline void init() {
    m = sz = n = 0, lst = 1;
    newnode(0), newnode(-1);
    S[0] = 250, fail[0] = 1;
  }
  inline int getFail(int v) {
    while (S[n - len[v] - 1] != S[n]) v = fail[v];
    return v;
  }
  inline int add(int c) {
    S[++n] = c;
    int cur = getFail(lst), i, j;
    for (i = head[cur]; i; i = nxt[i])
      if (nx[i] == c) break;
    if (!i) {
      int now = newnode(len[cur] + 2);
      int x = getFail(fail[cur]);
      for (j = head[x]; j; j = nxt[j])
        if (nx[j] == c) break;
      if (j)
        fail[now] = ch[j];
      else
        fail[now] = 0;
      nxt[++m] = head[cur];
      head[cur] = m;
      nx[m] = c;
      ch[m] = now;
      cnt[now] = cnt[fail[now]] + 1;
      lst = now;
    } else
      lst = ch[i];
    return cnt[lst];
  }
} PT;
;
;
char s[2000005];
int sum[2000005], n;
int main() {
  scanf("%d", &n);
  scanf("%s", s);
  PT.init();
  for (int i = n - 1; ~i; --i)
    sum[i] = (sum[i + 1] + PT.add(s[i] - 'a')) % 51123987;
  PT.init();
  long long rt = 0;
  for (int i = 0; i < n; ++i)
    rt = (rt + 1ll * PT.add(s[i] - 'a') * sum[i + 1]) % 51123987;
  printf("%I64d\n",
         ((1ll * sum[0] * sum[0] - sum[0]) / 2 - rt + 51123987) % 51123987);
}
