#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 998244353;

struct PAM {
    static constexpr int N = 10;
    struct Node {
        int len;
        int link;
        array <int, N> nxt;
        Node () : len {}, link {}, nxt {} {};
    };
    vector <Node> t;
    int suff;
    string s;
    PAM () {
        init ();
    }
    void init () {
        t.assign (2, Node ());
        t[0].len = -1;
        suff = 1;
        s.clear ();
    }
    int newNode () {
        t.emplace_back ();
        return t.size () - 1;
    }
    bool add (char c) {
        int pos = s.size ();
        s += c;
        int let = c - '0';
        int cur = suff, curlen = 0;
        while (true) {
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                break;
            }
            cur = t[cur].link;
        }
        if (t[cur].nxt[let]) {
            suff = t[cur].nxt[let];
            return false;
        }
        int num = newNode ();
        suff = num;
        t[num].len = t[cur].len + 2;
        t[cur].nxt[let] = num;
        if (t[num].len == 1) {
            t[num].link = 1;
            return true;
        } 
        while (true) {
            cur = t[cur].link;
            curlen = t[cur].len;
            if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
                t[num].link = t[cur].nxt[let];
                break;
            }
        }
        return true;
    }

    int nxt (int p, int x) {
        return t[p].nxt[x];
    }
    int link (int p) {
        return t[p].link;
    } 
    int len (int p) {
        return t[p].len;
    }
    int size () {
        return t.size ();
    }
};

using i64 = long long;

constexpr int N = 6E6 + 10;

// vector <vector <int>> e (N);

int f[N], f2[N];

// void dfs (int x) {
//     for (auto y : e[x]) {
//         dfs (y);
//         f[x] += f[y];
//     }
// };

// void dfs2 (int x)  {
//     for (auto y : e[x]) {
//         dfs2 (y);
//         f2[x] += f2[y];
//     }
// };

void solve () {
    int n;
    cin >> n;
    
	string s;
	// s = string (n, '1');
	// for (int i = 0; i < n / 3; i ++) {
	// 	s += "118";
	// }
	// for (int i = 0; i < n; i ++) {
	// 	s += "2";
	// }
    cin >> s;

    PAM pam;
    vector <int> v;
    for (auto c : s) {
        pam.add (c);
        v.push_back (pam.suff);
    }
    
    int N = pam.size ();

    // vector <int> f (N);
    for (auto x : v) {
        f[x] ++;
    }

    // for (int i = 2; i < N; i ++) {
    //     e[pam.link (i)].push_back (i);
    // }

	// for (int i = 1; i <= 10; i ++) {
	// 	cerr << f[i] << " ";
	// }
	for (int i = N - 1; i >= 2; i --) {
		f[pam.link (i)] += f[i];
	}
	// dfs (1);

    for (auto &x : f) {
        x = -x;
    }

    for (auto c : s) {
        pam.add (c);
        v.push_back (pam.suff);
    }
    
    int M = N;
    N = pam.size ();
	// cout << N << '\n';

    // vector <int> f2 (N);
    for (auto x : v) {
        f2[x] ++;
    }

    // e.resize (N);
    // for (int i = M; i < N; i ++) {
    //     e[pam.link (i)].push_back (i);
    // }

	for (int i = N - 1; i >= 2; i --) {
		f2[pam.link (i)] += f2[i];
	}
    // dfs2 (1);

    i64 ans = 0;
    for (int i = 2; i < N; i ++) {
        if (pam.len (i) > n) {
            continue;
        }
        if (i < M) {
            f2[i] += f[i];
        }
        ans = (ans + 1LL * f2[i] * f2[i] % mod * pam.len (i) % mod) % mod;
    }

    cout << ans << '\n';
}

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    int T = 1;
    // cin >> T;

    while (T --) {
        solve ();
    }
}