#include <bits/stdc++.h>
using namespace std;
namespace Fastio {
enum io_flags {
  ignore_int = 1 << 0,
  char_enter = 1 << 1,
  flush_stdout = 1 << 2,
  flush_stderr = 1 << 3,
  endline = char_enter | flush_stdout
};
enum number_type_flags {
  output_double_stable = 1 << 0,
  output_double_faster = 1 << 1
};
struct Reader {
  char endch;
  Reader() { endch = '\0'; }
  Reader& operator>>(io_flags f) {
    if (f & ignore_int) {
      endch = getchar();
      while ((!isdigit(endch)) && endch != '-' && endch != EOF)
        endch = getchar();
      while (isdigit(endch = getchar()))
        ;
    }
    return *this;
  }
  Reader& operator>>(char& ch) {
    ch = getchar();
    while (ch == ' ' || ch == '\r' || ch == '\n' || ch == '\t') ch = getchar();
    return *this;
  }
  Reader& operator>>(double& lf) {
    bool flag = 0;
    endch = getchar();
    while ((!isdigit(endch)) && endch != '-' && endch != EOF) endch = getchar();
    if (endch == '-') flag = 1, endch = getchar();
    lf = endch & 15;
    while (isdigit(endch = getchar())) lf = lf * 10 + (endch & 15);
    if (endch == '.') {
      double digit = 0.1;
      while (isdigit(endch = getchar())) {
        lf += (endch & 15) * digit;
        digit *= 0.1;
      }
    }
    if (flag) lf = -lf;
    return *this;
  }
  template <typename Int>
  Reader& operator>>(Int& d) {
    bool flag = 0;
    endch = getchar();
    while ((!isdigit(endch)) && endch != '-' && endch != EOF) endch = getchar();
    if (endch == '-') flag = 1, endch = getchar();
    d = endch & 15;
    while (isdigit(endch = getchar())) d = (d << 3) + (d << 1) + (endch & 15);
    if (flag) d = -d;
    return *this;
  }
  template <typename Int>
  inline Int get() {
    bool flag = 0;
    endch = getchar();
    while ((!isdigit(endch)) && endch != '-' && endch != EOF) endch = getchar();
    if (endch == '-') flag = 1, endch = getchar();
    Int d = endch & 15;
    while (isdigit(endch = getchar())) d = (d << 3) + (d << 1) + (endch & 15);
    if (flag) d = -d;
    return d;
  }
} read;
struct Writer {
  Writer& operator<<(io_flags f) {
    if (f & char_enter) putchar(10);
    if (f & flush_stdout) fflush(stdout);
    if (f & flush_stderr) fflush(stderr);
    return *this;
  }
  Writer& operator<<(const char* ch) {
    while (*ch) putchar(*(ch++));
    return *this;
  }
  Writer& operator<<(const char ch) {
    putchar(ch);
    return *this;
  }
  template <typename Int>
  Writer& operator<<(Int x) {
    static char buffer[33];
    static int top = 0;
    if (!x) {
      putchar('0');
      return *this;
    }
    if (x < 0) putchar('-'), x = ~x + 1;
    while (x) {
      buffer[++top] = '0' | (x % 10);
      x /= 10;
    }
    while (top) putchar(buffer[top--]);
    return *this;
  }
  inline void operator()(double val, int eps_digit = 6, char endch = '\0',
                         number_type_flags flg = output_double_faster) {
    if (flg & output_double_stable) {
      static char output_format[10];
      sprintf(output_format, "%%.%dlf", eps_digit);
      printf(output_format, val);
    } else if (flg & output_double_faster) {
      if (val < 0) {
        putchar('-');
        val = -val;
      }
      (*this) << (long long)val;
      val -= (long long)val;
      putchar('.');
      double eps_number = 0.5;
      for (int i = 1; i <= eps_digit; i++) eps_number /= 10;
      val += eps_number;
      while (eps_digit--) {
        val *= 10;
        putchar((int)val | '0');
        val -= (int)val;
      }
    } else {
      (*this) << "1.#ERROR_NOT_IDENTIFIED_FLAG";
    }
    if (endch) putchar(endch);
  }
} write;
}  // namespace Fastio
using namespace Fastio;
namespace File_IO {
void init_IO() {
  freopen("Palisection.in", "r", stdin);
  freopen("Palisection.out", "w", stdout);
}
}  // namespace File_IO
const int MAXN = 2e6 + 7, P = 51123987, inv2 = (P >> 1) + 1;
int lef[MAXN], rig[MAXN];
int len[MAXN << 1], l[MAXN << 1], r[MAXN << 1];
char S[MAXN << 1];
int n, length;
void manacher() {
  int mid = 0, mxr = 0;
  for (int i = 1; i <= length; i++) {
    if (i <= mxr) len[i] = min(len[(mid << 1) - i], mid + len[mid] - i);
    while (i - len[i] > 0 && i + len[i] <= length &&
           S[i - len[i]] == S[i + len[i]])
      len[i]++;
    if (i + len[i] > mxr) mxr = i + len[i], mid = i;
  }
}
int fix(const int a) { return (a % P + P) % P; }
int main() {
  read >> n;
  S[++length] = '$';
  for (int i = 1; i <= n; i++) S[++length] = getchar(), S[++length] = '$';
  manacher();
  for (int i = 1; i <= length; i++)
    l[i - len[i] + 1]++, l[i + 1]--, r[i]++, r[i + len[i]]--;
  int res = 0;
  for (int i = 1; i <= length; i++) {
    (res += (len[i] >> 1)) %= P, (l[i] += l[i - 1]) %= P,
        (r[i] += r[i - 1]) %= P;
    if (S[i] ^ '$') lef[i >> 1] = l[i], rig[i >> 1] = r[i];
  }
  for (int i = 1; i <= n; i++) (lef[n - i + 1] += lef[n - i + 2]) %= P;
  res = 1ll * res * fix(res - 1) % P * inv2 % P;
  for (int i = 1; i <= n; i++)
    res = fix(res - (long long)rig[i] * lef[i + 1] % P);
  write << res << endline;
  return 0;
}
