#include <bits/stdc++.h>
using namespace std;
namespace IO {
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 23) + 1];
inline int read() {
  register char ch =
      (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),
       (iS == iT ? EOF : *iS++) : *iS++);
  register int x = 0;
  register char t = 0;
  while (ch < '0' || ch > '9')
    t |= ch == '-', ch = (iS == iT ? iT = (iS = ibuf) +
                                          fread(ibuf, 1, (1 << 20) + 1, stdin),
                          (iS == iT ? EOF : *iS++) : *iS++);
  while (ch >= '0' && ch <= '9')
    x = x * 10 + (ch ^ 48),
    ch = (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
  return t ? -x : x;
}
inline void putc(char ch) { out[len++] = ch; }
template <class T>
inline void write(T x) {
  if (x < 0) putc('-'), x = -x;
  if (x > 9) write(x / 10);
  out[len++] = x % 10 + 48;
}
inline int isf(char x) { return (x >= 'a' && x <= 'z'); }
inline int readstr(char *m) {
  register char ch =
      (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),
       (iS == iT ? EOF : *iS++) : *iS++);
  register int x = 0;
  while (!isf(ch))
    ch = (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
  while (isf(ch))
    m[++x] = ch,
    ch = (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
  m[++x] = 0;
  return x - 1;
}
inline void flush() {
  fwrite(out, 1, len, stdout);
  len = 0;
}
}  // namespace IO
using IO::flush;
using IO::putc;
using IO::read;
using IO::readstr;
using IO::write;
const int N = 2e6 + 10, mod = 51123987;
char str[N << 1], input[N];
int p[N << 1], ans, del, sum, n;
inline void getc(char *a, char *b, int n) {
  int len = 0;
  b[len++] = '~';
  b[len++] = '|';
  for (int i = 1; i <= n; i++) {
    b[len++] = a[i];
    b[len++] = '|';
  }
  b[n * 2 + 2] = 0;
  len--;
}
int pre[2][N << 1];
inline void add(int typ, int l, int r, int v) {
  if (l > r) return;
  (pre[typ][l] += v) %= mod;
  (pre[typ][r + 1] -= v) %= mod;
}
int main() {
  n = readstr(input);
  getc(input, str, n);
  ans = 0;
  for (int i = 1, r = 0, mid = 0; i <= n * 2 + 1; i++) {
    if (i < r) p[i] = min(p[(mid << 1) - i], r - i);
    while (str[i - p[i]] == str[i + p[i]]) p[i]++;
    if (i + p[i] > r) r = i + p[i], mid = i;
    (ans += p[i] >> 1) %= mod;
  }
  ans = 1ll * (ans - 1) * ans / 2 % mod;
  for (int i = n * 2 + 1; i; i--) {
    add(0, i - p[i] + 1, i, 1);
  }
  for (int i = 1; i <= n * 2 + 1; i++) {
    add(1, i, i + p[i] - 1, 1);
  }
  for (int i = 1; i <= n * 2 + 1; i++) {
    for (int j = 0; j < 2; j++) {
      (pre[j][i] += pre[j][i - 1]) %= mod;
    }
  }
  for (int i = 2; i < n * 2; i += 2) {
    (sum += pre[1][i]) %= mod;
    (del += 1ll * pre[0][i + 2] * sum % mod) %= mod;
  }
  printf("%d\n", (ans - del + mod) % mod);
  return 0;
}
