#include<bits/stdc++.h>
using namespace std;
int n, ch[3000010][11], fail[3000010], cnt[3000010], len[3000010], pos = 0, las;
char s[3000010];
long long mod = 998244353;
void init()
{
	pos = 1;
	len[0] = 0;
	fail[0] = 1;
	len[1] = -1;
	fail[1] = 1;
	las = 0;
}
int find(int x, int now)
{
	while(s[now - len[x] - 1] != s[now])x = fail[x];
	return x;
}
void insert(int x)
{
	int p = find(las, x);
	if(! ch[p][s[x] - '0'])
	{
		len[++ pos] = len[p] + 2;
		fail[pos] = ch[find(fail[p], x)][s[x] - '0'];
		ch[p][s[x] - '0'] = pos;
	}
	++ cnt[las = ch[p][s[x] - '0']];
}

int tmp[3000010];
signed main() {
	cin>>n;
	s[0] = '*';
	for(int i = 1;i <= n;i ++)
	{
		cin>>s[i];
		s[n + i] = s[i];
	}
	init();
	for(int i = 1;i <= n;i ++)
	{
		insert(i);
		//cout<<i<<endl;
	}
	for(int i = 1;i <= pos;i ++)tmp[i] = cnt[i];
	memset(ch, 0, sizeof(ch));
	memset(fail, 0, sizeof(fail));
	memset(cnt, 0, sizeof(cnt));
	memset(len, 0, sizeof(len));
	pos = 0;
	long long ans = 0;
	init();
	for(int i = 1;i <= 2 * n;i ++)
	{
		insert(i);
		//cout<<i<<endl;
	}
	for(int i = pos;i > 0;i --)
	{
		cnt[fail[i]] = (cnt[fail[i]]+ cnt[i]) % mod;
		tmp[fail[i]] = (tmp[fail[i]] + tmp[i]) % mod;
		if(len[i] <= n)ans = (ans + (cnt[i] - tmp[i] + mod) % mod * (cnt[i] - tmp[i] + mod) % mod * len[i] % mod) % mod;
	}
	cout<<ans;
	return 0;
}