#include <stdio.h>
#include <algorithm>
#define il inline
#define int long long
#define N 8001
using namespace std;
const int gi=3,mod=998244353;

int n,m,inv,ans;
int base=1,l,rev[4*N];
int fac[N+2],iac[N+2];
int f[N][N/40+1],F[4*N],G[4*N];

il int ksm(int a,int b)
{
	int res=1;
	for ( ; b; b>>=1,a=a*a%mod) if (b&1) res=res*a%mod;
	return res;
}

il void NTT(int *Z,int opt)
{
	int i,j,k;
	for (i=1; i<base; i++) if (i<rev[i]) swap(Z[i],Z[rev[i]]);
	for (i=1; i<base; i<<=1)
	{
		int Wn=ksm(gi,(mod-1)/(i<<1));
		for (j=0; j<base; j+=(i<<1))
		{
			int W=1;
			for (k=0; k<i; W=W*Wn%mod,k++)
			{
				int X=Z[j+k],Y=W*Z[j+i+k]%mod;
				Z[j+k]=(X+Y)%mod,Z[j+i+k]=(X-Y+mod)%mod;
			}
		}
	}
	if (opt==1) return;
	reverse(Z+1,Z+base);
	for (i=0; i<base; i++) Z[i]=Z[i]*inv%mod;
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	int i,j;
	for (i=fac[0]=1; i<=n+2; i++) fac[i]=fac[i-1]*i%mod;
	for (i=n+2,iac[i]=ksm(fac[i],mod-2); i>=1; i--) iac[i-1]=iac[i]*i%mod;
	while (base<=n+n+2) base<<=1,l++;
	for (i=1,inv=ksm(base,mod-2); i<base; i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	
	for (i=1; i<=n; i++) G[i]=iac[i+2];
	f[0][0]=1,NTT(G,1);
  	for (j=1; j<=m; j++)
	{
    	for (i=0; i<=n; i++) F[i]=f[i][j-1]*iac[i];
    	for (i=n+1; i<base; i++) F[i]=0;
    	NTT(F,1);
    	for (i=0; i<base; i++) F[i]=F[i]*G[i]%mod;
    	NTT(F,-1);
    	for (i=0; i<=n; i++) f[i][j]=(F[i]*fac[i+2]%mod+f[i][j-1]*(1ll+i*(i+1)/2)%mod)%mod;
  	}
  	for (i=0; i<=n; i++) ans=(ans+f[i][m]*fac[n]%mod*iac[i]%mod*iac[n-i]%mod)%mod;
  	printf("%lld",ans);
	
	return 0;
}
### Prompt

Your task is to create a CPP solution 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 <stdio.h>
#include <algorithm>
#define il inline
#define int long long
#define N 8001
using namespace std;
const int gi=3,mod=998244353;

int n,m,inv,ans;
int base=1,l,rev[4*N];
int fac[N+2],iac[N+2];
int f[N][N/40+1],F[4*N],G[4*N];

il int ksm(int a,int b)
{
	int res=1;
	for ( ; b; b>>=1,a=a*a%mod) if (b&1) res=res*a%mod;
	return res;
}

il void NTT(int *Z,int opt)
{
	int i,j,k;
	for (i=1; i<base; i++) if (i<rev[i]) swap(Z[i],Z[rev[i]]);
	for (i=1; i<base; i<<=1)
	{
		int Wn=ksm(gi,(mod-1)/(i<<1));
		for (j=0; j<base; j+=(i<<1))
		{
			int W=1;
			for (k=0; k<i; W=W*Wn%mod,k++)
			{
				int X=Z[j+k],Y=W*Z[j+i+k]%mod;
				Z[j+k]=(X+Y)%mod,Z[j+i+k]=(X-Y+mod)%mod;
			}
		}
	}
	if (opt==1) return;
	reverse(Z+1,Z+base);
	for (i=0; i<base; i++) Z[i]=Z[i]*inv%mod;
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	int i,j;
	for (i=fac[0]=1; i<=n+2; i++) fac[i]=fac[i-1]*i%mod;
	for (i=n+2,iac[i]=ksm(fac[i],mod-2); i>=1; i--) iac[i-1]=iac[i]*i%mod;
	while (base<=n+n+2) base<<=1,l++;
	for (i=1,inv=ksm(base,mod-2); i<base; i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	
	for (i=1; i<=n; i++) G[i]=iac[i+2];
	f[0][0]=1,NTT(G,1);
  	for (j=1; j<=m; j++)
	{
    	for (i=0; i<=n; i++) F[i]=f[i][j-1]*iac[i];
    	for (i=n+1; i<base; i++) F[i]=0;
    	NTT(F,1);
    	for (i=0; i<base; i++) F[i]=F[i]*G[i]%mod;
    	NTT(F,-1);
    	for (i=0; i<=n; i++) f[i][j]=(F[i]*fac[i+2]%mod+f[i][j-1]*(1ll+i*(i+1)/2)%mod)%mod;
  	}
  	for (i=0; i<=n; i++) ans=(ans+f[i][m]*fac[n]%mod*iac[i]%mod*iac[n-i]%mod)%mod;
  	printf("%lld",ans);
	
	return 0;
}
```