#include <bits/stdc++.h>
using namespace std;
const long long MOD = 51123987;
int n;
int f[5000000];
long long l[5000000], r[5000000];
char st[5000000];
int main() {
  char ch;
  scanf("%d%*c", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%c", &ch);
    st[i * 2] = '#';
    st[i * 2 + 1] = ch;
  }
  st[n * 2] = '#';
  n = n * 2 + 1;
  long long ans = 0;
  memset(f, 0, sizeof(f));
  memset(l, 0, sizeof(l));
  memset(r, 0, sizeof(r));
  f[0] = 0;
  int far = 0, id = 0;
  for (int i = 1; i < n; ++i) {
    if (far >= i)
      f[i] = min(f[2 * id - i], far - i);
    else
      f[i] = 0;
    while (i - f[i] > 0 && st[i + f[i] + 1] == st[i - f[i] - 1]) f[i]++;
    if (i + f[i] > far) {
      far = i + f[i];
      id = i;
    }
    int ll = (i - f[i] + 1) / 2, rr = (i + f[i] - 1) / 2;
    l[ll]++;
    if (st[i] == '#')
      l[(i + 1) / 2]--;
    else
      l[(i + 2) / 2]--;
    r[rr]++;
    if (st[i] == '#')
      r[(i - 1) / 2]--;
    else if (i > 1)
      r[(i - 2) / 2]--;
    ans = (ans + (f[i] + 1) / 2) % MOD;
  }
  ans = ((ans * (ans - 1)) / 2) % MOD;
  n = (n - 1) / 2;
  for (int i = 1; i < n; ++i) l[i] = (l[i - 1] + l[i]) % MOD;
  for (int i = n - 2; i >= 0; --i) r[i] = (r[i + 1] + r[i]) % MOD;
  for (int i = 1; i < n; ++i) r[i] = (r[i - 1] + r[i]) % MOD;
  for (int i = 1; i < n; ++i) {
    ans -= l[i] * r[i - 1];
    if (ans < 0) ans += (((-ans) / MOD) + 1) * MOD;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}
