#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 5000, mod = 51123987;
int hw[N], n, l[N], r[N];
char st[N];
void solve() {
  st[0] = 1;
  int nn = n * 2 - 1;
  for (int i = nn; i >= 1; i--) st[i] = (i & 1) ? st[(i >> 1) + 1] : '#';
  int mx = 0, mid = 0;
  long long cnt = 0;
  for (int i = 1; i <= nn; i++) {
    hw[i] = i <= mx ? min(hw[2 * mid - i], mx - i + 1) : 1;
    for (; i + hw[i] <= nn && i - hw[i] >= 1 && st[i + hw[i]] == st[i - hw[i]];
         hw[i]++)
      ;
    if (i + hw[i] - 1 > mx) mx = i + hw[i] - 1, mid = i;
    r[i]++, r[i + hw[i]]--;
    l[i - hw[i] + 1]++, l[i + 1]--;
    cnt += (hw[i] + (i & 1)) >> 1;
  }
  cnt %= mod;
  for (int i = 1; i <= nn + 1; i++) l[i] += l[i - 1], r[i] += r[i - 1];
  for (int i = nn; i >= 1; i--)
    if (st[i] != '#')
      l[i] = (l[i] + l[i + 1]) % mod;
    else
      l[i] = l[i + 1];
  long long ans = (cnt * (cnt - 1) >> 1) % mod;
  for (int i = 1; i < nn; i += 2) ans = (ans - 1ll * r[i] * l[i + 1]) % mod;
  cout << (ans + mod) % mod << endl;
}
int main() {
  scanf("%d", &n);
  scanf("%s", st + 1);
  solve();
}
