#include <bits/stdc++.h>
using namespace std;
const int Hash = 743;
const int Mod = 51123987;
int powh[2000005], N, h1[2000005], h2[2000005], start[2000005], finish[2000005],
    a[2000005], b[2000005];
char s[2000005];
int getsub1(int lo, int hi) {
  return lo == 0 ? h1[hi] : h1[hi] - h1[lo - 1] * powh[hi - lo + 1];
}
int getsub2(int lo, int hi) {
  return hi == N - 1 ? h2[lo] : h2[lo] - h2[hi + 1] * powh[hi - lo + 1];
}
int main(void) {
  powh[0] = 1;
  for (int i = 1; i < 2000005; ++i) powh[i] = powh[i - 1] * Hash;
  scanf("%d %s", &N, s);
  int ch = 0;
  for (int i = 0; i < N; ++i) {
    ch = ch * Hash + s[i];
    h1[i] = ch;
  }
  ch = 0;
  for (int i = N - 1; i >= 0; --i) {
    ch = ch * Hash + s[i];
    h2[i] = ch;
  }
  long long tot = 0;
  for (int i = 0; i < N; ++i) {
    int lo = 1, hi = min(i + 1, N - i), mid, ans = 1;
    while (lo <= hi) {
      mid = (lo + hi) / 2;
      int s1 = getsub1(i, i + mid - 1);
      int s2 = getsub2(i - mid + 1, i);
      if (s1 == s2) {
        lo = mid + 1;
        ans = mid;
      } else
        hi = mid - 1;
    }
    tot += ans;
    tot %= Mod;
    a[i - ans + 1] += 1;
    a[i + 1] -= 1;
    b[i] += 1;
    b[i + ans] -= 1;
  }
  for (int i = 0; i + 1 < N; ++i) {
    if (s[i] != s[i + 1]) continue;
    int lo = 1, hi = min(i + 1, N - (i + 1)), mid, ans = 1;
    while (lo <= hi) {
      mid = (lo + hi) / 2;
      int s1 = getsub1(i + 1, i + mid);
      int s2 = getsub2(i - mid + 1, i);
      if (s1 == s2) {
        lo = mid + 1;
        ans = mid;
      } else
        hi = mid - 1;
    }
    tot += ans;
    tot %= Mod;
    a[i - ans + 1] += 1;
    a[i + 1] -= 1;
    b[i + 1] += 1;
    b[i + 1 + ans] -= 1;
  }
  for (int i = 0; i < N; ++i) {
    a[i] %= Mod;
    b[i] %= Mod;
    a[i] += Mod;
    b[i] += Mod;
    start[i] = (i == 0) ? a[i] : start[i - 1] + a[i];
    finish[i] = (i == 0) ? b[i] : finish[i - 1] + b[i];
    start[i] %= Mod;
    finish[i] %= Mod;
  }
  int sf = 0, sol = 0;
  for (int i = 0; i < N; ++i) {
    sol = (sol + (long long)(start[i]) * (long long)(sf) % Mod) % Mod;
    sf = (sf + finish[i]) % Mod;
  }
  cout << ((long long)(tot) * (tot - 1) / 2 - sol + Mod) % Mod << endl;
  return 0;
}
