#include <bits/stdc++.h>
using std::abs;
using std::bitset;
using std::cerr;
using std::cin;
using std::copy;
using std::cout;
using std::endl;
using std::fill;
using std::fixed;
using std::greater;
using std::lower_bound;
using std::map;
using std::max;
using std::min;
using std::next_permutation;
using std::pair;
using std::priority_queue;
using std::queue;
using std::reverse;
using std::rotate;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::tie;
using std::tuple;
using std::unique;
using std::unordered_map;
using std::unordered_set;
using std::upper_bound;
using std::vector;
int const INF = (int)1e9;
long long const INFL = (long long)1e18;
long double const PI = 3.1415926535897932384626433832795028;
int const MOD = 51123987;
int const N = 2000100;
char s[N];
int stupid(int n) {
  auto const pal = [](int a, int b) {
    for (--b; a < b; ++a, --b) {
      if (s[a] != s[b]) return false;
    }
    return true;
  };
  long long ans = 0;
  for (int a = 0; a < n; ++a) {
    for (int b = a + 1; b <= n; ++b) {
      if (!pal(a, b)) continue;
      for (int c = 0; c < n; ++c) {
        for (int d = c + 1; d <= n; ++d) {
          if (a == c && b == d) continue;
          if (b <= c || d <= a) continue;
          if (!pal(c, d)) continue;
          ++ans;
        }
      }
    }
  }
  ans /= 2;
  return ans % MOD;
}
int a[N + N];
int d[N + N];
int st[N], fn[N];
void solve() {
  int n;
  scanf("%d ", &n);
  gets(s);
  int sz = 0;
  a[sz++] = N;
  for (int i = 0; i < n; ++i) {
    a[sz++] = s[i] - 'a';
    a[sz++] = N;
  }
  int l = 0, r = 0;
  for (int i = 0; i < sz; ++i) {
    int& x = d[i];
    if (i < r) {
      x = min(r - i, d[l + r - i]);
    }
    while (i >= x && i + x < sz && a[i - x] == a[i + x]) {
      ++x;
    }
    if (i + x > r) {
      l = i - x;
      r = i + x;
    }
  }
  long long cnt = 0;
  for (int i = 1; i < sz - 1; ++i) {
    if (i % 2 == 0) {
      int x = i / 2;
      int h = d[i] / 2;
      if (h == 0) continue;
      cnt += h;
      ++st[x - h];
      --st[x];
      ++fn[x];
      --fn[x + h];
    } else {
      int x = i / 2;
      int h = d[i] / 2 - 1;
      cnt += h + 1;
      ++st[x - h];
      --st[x + 1];
      ++fn[x];
      --fn[x + h + 1];
    }
  }
  for (int i = 1; i <= n; ++i) {
    st[i] += st[i - 1];
    fn[i] += fn[i - 1];
  }
  cnt %= MOD;
  long long pairs = (long long)cnt * (cnt - 1) / 2;
  long long no = 0;
  long long sums = 0;
  for (int i = n - 1; i >= 0; --i) {
    no += fn[i] * sums % MOD;
    sums += st[i];
    sums %= MOD;
  }
  no %= MOD;
  long long ans = pairs - no + MOD;
  ans %= MOD;
  cout << ans << endl;
}
int main() {
  cout.precision(15);
  cout << fixed;
  cerr.precision(9);
  cerr << fixed;
  srand(1510);
  solve();
}
