#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
#define ar array
string s;
const int MOD = 1e9+7;
int fhash[9000001];
int bhash[9000001];
int inv[9000001];
seed_seq seq{
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
int p;
int exp(int n, int pe){
    int out{1};
    while(pe){
        if(pe&1){
            out *= n;
            out %= MOD;
        }
        pe >>= 1;
        n *= n;
        n %= MOD;
    }
    return out;
}

void init(){
    int run{};
    int pow = 1;
    inv[0] = 1;
    inv[1] = exp(p, MOD-2);
    for(int i{2}; i < s.size(); ++i){
        inv[i] = (inv[i-1]*inv[1])%MOD;
    }
    for(int i{}; i < s.size(); ++i){
        run += (pow*(s[i]-'0'+1))%MOD;
        run %= MOD;
        fhash[i] = run;
        pow *= p;
        pow %= MOD;
    }

    run = 0;
    pow = 1;
    for(int i = s.size()-1; i >= 0; --i){
        run += (pow*(s[i]-'0'+1))%MOD;
        run %= MOD;
        bhash[i] = run;
        pow *= p;
        pow %= MOD;
    }
}
int ms;
bool eq(int i, int j){
    int fh = fhash[j] - (i == 0 ? 0 : fhash[i-1]);
    fh %= MOD;
    if(fh < 0)
        fh += MOD;
    fh *= inv[i];
    fh %= MOD;
    int bh = bhash[i] - (j == ms-1 ? 0 : bhash[j+1]);
    bh %= MOD;
    if(bh < 0)
        bh += MOD;
    bh *= inv[ms-1-j];
    bh %= MOD;
    return fh == bh;
}

int gethash(int i, int j){
    int fh = fhash[j] - (i == 0 ? 0 : fhash[i-1]);
    fh %= MOD;
    if(fh < 0)
        fh += MOD;
    fh *= inv[i];
    fh %= MOD;
    return fh;
}
template <class K, class V>
using ht = gp_hash_table<
    K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>, linear_probe_fn<>,
    hash_standard_resize_policy<hash_exponential_size_policy<>,
                                hash_load_check_resize_trigger<>, true>>;
int pcounts[9000001];
int things[9000001];
int isp[9000001];
vector<int> plengths[3000001];
void solve(){
    p = uniform_int_distribution<int>(11, MOD-2)(rng);
    int n;
    cin >> n;
    cin >> s;

    string t = s;
    s += t;
    s += t;
    ms = s.size();
    init();
    ht<int, int> rep({}, {}, {}, {}, {1 << 22});
    int ind{};
    for(int i = n; i < 2*n; ++i){
        int l = 1, r = (n-1)/2;
        int longest = 0;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(eq(i-mid, i+mid)){
                longest = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        int hh = gethash(i-longest, i+longest);
        int le = 1+2*longest;
        int place;
        if(rep.find(hh) == rep.end()){
            place = ind;
            rep[hh] = ind++;
            plengths[le].push_back(place);
        }else
            place = rep[hh];
        pcounts[place]++;
        isp[place] = i;

        l = 1, r = n/2;
        longest = 0;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(eq(i-mid+1, i+mid)){
                longest = mid;
                l = mid+1;
            }else
                r = mid-1;
        }
        if(longest != 0){
            hh = gethash(i-longest+1, i+longest);
            le = 2*longest;
            if(rep.find(hh) == rep.end()){
                place = ind;
                rep[hh] = ind++;
                plengths[le].push_back(place);
            }else
                place = rep[hh];
            pcounts[place]++;
            isp[place] = i;
        }
    }

    int out{};
    int mm = 998244353;
    for(int i = n; i >= 1; --i){
        for(int j : plengths[i]){
            out += ((pcounts[j]*pcounts[j])%mm * i)%mm;
            out %= mm;
            if(i > 2){
                int hh;
                if(i%2 == 0){
                    hh = gethash(isp[j]-(i-2)/2+1, isp[j]+(i-2)/2);
                }else{
                    hh = gethash(isp[j]-(i-2)/2, isp[j]+(i-2)/2);
                }
                int place;
                if(rep.find(hh) == rep.end()){
                    place = ind;
                    rep[hh] = ind++;
                    plengths[i-2].push_back(place);
                }else
                    place = rep[hh];
                pcounts[place] += pcounts[j];
                isp[place] = isp[j];
            }
        }
    }
    cout << out << '\n';
}

uci main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
}