#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 7, p = 51123987;
int n, m[N], c = 1, l[N], r[N], ans;
char _s[N], s[N];
int main() {
  cin >> n >> _s;
  s[0] = 2;
  for (register int i = 0; i < n; ++i, ++c) s[++c] = _s[i];
  for (register int i = 1, j = 0, k = 0; i <= c; ++i) {
    m[i] = j > i ? min(m[k * 2 - i], j - i) : 1;
    for (; s[i - m[i]] == s[i + m[i]]; ++m[i])
      ;
    if (j < i + m[i]) j = i + m[i], k = i;
  }
  for (register int i(1); i <= (c); ++i)
    l[i - m[i] + 1]++, l[i + 1]--, r[i]++, r[i + m[i]]--,
        (ans += m[i] / 2) %= p;
  ans = 1ll * ans * (ans - 1) / 2 % p;
  for (register int i = 1, t = 0; i <= c; ++i) {
    l[i] += l[i - 1], r[i] += r[i - 1];
    if (!(i & 1)) (ans -= 1ll * l[i] * t % p) %= p, (t += r[i]) %= p;
  }
  return cout << (ans + p) % p, 0;
}
