#include <bits/stdc++.h>
using namespace std;
const int md = 51123987;
long long t, ans = 0, t1, t2, mult;
string s;
long long o[2000020], c[2000020], clos[2000020], open[2000020];
int d1[2000020], d2[2000020], i, j, l, r, n, m, k;
void add_open(int l, int r) {
  o[l]++;
  o[r + 1]--;
}
void add_clos(int l, int r) {
  c[l]++;
  c[r + 1]--;
}
int main() {
  cin >> n;
  cin >> s;
  int l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 0 : min(d1[l + r - i], r - i + 1));
    while (i + k < n && i - k >= 0 && s[i + k] == s[i - k]) ++k;
    d1[i] = k;
    --k;
    ans += d1[i];
    if (i + k > r) l = i - k, r = i + k;
  }
  l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1;
    while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k]) ++k;
    d2[i] = --k;
    ans += d2[i];
    if (i + k - 1 > r) l = i - k, r = i + k - 1;
  }
  for (i = 0; i < n; ++i) {
    add_open(i - d1[i] + 1, i);
    add_clos(i, i + d1[i] - 1);
    if (d2[i] > 0) {
      add_open(i - d2[i], i - 1);
      add_clos(i, i + d2[i] - 1);
    }
  }
  for (i = 0; i < n; ++i) {
    t = t + o[i];
    open[i] = t;
  }
  t = 0;
  for (i = 0; i < n; ++i) {
    t = t + c[i];
    clos[i] = (i == 0 ? 0 : clos[i - 1]);
    clos[i] += t;
  }
  t1 = ans;
  t2 = ans - 1;
  if (t1 % 2 == 0)
    t1 /= 2;
  else
    t2 /= 2;
  ans = (t1 % md) * (t2 % md) % md;
  for (i = 1; i < n; ++i) {
    mult = (open[i] % md) * (clos[i - 1] % md) % md;
    ans = (ans - mult + md) % md;
  }
  cout << ans << endl;
}
