#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
const int maxn = 3e6 + 5;
const long long MOD=998244353;
int tmp,pre,d[maxn];
namespace pam {
int sz, tot, last;
int cnt[maxn], ch[maxn][26], len[maxn], fail[maxn];
char s[maxn];

int node(int l) {  // 建立一个新节点，长度为 l
  sz++;
  memset(ch[sz], 0, sizeof(ch[sz]));
  len[sz] = l;
  fail[sz] = cnt[sz] = 0;
  return sz;
}

void clear() {  // 初始化
  sz = -1;
  last = 0;
  s[tot = 0] = '$';
  node(0);
  node(-1);
  fail[0] = 1;
}

int getfail(int x) {  // 找后缀回文
  while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
  return x;
}

void insert(char c) {  // 建树
  s[++tot] = c;
  int now = getfail(last);
  if (!ch[now][c - '0']) {
    int x = node(len[now] + 2);
    fail[x] = ch[getfail(fail[now])][c - '0'];
    ch[now][c - '0'] = x;
 //   cnt[x]=cnt[fail[x]]+1;
  }
  last = ch[now][c - '0'];
  cnt[last]++;
}
void solve1() {
  long long ans = 0;
  for (int i = sz; i >= 0; i--) {
    cnt[fail[i]] += cnt[i];
  }
  for (int i = 2; i <= sz; i++) { 
 // 	cout<<i<<" "<<cnt[i]<<"  "<<len[i]<<endl;// 更新答案
 	d[i]=cnt[i];
  }
}
long long solve2() {
  long long ans = 0;
  for (int i = sz; i >= 0; i--) {
    cnt[fail[i]] += cnt[i];
  }
  for (int i = 2; i <= sz; i++) { 
  	if(len[i]<=tmp)
	  	if(i>pre) // 更新答案
    		ans = (ans + (long long)cnt[i]*cnt[i]%MOD*len[i]%MOD)%MOD;
    	else
    		ans=(ans + (long long)(cnt[i]-d[i])*(cnt[i]-d[i])%MOD*len[i]%MOD)%MOD;
  }
  return ans;
}
}  // namespace pam

string s;

int main() {
  cin>>tmp;
  cin.tie(nullptr)->sync_with_stdio(false);
  pam::clear();
  long long ans1=0,ans2=0;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    pam::insert(s[i]);
  //  cout<<pam::last<<" "<<i<<" "<<pam::cnt[pam::last]<<endl;
  }
  pre=pam::sz;
  pam::solve1();
  s=s+s;
  pam::clear();
  for (int i = 0; i < s.size(); i++) {
  //	cout<<s[i]<<endl;
    pam::insert(s[i]);
  }
  ans2=pam::solve2();
  cout<<ans2<<endl;
  return 0;
}