#include <bits/stdc++.h>
const int maxn = 2000010, mo = 51123987;
int n, w[maxn * 2];
long long ans, l[maxn], r[maxn];
char s[maxn * 2];
inline int min(int x, int y) { return x > y ? y : x; }
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = n + n; i; i--)
    if (i & 1)
      s[i] = s[(i + 1) >> 1];
    else
      s[i] = ' ';
  int right = ans = 1, mid = w[1] = 1;
  for (int i = 2; i < n + n; i++) {
    if (right >= i) w[i] = min(w[mid + mid - i], right - i);
    while (i - w[i] - 1 >= 0 && i + w[i] + 1 <= n + n &&
           s[i - w[i] - 1] == s[i + w[i] + 1])
      w[i]++;
    if (i + w[i] > right) right = i + w[i], mid = i;
    if (i & 1)
      ans += (w[i] >> 1) + 1;
    else
      ans += (w[i] + 1) >> 1;
  }
  for (int i = 1; i < n + n; i++)
    if (i & 1)
      l[((i + 1) >> 1) - (w[i] >> 1)] += 1, l[((i + 1) >> 1) + 1] += -1;
    else
      l[(i >> 1) - ((w[i] + 1) >> 1) + 1] += 1, l[(i >> 1) + 1] += -1;
  for (int i = 1; i <= n; i++) l[i] += l[i - 1];
  for (int i = n - 1; i; i--) l[i] = (l[i] + l[i + 1]) % mo;
  for (int i = 1; i < n + n; i++)
    if (i & 1)
      r[((i + 1) >> 1) + (w[i] >> 1)] += 1, r[((i + 1) >> 1) - 1] += -1;
    else
      r[(i >> 1) + ((w[i] + 1) >> 1)] += 1, r[(i >> 1)] += -1;
  for (int i = n; i; i--) r[i] = (r[i] + r[i + 1]) % mo;
  if (ans % 2)
    ans = (ans % mo) * ((ans - 1) / 2 % mo) % mo;
  else
    ans = (ans / 2 % mo) * ((ans - 1) % mo) % mo;
  for (int i = 1; i < n; i++) ans = (ans - r[i] * l[i + 1]) % mo;
  printf("%d\n", (int)((ans % mo + mo) % mo));
}
