#include <bits/stdc++.h>
using namespace std;
char s[2000010], str[4000010];
long long p[4000010], n, m, f[4000010], g[4000010], sum, ans, tot, num, mx, id;
int main() {
  scanf("%lld%s", &n, s + 1);
  str[0] = '$';
  for (int i = 1; i <= n; i++) str[i * 2] = s[i], str[i * 2 - 1] = '#';
  m = n * 2 + 1, str[m] = '+';
  for (int i = 1; i <= m; i++) {
    (mx > i) ? p[i] = min(p[2 * id - i], mx - i) : p[i] = 1;
    while (str[i + p[i]] == str[i - p[i]]) p[i]++;
    if (i + p[i] > mx) id = i, mx = i + p[i];
  }
  for (int i = 1; i <= m; i++)
    f[i]++, f[i + p[i] - 1 + 1]--, g[i]++, g[i - p[i] + 1 - 1]--;
  for (int i = 1; i <= m; i++) f[i] = (f[i] + f[i - 1]) % 51123987;
  for (int i = m; i >= 1; i--) g[i] = (g[i] + g[i + 1]) % 51123987;
  for (int i = 1; i <= n; i++)
    ans = (ans + g[i * 2] * sum) % 51123987, sum = (sum + f[i * 2]) % 51123987,
    num = (num + f[i * 2]) % 51123987;
  printf("%lld", ((num - 1) * num / 2 % 51123987 - ans + 51123987) % 51123987);
  return 0;
}
