#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
int n,m,ans,f[N][2],g[N][2];
inline int add(int a,int b){
	a+=b;
	return a<mod?a:a-mod;
}
inline int dec(int a,int b){
	a-=b;
	return a<0?a+mod:a;
}
inline int mul(int a,int b){
	return 1LL*a*b%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(f));
		f[0][0]=1;
		g[0][0]=0;
		for(int j=1;j<=n;j++){
			f[j][0]=add(mul(f[j-1][0],m-1),mul(f[j-1][1],i-1));
			g[j][0]=add(mul(g[j-1][0],m-1),mul(g[j-1][1],i-1));
			f[j][1]=add(f[j-1][0],mul(f[j-1][1],m-i+1));
			if(j==n){
				j++;
				j--;
			}
			g[j][1]=add(g[j-1][0],f[j-1][0]);
			g[j][1]=add(g[j][1],mul(g[j-1][1],m-i+1));
		}
		ans=add(ans,add(g[n][0],g[n][1]));
	}
	printf("%d\n",ans);
	return 0;
}
#include "bits/stdc++.h"
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll

template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

const int N=1e10;



void solve(){
	int n;
	string t;
	cin >> n >> t;
	if(t == "0"){
		cout << N;
		return;
	}
	if(t == "1"){
		cout << 2 * N;
		return;
	}
	string s = "110";
	rep(i,0,3){
		bool ok = 1;
		rep(j,0,n){
			if(t[j] != s[(j + i) % 3]) ok = 0;
		}
		if(ok){
			// int r = (n + 2) / 3;
			int r = (i + n + 2) / 3;
			int ans = N - r + 1;
			// if(k > r) ans --;
			cout << ans;
			return;
		}
	}
	cout << 0;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#ifdef SIEVE
		sieve();
	#endif
	#ifdef NCR
		init();
	#endif
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}
