#include <bits/stdc++.h>
using namespace std;
char str[2001111];
char s[2 * 2001111];
long long d[2 * 2001111], l[2001111], r[2001111], t[2001111];
int main() {
  long long n;
  scanf("%lld", &n);
  scanf("%s", str);
  for (long long i = 0; i < 2 * n + 1; i++) {
    if (i % 2 == 1)
      s[i] = str[i / 2];
    else
      s[i] = ' ';
  }
  long long all = 0, j = 0;
  for (long long i = 0; i < 2 * n + 1; i++) {
    long long mirror = 2 * j - i;
    d[i] = min(d[mirror], max(0LL, j + d[j] - i));
    while (i - d[i] >= 0 && i + d[i] < 2 * n + 1 && s[i - d[i]] == s[i + d[i]])
      d[i]++;
    if (i + d[i] > j + d[j]) j = i;
    all += d[i] / 2;
    l[(i - d[i] + 1) / 2]--;
    l[(i + 1) / 2]++;
    r[i / 2 + 1]++;
    r[(i + d[i] + 1) / 2]--;
  }
  all %= 51123987;
  long long ans = ((all * (all - 1)) / 2) % 51123987;
  for (int i = 2001111; i--; t[i] = (t[i + 1] + l[i]) % 51123987)
    l[i] += l[i + 1];
  for (int i = 0; ++i < 2001111; ans -= (r[i] * t[i + 1]) % 51123987)
    r[i] += r[i - 1];
  printf("%lld\n", (ans % 51123987 + 51123987) % 51123987);
  return 0;
}
