#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
const int N=2e4+5;
int n,m,k,len,r[N];
long long ans,Inv,f[N],g[N],h[N],fac[N],inv[N];
long long fsp(long long x,int y){
	long long ans=1;
	while(y){
		if(y&1)	ans=ans*x%P;
		y>>=1,x=x*x%P;
	}
	return ans;
}
void NTT(long long *d,int f){
	for(int i=1;i<n;i++)	if(i<r[i])	swap(d[i],d[r[i]]);
	for(int i=1;i<n;i<<=1){
		int wn=fsp(3,(P-1)/(i<<1));
		if(f)	wn=fsp(wn,P-2);
		for(int j=0;j<n;j+=i<<1){
			long long w=1;
			for(int k=0;k<i;k++,w=w*wn%P){
				int x=d[j+k],y=w*d[i+j+k]%P;
				d[j+k]=(x+y)%P,d[i+j+k]=(x-y+P)%P;
			}
		}
	}
	if(f)	for(int i=0;i<n;i++)	d[i]=d[i]*Inv%P;
}
long long C(int n,int m){
	return fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
	scanf("%d%d",&k,&m),fac[0]=inv[0]=1;
	for(int i=1;i<=k+2;i++){
		fac[i]=fac[i-1]*i%P;
		inv[i]=fsp(fac[i],P-2);
	}
	for(;(1<<len)<=k*2;++len);
	n=1<<len,Inv=fsp(n,P-2),g[0]=1;
	for(int i=1;i<=k;i++)	h[i]=inv[i+2];
	for(int i=1;i<n;i++)	r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
	NTT(h,0);

	while(m--){
		for(int i=0;i<=k;i++)	f[i]=(1LL*i*(i-1)/2+i+1)*g[i]%P;
		for(int i=0;i<=k;i++)	g[i]=g[i]*inv[i]%P;
		NTT(g,0);

		for(int i=0;i<n;i++)	g[i]=g[i]*h[i]%P;

		NTT(g,1);
		for(int i=k+1;i<n;i++)	f[i]=0;
		for(int i=0;i<=k;i++)	f[i]=(f[i]+g[i]*fac[i+2])%P;
		swap(f,g);
	}
	for(int i=0;i<=k;i++)	ans=(ans+g[i]*C(k,i))%P;
	printf("%lld\n",ans);
	return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

We have an N \times M grid. The square at the i-th row and j-th column will be denoted as (i,j). Particularly, the top-left square will be denoted as (1,1), and the bottom-right square will be denoted as (N,M). Takahashi painted some of the squares (possibly zero) black, and painted the other squares white.

We will define an integer sequence A of length N, and two integer sequences B and C of length M each, as follows:

* A_i(1\leq i\leq N) is the minimum j such that (i,j) is painted black, or M+1 if it does not exist.
* B_i(1\leq i\leq M) is the minimum k such that (k,i) is painted black, or N+1 if it does not exist.
* C_i(1\leq i\leq M) is the maximum k such that (k,i) is painted black, or 0 if it does not exist.



How many triples (A,B,C) can occur? Find the count modulo 998244353.

Constraints

* 1 \leq N \leq 8000
* 1 \leq M \leq 200
* N and M are integers.



Partial Score

* 1500 points will be awarded for passing the test set satisfying N\leq 300.

Constraints

* 1 \leq N \leq 8000
* 1 \leq M \leq 200
* N and M are integers.

Input

Input is given from Standard Input in the following format:


N M

Output

Print the number of triples (A,B,C), modulo 998244353.

Examples

Input

2 3


Output

64


Input

4 3


Output

2588


Input

17 13


Output

229876268


Input

5000 100


Output

57613837

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
const int N=2e4+5;
int n,m,k,len,r[N];
long long ans,Inv,f[N],g[N],h[N],fac[N],inv[N];
long long fsp(long long x,int y){
	long long ans=1;
	while(y){
		if(y&1)	ans=ans*x%P;
		y>>=1,x=x*x%P;
	}
	return ans;
}
void NTT(long long *d,int f){
	for(int i=1;i<n;i++)	if(i<r[i])	swap(d[i],d[r[i]]);
	for(int i=1;i<n;i<<=1){
		int wn=fsp(3,(P-1)/(i<<1));
		if(f)	wn=fsp(wn,P-2);
		for(int j=0;j<n;j+=i<<1){
			long long w=1;
			for(int k=0;k<i;k++,w=w*wn%P){
				int x=d[j+k],y=w*d[i+j+k]%P;
				d[j+k]=(x+y)%P,d[i+j+k]=(x-y+P)%P;
			}
		}
	}
	if(f)	for(int i=0;i<n;i++)	d[i]=d[i]*Inv%P;
}
long long C(int n,int m){
	return fac[n]*inv[m]%P*inv[n-m]%P;
}
int main(){
	scanf("%d%d",&k,&m),fac[0]=inv[0]=1;
	for(int i=1;i<=k+2;i++){
		fac[i]=fac[i-1]*i%P;
		inv[i]=fsp(fac[i],P-2);
	}
	for(;(1<<len)<=k*2;++len);
	n=1<<len,Inv=fsp(n,P-2),g[0]=1;
	for(int i=1;i<=k;i++)	h[i]=inv[i+2];
	for(int i=1;i<n;i++)	r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
	NTT(h,0);

	while(m--){
		for(int i=0;i<=k;i++)	f[i]=(1LL*i*(i-1)/2+i+1)*g[i]%P;
		for(int i=0;i<=k;i++)	g[i]=g[i]*inv[i]%P;
		NTT(g,0);

		for(int i=0;i<n;i++)	g[i]=g[i]*h[i]%P;

		NTT(g,1);
		for(int i=k+1;i<n;i++)	f[i]=0;
		for(int i=0;i<=k;i++)	f[i]=(f[i]+g[i]*fac[i+2])%P;
		swap(f,g);
	}
	for(int i=0;i<=k;i++)	ans=(ans+g[i]*C(k,i))%P;
	printf("%lld\n",ans);
	return 0;
}

```