#include <bits/stdc++.h>
using namespace std;
template <class A>
void rd(vector<A> &v);
template <class T>
void rd(T &x) {
  cin >> x;
}
template <class H, class... T>
void rd(H &h, T &...t) {
  rd(h);
  rd(t...);
}
template <class A>
void rd(vector<A> &x) {
  for (auto &a : x) rd(a);
}
template <class T>
bool ckmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
void __p(T a) {
  cout << a;
}
template <typename T, typename F>
void __p(pair<T, F> a) {
  cout << "{";
  __p(a.first);
  cout << ",";
  __p(a.second);
  cout << "}\n";
}
template <typename T>
void __p(std::vector<T> a) {
  cout << "{";
  for (auto it = a.begin(); it < a.end(); it++)
    __p(*it), cout << ",}\n"[it + 1 == a.end()];
}
template <typename T, typename... Arg>
void __p(T a1, Arg... a) {
  __p(a1);
  __p(a...);
}
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout << name << " : ";
  __p(arg1);
  cout << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  int bracket = 0, i = 0;
  for (;; i++)
    if (names[i] == ',' && bracket == 0)
      break;
    else if (names[i] == '(')
      bracket++;
    else if (names[i] == ')')
      bracket--;
  const char *comma = names + i;
  cout.write(names, comma - names) << " : ";
  __p(arg1);
  cout << " | ";
  __f(comma + 1, args...);
}
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  cout.precision(15);
  cout << fixed;
  if (((int)(s).size())) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
template <const int &MOD>
struct _m_int {
  int val;
  _m_int(int64_t v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int inv_mod(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int64_t() const { return val; }
  _m_int &operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  _m_int &operator-=(const _m_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  _m_int &operator*=(const _m_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  _m_int &operator/=(const _m_int &other) { return *this *= other.inv(); }
  friend _m_int operator+(const _m_int &a, const _m_int &b) {
    return _m_int(a) += b;
  }
  friend _m_int operator-(const _m_int &a, const _m_int &b) {
    return _m_int(a) -= b;
  }
  friend _m_int operator*(const _m_int &a, const _m_int &b) {
    return _m_int(a) *= b;
  }
  friend _m_int operator/(const _m_int &a, const _m_int &b) {
    return _m_int(a) /= b;
  }
  _m_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  _m_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  _m_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }
  _m_int inv() const { return inv_mod(val); }
  _m_int pow(int64_t p) const {
    if (p < 0) return inv().pow(-p);
    _m_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
  friend ostream &operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};
extern const int MOD = 51123987;
using mint = _m_int<MOD>;
const int MAX_N = 2e6 + 7;
vector<pair<int, int>> __next__[MAX_N];
int length[2 * MAX_N], suffix_link[MAX_N], chain_length[MAX_N];
mint __count__[MAX_N], ans;
string s;
mint sub = 0, proper = 0;
struct palindromic_ {
  int total_nodes;
  int max_suffix;
  palindromic_() {
    length[1] = -1, suffix_link[1] = 1, chain_length[1] = 0;
    length[2] = 0, suffix_link[2] = 1, chain_length[2] = 0;
    total_nodes = 2;
    max_suffix = 2;
  }
  int find(int i, int x) {
    for (auto [c, j] : __next__[i]) {
      if (c == x) return j;
    }
    return -1;
  }
  void upd(int i, int x, int v) {
    assert(find(i, x) == -1);
    __next__[i].emplace_back(x, v);
    return;
  }
  bool add_char(char _c) {
    s.push_back(_c);
    int pos = int(s.size()) - 1;
    int cur_suffix = max_suffix, cur_length = 0;
    int c = s[pos] - 'a';
    while (true) {
      cur_length = length[cur_suffix];
      if (pos - 1 - cur_length >= 0 && s[pos - 1 - cur_length] == s[pos]) {
        break;
      }
      cur_suffix = suffix_link[cur_suffix];
    }
    if (find(cur_suffix, c) > 0) {
      max_suffix = find(cur_suffix, c);
      ++__count__[max_suffix];
      return false;
    }
    int now = ++total_nodes;
    ++__count__[now];
    max_suffix = now;
    length[now] = length[cur_suffix] + 2;
    upd(cur_suffix, c, now);
    if (length[now] == 1) {
      suffix_link[now] = 2;
      chain_length[now] = 1;
      return true;
    }
    while (true) {
      cur_suffix = suffix_link[cur_suffix];
      cur_length = length[cur_suffix];
      if (pos - 1 - cur_length >= 0 && s[pos - 1 - cur_length] == s[pos]) {
        suffix_link[now] = find(cur_suffix, c);
        break;
      }
    }
    chain_length[now] = 1 + chain_length[suffix_link[now]];
    return true;
  }
  mint dp_x;
  void dfs(int R, mint V) {
    stack<pair<int, mint>> st;
    st.push({R, V});
    while (((int)(st).size())) {
      auto [i, dp_i] = st.top();
      st.pop();
      for (auto &[_, x] : __next__[i]) {
        if (length[x] == 1)
          dp_x = 1;
        else if (length[x] == 2)
          dp_x = 3;
        else {
          dp_x = dp_i + 2 * mint(chain_length[x]) - 1;
        }
        proper += __count__[x] * dp_i;
        sub += __count__[x] * dp_x;
        st.push({x, dp_x});
      }
    }
  }
  void fun() {
    for (int i = total_nodes; i >= 1; --i) {
      int j = suffix_link[i];
      __count__[j] += __count__[i];
    }
    int R1 = 1, R2 = 2;
    mint V = 0;
    dfs(R1, V);
    dfs(R2, V);
    return;
  }
};
palindromic_ pdt;
void odd_manacher(int n) {
  for (int i = int(0); i < int(n); ++i) length[i] = 0;
  int loc = 0;
  for (int i = 1; i < n; i++) {
    if (i <= loc + length[loc]) {
      length[i] = min(length[loc - (i - loc)], loc + length[loc] - i);
    }
    for (; i - length[i] > 0 && i + length[i] < n - 1 &&
           s[i - length[i] - 1] == s[i + length[i] + 1];
         ++length[i])
      ;
    if (i + length[i] > loc + length[loc]) {
      loc = i;
    }
  }
}
signed main() {
  setIO();
  int n = 2e6;
  rd(n);
  for (int i = int(0); i < int(n); ++i) {
    char c = 'a';
    rd(c);
    pdt.add_char(c);
  }
  pdt.fun();
  s.resize(2 * n + 1);
  for (int i = n - 1; i >= 0; --i) {
    s[2 * i + 1] = s[i];
  }
  for (int i = 0; i < 2 * n + 1; i += 2) {
    s[i] = 0;
  }
  mint ans = 0;
  odd_manacher(2 * n + 1);
  for (int i = int(0); i < int(n + 1); ++i) suffix_link[i] = 0;
  for (int i = int(0); i < int(2 * n + 1); ++i) {
    int st = (i - length[i]) / 2, en = (i + length[i]) / 2;
    if (st >= en) continue;
    ++suffix_link[st];
    --suffix_link[en];
  }
  for (int i = int(1); i < int(n + 1); ++i)
    suffix_link[i] += suffix_link[i - 1];
  for (int i = int(0); i < int(2 * n + 1); ++i) {
    int st = (i - length[i]) / 2, en = (i + length[i]) / 2;
    if (st >= en) continue;
    if ((en - st) % 2 == 1) {
      ++suffix_link[(en + st) / 2];
    }
  }
  {
    for (int i = int(0); i < int(n); ++i) __count__[i] = 0, chain_length[i] = 0;
    auto add_a = [&](int l, int r) -> void {
      ++__count__[l];
      if (r == n - 1) return;
      --__count__[r + 1];
      chain_length[r + 1] -= r - l + 1;
    };
    for (int i = int(0); i < int(2 * n + 1); ++i) {
      int st = (i - length[i]) / 2, en = (i + length[i]) / 2;
      if (st >= en) continue;
      int mid = (st + en - 1) / 2;
      add_a(st, mid);
    }
    for (int i = int(1); i < int(n); ++i) __count__[i] += __count__[i - 1];
    for (int i = int(0); i < int(n); ++i) __count__[i] += chain_length[i];
    for (int i = int(1); i < int(n); ++i) __count__[i] += __count__[i - 1];
    for (int i = int(0); i < int(n); ++i)
      ans += (mint)suffix_link[i] * (mint)__count__[i];
  }
  {
    for (int i = int(0); i < int(n); ++i) __count__[i] = 0, chain_length[i] = 0;
    auto add_a = [&](int l, int r) -> void {
      ++__count__[l];
      if (r == n - 1) return;
      --__count__[r + 1];
      chain_length[r + 1] -= r - l + 1;
    };
    for (int i = int(0); i < int(2 * n + 1); ++i) {
      int st = (i - length[i]) / 2, en = (i + length[i]) / 2;
      if (st >= en) continue;
      int mid = (st + en - 1) / 2;
      add_a(n - 1 - (en - 1), n - 1 - (mid + 1));
    }
    for (int i = int(1); i < int(n); ++i) __count__[i] += __count__[i - 1];
    for (int i = int(0); i < int(n); ++i) __count__[i] += chain_length[i];
    for (int i = int(1); i < int(n); ++i) __count__[i] += __count__[i - 1];
    for (int i = int(0); i < int(n); ++i)
      ans += (mint)suffix_link[i] * (mint)__count__[n - 1 - i];
  }
  mint total_palindromes = 0;
  for (int i = int(0); i < int(2 * n + 1); ++i) {
    int st = (i - length[i]) / 2, en = (i + length[i]) / 2;
    if (st >= en) continue;
    total_palindromes += (en - st + 1) / 2;
  }
  ans -= sub;
  ans += proper;
  ans -= total_palindromes;
  ans /= mint(2);
  cout << ans;
}
