#include <bits/stdc++.h>
const int MAXN = 2e6 + 5;
const int MOD = 51123987;
int N;
char s[MAXN], S[MAXN << 1];
int R[MAXN << 1];
void init() {
  char *p = S + 1, *p2 = s;
  *p++ = '@', *p++ = '#';
  while (*p2) {
    *p++ = *p2++;
    *p++ = '#';
  }
  *p++ = '$';
}
long long Num[MAXN], Sum[MAXN], Sum2[MAXN];
long long ans;
void manacher() {
  init();
  int n = strlen(S + 1);
  int mr = 0, id = 0;
  for (int i = 1; i <= n; ++i) {
    if (i < mr) {
      R[i] = std::min(R[id * 2 - i], mr - i);
    } else {
      R[i] = 1;
    }
    while (S[i - R[i]] == S[i + R[i]]) {
      ++R[i];
    }
    if (R[i] + i > mr) {
      mr = R[i] + i;
      id = i;
    }
    Num[i / 2]++;
    if (isalpha(S[i])) {
      Num[i / 2 + (R[i] - 1) / 2 + 1]--;
    } else {
      Num[i / 2 + (R[i] - 1) / 2]--;
    }
    (ans += R[i] / 2) %= MOD;
  }
  ans = ans * (ans - 1) / 2;
  for (int i = 1; i <= N; ++i) {
    Num[i] += Num[i - 1];
    Sum[i] = Sum[i - 1] + Num[i];
    Sum2[i] = Sum2[i - 1] + Sum[i];
  }
  for (int i = 3; i <= N * 2 + 1; ++i) {
    if (isalpha(S[i])) {
      int p = i / 2;
      ans -= Sum2[p - 1] - Sum2[p - (R[i] - 1) / 2 - 2];
    } else {
      int p = i / 2 - 1;
      ans -= Sum2[p - 1] - Sum2[p - (R[i] - 1) / 2 - 1];
    }
    ans %= MOD;
  }
}
int main() {
  scanf("%d%s", &N, s);
  manacher();
  printf("%lld\n", (ans + MOD) % MOD);
  return 0;
}
