#include <bits/stdc++.h>
using namespace std;
const long long M30 = ((long long)1 << 30) - 1;
const long long M31 = ((long long)1 << 31) - 1;
const long long MOD = ((long long)1 << 61) - 1;
const long long MOD2 = 998244353;
const long long BASE = 123456789;
unsigned long long modulo(unsigned long long x) {
    unsigned long long xu = x >> 61;
    unsigned long long xd = x & MOD;
    unsigned long long res = xu + xd;
    if(res >= MOD) { res -= MOD; }
    return res;
}
unsigned long long mul(unsigned long long a, unsigned long long b) {
    unsigned long long au = a >> 31;
    unsigned long long ad = a & M31;
    unsigned long long bu = b >> 31;
    unsigned long long bd = b & M31;
    unsigned long long mid = au * bd + ad * bu;
    unsigned long long midu = mid >> 30;
    unsigned long long midd = mid & M30;
    return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
struct rolling_hash {
    vector<unsigned long long> POW, S;
    rolling_hash(string s) {
        int N = s.size();
        POW.resize(N + 1);
        POW[0] = 1;
        for(int i = 0; i < N; i++) { POW[i + 1] = mul(POW[i], BASE); }
        S.resize(N + 1);
        S[N] = 0;
        for(int i = N - 1; i >= 0; i--) { S[i] = modulo(mul(S[i + 1], BASE) + s[i]); }
    }
    unsigned long long get(int L, int R) { return modulo(S[L] + MOD - mul(S[R], POW[R - L])); }
};
vector<int> manacher(string &S) {
    int N = S.size();
    vector<int> ans(N, 0);
    int i = 0, j = 0;
    while(i < N) {
        while(i >= j && i + j < N && S[i - j] == S[i + j]) { j++; }
        ans[i] = j;
        int k = 1;
        while(i >= k && i + k < N && k + ans[i - k] < j) {
            ans[i + k] = ans[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ans;
}

// https://nyaannyaan.github.io/library/hashmap/hashmap.hpp
namespace HashMapImpl {
using u32 = uint32_t;
using u64 = uint64_t;

template <typename Key, typename Data> struct HashMapBase;

template <typename Key, typename Data> struct itrB : iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data *, Data &> {
    using base = iterator<bidirectional_iterator_tag, Data, ptrdiff_t, Data *, Data &>;
    using ptr = typename base::pointer;
    using ref = typename base::reference;

    u32 i;
    HashMapBase<Key, Data> *p;

    explicit constexpr itrB() : i(0), p(nullptr) {}
    explicit constexpr itrB(u32 _i, HashMapBase<Key, Data> *_p) : i(_i), p(_p) {}
    explicit constexpr itrB(u32 _i, const HashMapBase<Key, Data> *_p) : i(_i), p(const_cast<HashMapBase<Key, Data> *>(_p)) {}
    friend void swap(itrB &l, itrB &r) { swap(l.i, r.i), swap(l.p, r.p); }
    friend bool operator==(const itrB &l, const itrB &r) { return l.i == r.i; }
    friend bool operator!=(const itrB &l, const itrB &r) { return l.i != r.i; }
    const ref operator*() const { return const_cast<const HashMapBase<Key, Data> *>(p)->data[i]; }
    ref operator*() { return p->data[i]; }
    ptr operator->() const { return &(p->data[i]); }

    itrB &operator++() {
        assert(i != p->cap && "itr::operator++()");
        do {
            i++;
            if(i == p->cap) break;
            if(p->flag[i] == true && p->dflag[i] == false) break;
        } while(true);
        return (*this);
    }
    itrB operator++(int) {
        itrB it(*this);
        ++(*this);
        return it;
    }
    itrB &operator--() {
        do {
            i--;
            if(p->flag[i] == true && p->dflag[i] == false) break;
            assert(i != 0 && "itr::operator--()");
        } while(true);
        return (*this);
    }
    itrB operator--(int) {
        itrB it(*this);
        --(*this);
        return it;
    }
};

template <typename Key, typename Data> struct HashMapBase {
    using u32 = uint32_t;
    using u64 = uint64_t;
    using iterator = itrB<Key, Data>;
    using itr = iterator;

  protected:
    template <typename K> inline u64 randomized(const K &key) const { return u64(key) ^ r; }

    template <typename K, enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr, enable_if_t<is_integral<K>::value, nullptr_t> = nullptr>
    inline u32 inner_hash(const K &key) const {
        return (randomized(key) * 11995408973635179863ULL) >> shift;
    }
    template <typename K, enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr, enable_if_t<is_integral<decltype(K::first)>::value, nullptr_t> = nullptr,
              enable_if_t<is_integral<decltype(K::second)>::value, nullptr_t> = nullptr>
    inline u32 inner_hash(const K &key) const {
        u64 a = randomized(key.first), b = randomized(key.second);
        a *= 11995408973635179863ULL;
        b *= 10150724397891781847ULL;
        return (a + b) >> shift;
    }
    template <typename K, enable_if_t<is_same<K, Key>::value, nullptr_t> = nullptr,
              enable_if_t<is_integral<typename K::value_type>::value, nullptr_t> = nullptr>
    inline u32 inner_hash(const K &key) const {
        static constexpr u64 mod = (1LL << 61) - 1;
        static constexpr u64 base = 950699498548472943ULL;
        u64 res = 0;
        for(auto &elem : key) {
            __uint128_t x = __uint128_t(res) * base + (randomized(elem) & mod);
            res = (x & mod) + (x >> 61);
        }
        __uint128_t x = __uint128_t(res) * base;
        res = (x & mod) + (x >> 61);
        if(res >= mod) res -= mod;
        return res >> (shift - 3);
    }

    template <typename D = Data, enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr> inline u32 hash(const D &dat) const { return inner_hash(dat); }
    template <typename D = Data, enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr> inline u32 hash(const D &dat) const {
        return inner_hash(dat.first);
    }

    template <typename D = Data, enable_if_t<is_same<D, Key>::value, nullptr_t> = nullptr> inline Key dtok(const D &dat) const { return dat; }
    template <typename D = Data, enable_if_t<is_same<decltype(D::first), Key>::value, nullptr_t> = nullptr> inline Key dtok(const D &dat) const {
        return dat.first;
    }

    void reallocate(u32 ncap) {
        vector<Data> ndata(ncap);
        vector<bool> nf(ncap);
        shift = 64 - __lg(ncap);
        for(u32 i = 0; i < cap; i++) {
            if(flag[i] == true && dflag[i] == false) {
                u32 h = hash(data[i]);
                while(nf[h]) h = (h + 1) & (ncap - 1);
                ndata[h] = move(data[i]);
                nf[h] = true;
            }
        }
        data.swap(ndata);
        flag.swap(nf);
        cap = ncap;
        dflag.resize(cap);
        fill(std::begin(dflag), std::end(dflag), false);
    }

    inline bool extend_rate(u32 x) const { return x * 2 >= cap; }

    inline bool shrink_rate(u32 x) const { return HASHMAP_DEFAULT_SIZE < cap && x * 10 <= cap; }

    inline void extend() { reallocate(cap << 1); }

    inline void shrink() { reallocate(cap >> 1); }

  public:
    u32 cap, s;
    vector<Data> data;
    vector<bool> flag, dflag;
    u32 shift;
    static u64 r;
    static constexpr uint32_t HASHMAP_DEFAULT_SIZE = 4;

    explicit HashMapBase() : cap(HASHMAP_DEFAULT_SIZE), s(0), data(cap), flag(cap), dflag(cap), shift(64 - __lg(cap)) {}

    itr begin() const {
        u32 h = 0;
        while(h != cap) {
            if(flag[h] == true && dflag[h] == false) break;
            h++;
        }
        return itr(h, this);
    }
    itr end() const { return itr(this->cap, this); }

    friend itr begin(const HashMapBase &h) { return h.begin(); }
    friend itr end(const HashMapBase &h) { return h.end(); }

    itr find(const Key &key) const {
        u32 h = inner_hash(key);
        while(true) {
            if(flag[h] == false) return this->end();
            if(dtok(data[h]) == key) {
                if(dflag[h] == true) return this->end();
                return itr(h, this);
            }
            h = (h + 1) & (cap - 1);
        }
    }

    bool contain(const Key &key) const { return find(key) != this->end(); }

    itr insert(const Data &d) {
        u32 h = hash(d);
        while(true) {
            if(flag[h] == false) {
                if(extend_rate(s + 1)) {
                    extend();
                    h = hash(d);
                    continue;
                }
                data[h] = d;
                flag[h] = true;
                ++s;
                return itr(h, this);
            }
            if(dtok(data[h]) == dtok(d)) {
                if(dflag[h] == true) {
                    data[h] = d;
                    dflag[h] = false;
                    ++s;
                }
                return itr(h, this);
            }
            h = (h + 1) & (cap - 1);
        }
    }

    // tips for speed up :
    // if return value is unnecessary, make argument_2 false.
    itr erase(itr it, bool get_next = true) {
        if(it == this->end()) return this->end();
        s--;
        if(shrink_rate(s)) {
            Data d = data[it.i];
            shrink();
            it = find(dtok(d));
        }
        int ni = (it.i + 1) & (cap - 1);
        if(this->flag[ni]) {
            this->dflag[it.i] = true;
        } else {
            this->flag[it.i] = false;
        }
        if(get_next) ++it;
        return it;
    }

    itr erase(const Key &key) { return erase(find(key)); }

    bool empty() const { return s == 0; }

    int size() const { return s; }

    void clear() {
        fill(std::begin(flag), std::end(flag), false);
        fill(std::begin(dflag), std::end(dflag), false);
        s = 0;
    }

    void reserve(int n) {
        if(n <= 0) return;
        n = 1 << min(23, __lg(n) + 2);
        if(cap < u32(n)) reallocate(n);
    }
};

template <typename Key, typename Data>
uint64_t HashMapBase<Key, Data>::r = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();

} // namespace HashMapImpl

/**
 * @brief Hash Map(base)　(ハッシュマップ・基底クラス)
 */

template <typename Key, typename Val> struct HashMap : HashMapImpl::HashMapBase<Key, pair<Key, Val>> {
    using base = typename HashMapImpl::HashMapBase<Key, pair<Key, Val>>;
    using HashMapImpl::HashMapBase<Key, pair<Key, Val>>::HashMapBase;
    using Data = pair<Key, Val>;

    Val &operator[](const Key &k) {
        typename base::u32 h = base::inner_hash(k);
        while(true) {
            if(base::flag[h] == false) {
                if(base::extend_rate(base::s + 1)) {
                    base::extend();
                    h = base::hash(k);
                    continue;
                }
                base::data[h].first = k;
                base::data[h].second = Val();
                base::flag[h] = true;
                ++base::s;
                return base::data[h].second;
            }
            if(base::data[h].first == k) {
                if(base::dflag[h] == true) base::data[h].second = Val();
                return base::data[h].second;
            }
            h = (h + 1) & (base::cap - 1);
        }
    }

    typename base::itr emplace(const Key &key, const Val &val) { return base::insert(Data(key, val)); }
};

/*
 * @brief ハッシュマップ(連想配列)
 * @docs docs/hashmap/hashmap.md
 **/

template <typename Key> struct HashSet : HashMapImpl::HashMapBase<Key, Key> {
    using HashMapImpl::HashMapBase<Key, Key>::HashMapBase;
};

/*
 * @brief ハッシュセット(集合)
 * @docs docs/hashmap/hashset.md
 **/

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s;
    cin >> s;
    string s2 = s + s + s;
    string s3;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < n; j++) {
            s3 += s[j];
            s3 += '$';
        }
    }
    vector<int> M = manacher(s3);
    rolling_hash RH(s2);
    HashSet<unsigned long long> st;
    vector<tuple<int, int, unsigned long long>> P;
    for(int i = n * 2 - 1; i < n * 4 - 1; i++) {
        int l = (i - M[i] + 2) / 2, r = (i + M[i] + 1) / 2;
        if(r - l > n) {
            int x = (r - l - (n - 1)) / 2;
            l += x;
            r -= x;
        }
        while(l < r) {
            long long H = RH.get(l, r);
            if(st.contain(H) == 0) {
                st.insert(H);
                P.push_back(make_tuple(l, r, H));
            } else {
                break;
            }
            l++;
            r--;
        }
    }
    int cnt = P.size();
    sort(P.begin(), P.end(),
         [&](tuple<int, int, unsigned long long> a, tuple<int, int, unsigned long long> b) { return get<1>(a) - get<0>(a) < get<1>(b) - get<0>(b); });

    HashMap<unsigned long long, int> P2;
    // vector<pair<unsigned long long, int>> P2(cnt);
    for(int i = 0; i < cnt; i++) {
        P2[get<2>(P[i])] = i;
        // P2[i] = make_pair(get<2>(P[i]), i);
    }
    // sort(P2.begin(), P2.end());
    vector<int> p(cnt, -1);
    for(int i = 0; i < cnt; i++) {
        if(get<1>(P[i]) - get<0>(P[i]) >= 3) {
            p[i] = P2[RH.get(get<0>(P[i]) + 1, get<1>(P[i]) - 1)];
            // p[i] = (*lower_bound(P2.begin(), P2.end(), make_pair(RH.get(get<0>(P[i]) + 1, get<1>(P[i]) - 1), -1))).second;
        }
    }
    vector<int> imos(cnt, 0);
    for(int i = n * 2 - 1; i < n * 4 - 1; i++) {
        int l = (i - M[i] + 2) / 2, r = (i + M[i] + 1) / 2;
        if(r - l > n) {
            int x = (r - l - (n - 1)) / 2;
            l += x;
            r -= x;
        }
        if(l < r) { imos[P2[RH.get(l, r)]]++; }
    }
    for(int i = cnt - 1; i >= 0; i--) {
        if(p[i] >= 0) { imos[p[i]] += imos[i]; }
    }
    long long ans = 0;
    for(int i = 0; i < cnt; i++) {
        int d = get<1>(P[i]) - get<0>(P[i]);
        if(d <= n) {
            ans += (long long)d * imos[i] % MOD2 * imos[i];
            ans %= MOD2;
        }
    }
    cout << ans << endl;
}