#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 3e6 + 10;
const int mod = 998244353;

vector<pair<int, int>> a[2] {};
namespace pam {
int sz, tot, last;
int cnt[maxn], ch[maxn][10], 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;
  }
  last = ch[now][c - '0'];
  cnt[last]++;
}

void solve(int op) {
  for (int i = sz; i >= 0; i--) {
    cnt[fail[i]] += cnt[i];
  }
  for (int i = 2; i <= sz; i++) {  // 更新答案
    a[op].push_back({len[i], cnt[i]});
  }
}
}  // namespace pam

char s[maxn];

int ans = 0;

signed main() {
	int n;
	cin >> n;
  pam::clear();
  scanf("%s", s + 1);
  for (int i = 1; s[i]; i++) {
    pam::insert(s[i]);
  }
  pam::solve(0);
  pam::clear();
  for (int i = 1; s[i]; i++) {
  	pam::insert(s[i]);
  }
  for (int i = 1; s[i]; i++) {
  	pam::insert(s[i]);
  }  
  pam::solve(1);

  for (int i = 0; i < a[1].size(); i++) {
  	if (i < a[0].size()) {
  		// cout << a[0][i].first << " " << a[0][i].second << "\n";
  		// cout << a[1][i].first << " " << a[1][i].second << "\n";
  		// cout << "\n";
  		ans = (ans + a[0][i].first * (a[1][i].second - a[0][i].second) % mod * (a[1][i].second - a[0][i].second) % mod) % mod;
  	} else {
  		// cout << a[1][i].first << " " << a[1][i].second << "\n";
  		if (a[1][i].first <= n) {
  			ans = (ans + a[1][i].first * a[1][i].second % mod * a[1][i].second % mod) % mod;
  		}
  	}
  }

  cout << ans << "\n";

  return 0;
}