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

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=8000 +117;
const int MM=200 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
LL fact[NN]={};
LL rev[NN]={};
const int mod=998244353;
LL comp(int n,int m){
	if(m>n)return 0;
	return fact[n]*rev[m]%mod*rev[n-m]%mod;
}
LL ksm(LL a,LL b){
	LL ret=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ret=ret*a%mod;
	return ret;
}
void prefact(int n){
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=fact[i-1]*i%mod;
	rev[n]=ksm(fact[n],mod-2);
	for(int i=n;i>=1;--i)rev[i-1]=rev[i]*i%mod;
}
LL dp[2][NN]={};
LL a[4*NN]={};
LL b[4*NN]={};
int len=0;
int revb[4*NN]={};
int gt=3;
int revgt;
void dft(LL a[],int len,int sym){
	for(int i=1;i<len;++i)if(revb[i]<i)swap(a[revb[i]],a[i]);
	LL g=(sym==1?gt:revgt);
	for(int d=1;d<len;d<<=1){
		LL e=ksm(g,(mod-1)/d/2);
		for(int st=0,gap=d<<1;st<len;st+=gap){
			LL rt=1;
			for(int k=0;k<d;++k,rt=rt*e%mod){
				LL y=a[st+d+k]*rt;
				a[st+d+k]=(a[st+k]-y)%mod;
				a[st+k]=(a[st+k]+y)%mod;
			}
		}
	}
	if(sym==-1){
		LL bas=ksm(len,mod-2);
		for(int i=0;i<len;++i)
			a[i]=a[i]*bas%mod;
	}
}
int main(){
	//open();
	n=read();
	m=read();
	prefact(n+10);
	dp[0][0]=1;
	int now=0;
	len=1;
	while(len<=2*n)len<<=1;
	for(int i=1;i<len;++i){
		revb[i]=revb[i>>1]>>1;
		if(i&1)revb[i]|=len>>1;
	}
	for(int i=1;i<=n;++i){
		b[i]=rev[i+2];
	}
	revgt=ksm(gt,mod-2);
	dft(b,len,1);
	for(int ti=1;ti<=m;++ti){
		now^=1;
		for(int i=0;i<len;++i)a[i]=0;
		for(int i=0;i<=n;++i){
			a[i]=dp[now^1][i]*rev[i]%mod;
		}
		dft(a,len,1);
		for(int i=0;i<len;++i)a[i]=a[i]*b[i]%mod;
		dft(a,len,-1);
		for(int j=0;j<=n;++j){
			dp[now][j]=a[j]*fact[j+2]%mod;
		}
		for(int j=0;j<=n;++j){
			dp[now][j]+=dp[now^1][j]*(comp(j+1,2)+1);
			dp[now][j]%=mod;
		}
	}
	LL ans=0;
	for(int i=0;i<=n;++i){
		ans=(ans+dp[now][i]*comp(n,i))%mod;
	}
	ans=(ans+mod)%mod;
	printf("%lld\n",ans);
	close();
	return 0;
}