Problem: In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam». 

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3 2. 1..3 cross with 2..2 3. 1..3 cross with 3..3 4. 1..3 cross with 3..4 5. 3..3 cross with 3..4 6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from a to z).

Output

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

Examples

Input

4
babb


Output

6


Input

2
aa


Output

2

Solution (in CPP):

Solution:
#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;
}