#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];
int pows[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;
}
int ms;
void init(){
    int run{};
    int pow = 1;
    inv[0] = 1;
    inv[1] = exp(p, MOD-2);
    pows[0] = 1;
    pows[1] = p;
    for(int i{}; i < s.size(); ++i){
        if(i >= 2){
            inv[i] = (inv[i-1]*inv[1])%MOD;
            pows[i] = (pows[i-1]*p)%MOD;
        }
        run += (pows[i]*(s[i]-'0'+1))%MOD;
        run %= MOD;
        fhash[i] = run;
    }

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

int gethash(int i, int j){
    int fh = ((fhash[j] - (i == 0 ? 0 : fhash[i-1]))*inv[i])%MOD;
    fh %= MOD;
    if(fh < 0)
        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<ar<int, 3>> plengths[3000001];
struct node{
    node *ne[10];
    int ind;
    node(){
        for(int i{}; i < 10; ++i)
            ne[i] = nullptr;
        ind = -1;
    }
};

int add(int i, int pl, node *root){
    if(i == 0){
        if(root->ind != -1)
            return root->ind;
        root->ind = pl;
        return root->ind;
    }else{
        if(!root->ne[i%10]){
            root->ne[i%10] = new node();
        }
        return add(i/10, pl, root->ne[i%10]);
    }
}


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();
    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;
        plengths[le].push_back({hh, 1, 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;
            plengths[le].push_back({hh, 1, i});
        }
    }

    int out{};
    int mm = 998244353;
    for(int i = n; i >= 1; --i){
        sort(plengths[i].begin(), plengths[i].end());
        for(int j{}; j < plengths[i].size(); ){
            int k = j;
            int amt{};
            while(k < plengths[i].size() && plengths[i][k][0] == plengths[i][j][0]){
                amt += plengths[i][k][1];
                ++k;
            }
            out += ((amt)*(amt)%mm * i)%mm;
            out %= mm;

            if(i > 2){
                int rep = plengths[i][j][2];
                int hh;
                if(i%2 == 0){
                    hh = gethash(rep-(i-2)/2+1, rep+(i-2)/2);
                }else{
                    hh = gethash(rep-(i-2)/2, rep+(i-2)/2);
                }
                plengths[i-2].push_back({hh, amt, rep});
            }
            

            j = k;
        }
    }
    cout << out << '\n';
}

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