#include <bits/stdc++.h>
using namespace std;
const int mod = 51123987;
int len, n;
char s[4000010], tmp[2000010];
long long p[4000010];
long long sum, ans;
long long le[4000010], ri[4000010];
int main() {
  scanf("%d%s", &len, tmp + 1);
  s[++n] = '@';
  for (int i = 1; i <= len; i++) {
    s[++n] = '#';
    s[++n] = tmp[i];
  }
  s[++n] = '#';
  long long id = 0, mx = 0;
  for (long long i = 1; i <= n; i++) {
    p[i] = ((mx > i) ? min(p[id * 2 - i], mx - i) : 1);
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
      mx = i + p[i];
      id = i;
    }
    sum += 1ll * p[i] / 2;
    sum %= mod;
    le[i - p[i]]++;
    le[i]--;
    ri[i - 1]++;
    ri[i + p[i] - 1]--;
  }
  sum = sum * (sum - 1) / 2;
  sum %= mod;
  for (int i = 1; i <= n; i++) {
    le[i] += le[i - 1];
    ri[i] += ri[i - 1];
    if (i % 2 == 0) {
      sum -= 1ll * ans * le[i] % mod;
      sum = (sum + mod) % mod;
      ans = (ans + ri[i]) % mod;
    }
  }
  cout << (sum + mod) % mod;
  return 0;
}
