QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725768#7873. Since A LightTheZone100 ✓149ms16064kbC++2069.5kb2024-11-08 19:54:272024-11-08 19:54:29

Judging History

你现在查看的是最新测评结果

  • [2024-11-08 19:54:29]
  • 评测
  • 测评结果：100
  • 用时：149ms
  • 内存：16064kb
查看
  • [2024-11-08 19:54:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}
/*#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,ggg=3,invggg=(mod+1)/ggg;
int n,d;
struct matr{
	int n,m;
	vector<vector<int> >v;
	void init(int nn,int mm){
		n=nn;m=mm;
		vector<int>q;
		for(int i=0;i<m;i++)
			q.push_back(0);
		for(int i=0;i<n;i++)
			v.push_back(q);
	}
};
matr mul(matr a,matr b){
	matr ret;ret.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int k=0;k<b.n;k++)
			for(int j=0;j<b.m;j++)
				ret.v[i][j]=(ret.v[i][j]+1ll*a.v[i][k]*b.v[k][j])%mod;
	return ret;
}
matr Mypow(matr a,int times){
	if(times==1)
		return a;
	matr ret=Mypow(a,times/2);
	ret=mul(ret,ret);
	if(times&1)
		ret=mul(ret,a);
	return ret;
}
const int maxn=262144;
int tmp[maxn],F[maxn],G[maxn];
long long mypow(long long x,int y){
	long long ret=1;
	while(y){
		if(y&1)ret=ret*x%mod;
		y>>=1;x=x*x%mod;
	}return ret;
}
int revs[maxn];
void initrev(int Len){
	for(int i=1;i<Len;++i){
		revs[i]=revs[i>>1]>>1;
		if(i&1)revs[i]|=(Len>>1);
	}
}
void DFT(int *f,int n,int rev){
	int g0=rev==1?ggg:invggg;
	initrev(n);
	for(register int i=0;i<n;++i)
		if(i<revs[i])
			f[i]^=f[revs[i]]^=f[i]^=f[revs[i]];
	for(register int h=2;h<=n;h<<=1){
		int gn=mypow(g0,(mod-1)/h);
		for(register int j=0;j<n;j+=h){
			int gk=1;
			for(register int k=j;k<j+(h>>1);++k){
				int e=f[k],o=1ll*gk*f[k+(h>>1)]%mod;
				f[k]=(e+o)%mod,f[k+(h>>1)]=(e+mod-o)%mod;
				gk=1ll*gk*gn%mod;
			}
		}
	}
	if(rev==-1){
		int invv=mypow(n,mod-2);
		for(register int i=0;i<n;++i)
			f[i]=1ll*f[i]*invv%mod; 
	}
}
long long dpn[2][100003];
vector<int>mat[2][2][2][2],dmat[2][2][2][2];
int f[2][200003],g[2][200003],h[2][200003],ff[262144],gg[262144],hh[262144];
void init(){
	long long nw=1,x=(n+1)/2,y=(n+1)/2;
	for(int i=0;i<=d;i++){
		f[0][i]=nw;
		if(i%2==0)
			g[0][i]=nw;
		else
			h[0][i]=nw;
		if(i<=n+1)
			if((n+1-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}nw=1;x=n/2;y=n/2;
	for(int i=0;i<=d;i++){
		f[1][i]=nw;
		if(i%2==0)
			g[1][i]=nw;
		else
			h[1][i]=nw;
		if(i<=n)
			if((n-i)%2==0)
				nw=nw*y%mod,
				y--,
				nw=nw*mypow(x-y,mod-2)%mod;
			else
				x++,
				nw=nw*x%mod,
				nw=nw*mypow(x-y,mod-2)%mod;
		else break;
	}
	for(int i=0;i<=d;i++)
		F[i]=f[0][i],
		G[i]=f[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		ff[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[0][i],
		G[i]=h[1][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		gg[i]=F[i];
	for(int i=0;i<maxn;i++)F[i]=0,G[i]=0;
	for(int i=0;i<=d;i++)
		F[i]=g[1][i],
		G[i]=h[0][i];
	DFT(F,maxn,1);
	DFT(G,maxn,1);
	for(int i=0;i<maxn;i++)
		F[i]=1ll*F[i]*G[i]%mod;
	DFT(F,maxn,-1);
	for(int i=0;i<maxn;i++)
		hh[i]=F[i];
}
int calc(int D,int qaq){
	if(qaq==1)
		return (ff[D]-hh[D]+mod)%mod;
	else
		return (ff[D]-gg[D]+mod)%mod;
}
int QAQ(int x,int y){
	if(x==0)
		return min(1,y);
	return y;
}
void calcsmall(){
	matr fr,time0,time1;
	fr.init(1,8);
	fr.v[0][4]=1;
	time0.init(8,8);
	time1.init(8,8);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time0.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][0][j%2][k][l]);
	for(int i=0;i<2;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<2;k++)
				for(int l=0;l<=min(1,j);l++)
					time1.v[k*4+j-l][i*4+j]=QAQ(j-l,mat[i][1][j%2][k][l]);
	time0.v[4][0]=1;
	time1.v[0][4]=1;
	if(n/2)
		fr=mul(fr,Mypow(mul(time0,time1),n/2));
	if(n%2)
		fr=mul(fr,time0);
	for(int i=0;i<8;i++)
		dpn[i/4][i%4]=fr.v[0][i];
}
int main(){
	cin>>n>>d;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					for(int times=0;times<3;times++)
						mat[k][i][j][l].push_back(0);
					for(int times=0;times<5;times++)
						dmat[k][i][j][l].push_back(0);
				}
			if(j){
				mat[0][i][j][0][0]=1;
				mat[0][i][j][1^i][1]=2;
				mat[1][i][j][1][0]=1;
				mat[1][i][j][1^i][1]=2;
			}else{
				mat[0][i][j][0][0]=1;
				mat[1][i][j][1][0]=1;
				mat[i][i][j][1^i][1]=1;
				mat[i][i][j][1^i][2]=1;
			}
		} 
	init();
	calcsmall();
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			if(j){
				mat[0][i][j][1^i][1]=0;
				mat[1][i][j][1^i][1]=0;
				mat[0][i][j][i][1]=2;
				mat[1][i][j][i][1]=2;
			}else{
				mat[i][i][j][i^1][1]=0;
				mat[i][i][j][i^1][2]=0;
				mat[i^1][i][j][i][1]=1;
				mat[i^1][i][j][i][2]=1;
			}
		}
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++)
					for(int o=0;o<3;o++)
						for(int ll=0;ll<2;ll++)
							for(int oo=0;oo<3;oo++)
								dmat[i][j][k][ll][o+oo]+=mat[i][j][k][l][o]*mat[l][j^1][(k-o+2)%2][ll][oo];
				dmat[i][j][k][i][0]--;
				for(int ll=0;ll<2;ll++)
					for(int oo=1;oo<3;oo++)
						dmat[i][j][k][ll][oo]-=mat[1^i][j^1][k][ll][oo];
			}
	for(int D=4;D<=d;D++)
		for(int k=0;k<2;k++){
			for(int i=0;i<2;i++)
				for(int j=1;j<5;j++)
					if(D-j||j!=4)
						dpn[k][D]+=dpn[i][D-j]*dmat[k^1][n%2][D%2][i][j];
			dpn[k][D]-=calc(D-1,k);
			dpn[k][D]=(dpn[k][D]%mod+mod)%mod;
		}
	int ans=(dpn[0][d]+dpn[1][d])%mod;
	if(d%2)ans=1ll*ans*(mod+1)/2%mod;
	cout<<ans; 
}*/
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 1
Accepted

Test #1:

score: 1
Accepted
time: 121ms
memory: 14320kb

input:

1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 1
Accepted
time: 128ms
memory: 14820kb

input:

2 1

output:

2

result:

ok single line: '2'

Test #3:

score: 1
Accepted
time: 133ms
memory: 14908kb

input:

3 2

output:

3

result:

ok single line: '3'

Test #4:

score: 1
Accepted
time: 129ms
memory: 14264kb

input:

4 4

output:

5

result:

ok single line: '5'

Test #5:

score: 1
Accepted
time: 120ms
memory: 12620kb

input:

5 7

output:

2

result:

ok single line: '2'

Test #6:

score: 1
Accepted
time: 133ms
memory: 15168kb

input:

6 4

output:

41

result:

ok single line: '41'

Test #7:

score: 1
Accepted
time: 118ms
memory: 14212kb

input:

7 11

output:

2

result:

ok single line: '2'

Test #8:

score: 1
Accepted
time: 121ms
memory: 14312kb

input:

8 8

output:

175

result:

ok single line: '175'

Test #9:

score: 1
Accepted
time: 133ms
memory: 14500kb

input:

9 10

output:

298

result:

ok single line: '298'

Test #10:

score: 1
Accepted
time: 125ms
memory: 14320kb

input:

10 3

output:

392

result:

ok single line: '392'

Test #11:

score: 1
Accepted
time: 132ms
memory: 14924kb

input:

11 8

output:

3785

result:

ok single line: '3785'

Test #12:

score: 1
Accepted
time: 133ms
memory: 14384kb

input:

12 15

output:

1422

result:

ok single line: '1422'

Test #13:

score: 1
Accepted
time: 120ms
memory: 13152kb

input:

13 17

output:

2008

result:

ok single line: '2008'

Test #14:

score: 1
Accepted
time: 128ms
memory: 15216kb

input:

14 16

output:

21508

result:

ok single line: '21508'

Test #15:

score: 1
Accepted
time: 125ms
memory: 14772kb

input:

15 1

output:

1596

result:

ok single line: '1596'

Test #16:

score: 1
Accepted
time: 120ms
memory: 12600kb

input:

16 28

output:

29

result:

ok single line: '29'

Test #17:

score: 1
Accepted
time: 120ms
memory: 12528kb

input:

17 6

output:

98086

result:

ok single line: '98086'

Test #18:

score: 1
Accepted
time: 124ms
memory: 12732kb

input:

18 11

output:

1478534

result:

ok single line: '1478534'

Test #19:

score: 1
Accepted
time: 133ms
memory: 14820kb

input:

19 25

output:

250068

result:

ok single line: '250068'

Test #20:

score: 1
Accepted
time: 122ms
memory: 14244kb

input:

20 27

output:

355418

result:

ok single line: '355418'

Test #21:

score: 1
Accepted
time: 129ms
memory: 14512kb

input:

21 23

output:

13517834

result:

ok single line: '13517834'

Test #22:

score: 1
Accepted
time: 127ms
memory: 14184kb

input:

22 4

output:

315460

result:

ok single line: '315460'

Test #23:

score: 1
Accepted
time: 125ms
memory: 14452kb

input:

23 37

output:

18428

result:

ok single line: '18428'

Test #24:

score: 1
Accepted
time: 129ms
memory: 14528kb

input:

24 18

output:

647287901

result:

ok single line: '647287901'

Test #25:

score: 1
Accepted
time: 124ms
memory: 13096kb

input:

25 40

output:

136655

result:

ok single line: '136655'

Subtask #2:

score: 7
Accepted

Test #26:

score: 7
Accepted
time: 133ms
memory: 14316kb

input:

380 59

output:

718355613

result:

ok single line: '718355613'

Test #27:

score: 7
Accepted
time: 129ms
memory: 14928kb

input:

164 46

output:

353450103

result:

ok single line: '353450103'

Test #28:

score: 7
Accepted
time: 128ms
memory: 14876kb

input:

206 144

output:

910367339

result:

ok single line: '910367339'

Test #29:

score: 7
Accepted
time: 126ms
memory: 14164kb

input:

270 127

output:

78796015

result:

ok single line: '78796015'

Test #30:

score: 7
Accepted
time: 133ms
memory: 14748kb

input:

157 87

output:

705420296

result:

ok single line: '705420296'

Subtask #3:

score: 10
Accepted

Test #31:

score: 10
Accepted
time: 129ms
memory: 15184kb

input:

413 652

output:

170600118

result:

ok single line: '170600118'

Test #32:

score: 10
Accepted
time: 121ms
memory: 12868kb

input:

724 979

output:

677376486

result:

ok single line: '677376486'

Test #33:

score: 10
Accepted
time: 133ms
memory: 14252kb

input:

1667 1699

output:

147640784

result:

ok single line: '147640784'

Test #34:

score: 10
Accepted
time: 132ms
memory: 14844kb

input:

1980 517

output:

276583672

result:

ok single line: '276583672'

Test #35:

score: 10
Accepted
time: 121ms
memory: 12656kb

input:

2000 2000

output:

265422351

result:

ok single line: '265422351'

Subtask #4:

score: 14
Accepted

Test #36:

score: 14
Accepted
time: 130ms
memory: 14488kb

input:

4495 4498

output:

375585699

result:

ok single line: '375585699'

Test #37:

score: 14
Accepted
time: 129ms
memory: 14672kb

input:

4968 2196

output:

844161053

result:

ok single line: '844161053'

Test #38:

score: 14
Accepted
time: 122ms
memory: 12576kb

input:

3967 3143

output:

496535114

result:

ok single line: '496535114'

Test #39:

score: 14
Accepted
time: 129ms
memory: 15012kb

input:

2406 4205

output:

599052202

result:

ok single line: '599052202'

Test #40:

score: 14
Accepted
time: 118ms
memory: 14196kb

input:

3942 3259

output:

110001226

result:

ok single line: '110001226'

Subtask #5:

score: 19
Accepted

Test #41:

score: 19
Accepted
time: 133ms
memory: 14568kb

input:

158314621 32

output:

465741961

result:

ok single line: '465741961'

Test #42:

score: 19
Accepted
time: 133ms
memory: 14476kb

input:

456573367 93

output:

310185347

result:

ok single line: '310185347'

Test #43:

score: 19
Accepted
time: 125ms
memory: 12536kb

input:

638787498 62

output:

467767457

result:

ok single line: '467767457'

Test #44:

score: 19
Accepted
time: 117ms
memory: 14424kb

input:

752253598 48

output:

110045639

result:

ok single line: '110045639'

Test #45:

score: 19
Accepted
time: 126ms
memory: 14064kb

input:

992442354 76

output:

330338775

result:

ok single line: '330338775'

Subtask #6:

score: 36
Accepted

Test #46:

score: 36
Accepted
time: 130ms
memory: 14080kb

input:

812922977 1762

output:

927995257

result:

ok single line: '927995257'

Test #47:

score: 36
Accepted
time: 133ms
memory: 14464kb

input:

661518393 1247

output:

469311509

result:

ok single line: '469311509'

Test #48:

score: 36
Accepted
time: 131ms
memory: 14828kb

input:

562238351 1811

output:

157645249

result:

ok single line: '157645249'

Test #49:

score: 36
Accepted
time: 125ms
memory: 14456kb

input:

985149295 62

output:

137919742

result:

ok single line: '137919742'

Test #50:

score: 36
Accepted
time: 130ms
memory: 14872kb

input:

983061012 3695

output:

893431185

result:

ok single line: '893431185'

Subtask #7:

score: 13
Accepted

Test #51:

score: 13
Accepted
time: 141ms
memory: 14864kb

input:

320076133 78121

output:

395290254

result:

ok single line: '395290254'

Test #52:

score: 13
Accepted
time: 137ms
memory: 15416kb

input:

446896560 77255

output:

351855538

result:

ok single line: '351855538'

Test #53:

score: 13
Accepted
time: 137ms
memory: 14168kb

input:

119010844 13459

output:

267420251

result:

ok single line: '267420251'

Test #54:

score: 13
Accepted
time: 149ms
memory: 16064kb

input:

974106901 92469

output:

455361665

result:

ok single line: '455361665'

Test #55:

score: 13
Accepted
time: 135ms
memory: 14504kb

input:

776878732 25173

output:

929444986

result:

ok single line: '929444986'
English 繁體中文 简体中文

伺服器時間: 2024-12-12 00:41:45 | 開源專案