#include <bits/stdc++.h>
using namespace std;
const long double pi = 3.14159265359;
template <typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}
const int maxn = 2000005;
vector<pair<char, int> > to[maxn];
int lnk[maxn], len[maxn], cnt[maxn];
int strict[maxn];
char s[maxn];
int last = 1, sn = 1, sz = 2;
void init() {
  for (int i = 0; i < maxn; i++) to[i].clear();
  last = 1, sn = 1, sz = 2;
  s[0] = -1;
  lnk[1] = 0;
  strict[1] = 0;
  len[0] = -1;
}
int go(int v, char c) {
  for (auto x : to[v])
    if (x.first == c) return x.second;
  return -1;
}
int getLink(int v, char c) {
  while (true) {
    int p = lnk[v];
    if (c == s[sn - 1 - len[p] - 1]) return p;
    v = strict[v];
    if (c == s[sn - 1 - len[v] - 1]) return v;
  }
}
int getLinkNaive(int v, char c) {
  v = lnk[v];
  while (c != s[sn - 1 - len[v] - 1]) v = lnk[v];
  return v;
}
int add(char c) {
  s[sn++] = c;
  assert(getLink(last, c) == getLinkNaive(last, c));
  int p = (c == s[sn - 1 - len[last] - 1]) ? last : getLink(last, c);
  if (go(p, c) == -1) {
    len[sz] = len[p] + 2;
    to[p].push_back(make_pair(c, sz));
    int q;
    if (len[sz] == 1)
      q = 1;
    else {
      q = getLink(p, c);
      assert(getLink(p, c) == getLinkNaive(p, c));
      q = go(q, c);
    }
    lnk[sz] = q;
    if (lnk[lnk[q]] > 1) {
      if (s[sn - 1 - len[lnk[sz]] - 1] == s[sn - 1 - len[lnk[lnk[sz]]] - 1])
        strict[sz] = lnk[lnk[sz]];
      else
        strict[sz] = lnk[sz];
    } else
      strict[sz] = lnk[sz];
    sz++;
  }
  last = go(p, c);
  return cnt[last] = cnt[lnk[last]] + 1;
}
long long start[maxn], finish[maxn];
char t[maxn];
int main() {
  gets(t);
  gets(t);
  int n = strlen(t);
  init();
  for (int i = 0; i < n; i++) finish[i] = add(t[i]);
  init();
  for (int i = n - 1; i >= 0; i--) start[i] = add(t[i]);
  const long long mod = 51123987;
  for (int i = n - 2; i >= 0; i--) {
    start[i] += start[i + 1];
    if (start[i] >= mod) start[i] -= mod;
  }
  long long ans = ((long long)start[0] * (start[0] - 1) / 2) % mod;
  for (int i = 1; i < n; i++) {
    ans -= (finish[i - 1] * start[i]) % mod;
    if (ans < 0) ans += mod;
  }
  cout << ans << endl;
  return 0;
}
