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 <bits/stdc++.h>

#define debug(x) cerr<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}

int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}

const int N = 18400;
int fac[N+10],invfac[N+10];

int C(int n,int m){
	if(n<0 || m<0 || m>n)return 0;
	return mul(fac[n],mul(invfac[m],invfac[n-m]));
}

int n,m,dp[303][8080],coef[N],co2;

struct poly{
	int wroot = 3;
	int n,l,rev[N],mrt[N],invn,MXLNTT = 14,MXNTT = 1<<MXLNTT;
	int uptopow(int x){
		while(x!=(x&(-x)))x+=x&(-x);
		return x;
	}
	void ori(){
		int stepv = mpow(wroot,(mod-1)/MXNTT);
		mrt[0] = 1;	for(int i=1;i<=MXNTT;i++)mrt[i] = mul(mrt[i-1],stepv);
		rev[0] = 0;	for(int i=1;i<=MXNTT;i++)rev[i] = (rev[i>>1]>>1)|(i&1?(1<<(MXLNTT-1)):0);
	}
	void dft(int a[],int sz,int typ){
		static int cc1[N],us[N];
		int mn = MXLNTT-__builtin_ctz(sz);
		for(int i=0;i<sz;i++)cc1[i] = a[rev[i]>>mn];
		for(int l=2;l<=sz;l*=2){
			int m = l>>1,step = MXNTT/l;
			if(typ == 0) for(int i=0,j = 0;i<=m;i++,j+=step)us[i] = mrt[j];
			else for(int i=0,j=MXNTT;i<=m;i++,j-=step)us[i] = mrt[j];
			for(int i = 0;i!=sz;i+=l){
				for(int j=0;j<m;j++){
					int t = mul(cc1[i+j+m],us[j]);
					cc1[i+j+m] = sub(cc1[i+j],t);
					cc1[i+j] = add(cc1[i+j],t);
				}
			}
		}
		if(typ){
			int invn = mpow(sz,mod-2);
			for(int i=0;i<sz;i++)a[i] = mul(cc1[i],invn);
		}else{
			memcpy(a,cc1,sz*sizeof(int));
		}
	}
}NTT;

int main() {
	fac[0] = 1;
	for(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);
	invfac[N] = mpow(fac[N],mod-2);
	for(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);
	NTT.ori();
	read(n);read(m);
	for(int i=0;i<=n;i++) dp[1][i] = 1;
	for(int i=1;i<=n;i++) coef[i] = invfac[i+2];
	int sz = NTT.uptopow((n+1)*2);
	NTT.dft(coef,sz,0);
	int pdp[N];
	int inv2 = (mod+1)/2;
	for(int ech=2;ech<=m;ech++){
		memset(pdp,0,sizeof(pdp));
		for(int i=0;i<=n;i++)pdp[i] = mul(dp[ech-1][i],invfac[i]);
		NTT.dft(pdp,sz,0);
		for(int i=0;i<sz;i++)pdp[i]=mul(pdp[i],coef[i]);
		NTT.dft(pdp,sz,1);
		for(int i=0;i<=n;i++){
			dp[ech][i] = add(mul(pdp[i],fac[i+2]),mul(dp[ech-1][i],i*(i+1)/2+1));
		}
	}
	int ans = 0;
	for(int i=0;i<=n;i++)ans = add(ans,mul(C(n,i),dp[m][i]));
	cout<<ans<<endl;
	return 0;
}