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<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

const int L=14,N=1<<L;
const int mod=998244353;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

inline int qpow(int x,int y) {
	int ans=1;
	while (y) {
		if (y&1) ans=1LL*ans*x%mod;
		x=1LL*x*x%mod;y>>=1;
	}
	return ans;
}

int W[N*2],*w0[L],*w1[L],R[N];
inline void DFT(int *a,int n,int f) {
	int i,o,k,t,*wn,*w,x,y;
	for (i=0;i<n;i++)
		if (R[i]>i) swap(a[i],a[R[i]]);
	for (i=1,t=0;i<n;i<<=1,t++)
		for (o=0,wn=f==1?w0[t]:w1[t];o<n;o+=i<<1)
			for (k=0,w=wn;k<i;k++,w++) {
				x=a[o+k],y=1LL*a[o+k+i]**w%mod;
				a[o+k]=(x+y)%mod;
				a[o+k+i]=(x-y+mod)%mod;
			}
}

int f[210][N],g[N],h[N];
int fac[N],inv[N];
int main()
{
	int n=gi(),m=gi(),i,j,len,t,*cur=W,LEN,G;
	for (i=fac[0]=1;i<=n+2;i++) fac[i]=1LL*fac[i-1]*i%mod;
	for (i=2,inv[0]=inv[1]=1;i<=n+2;i++) inv[i]=mod-1LL*(mod/i)*inv[mod%i]%mod;
	for (i=3;i<=n+2;i++) inv[i]=1LL*inv[i-1]*inv[i]%mod;
	
	for (len=1,t=0;len<=n*2;len<<=1,t++) {
		G=qpow(3,(mod-1)/(len<<1));w0[t]=cur;
		for (i=cur[0]=1;i<len;i++) cur[i]=1LL*cur[i-1]*G%mod;
		cur+=len;
		G=qpow(G,mod-2);w1[t]=cur;
		for (i=cur[0]=1;i<len;i++) cur[i]=1LL*cur[i-1]*G%mod;
		cur+=len;
	}
	for (i=0,t--;i<len;i++)
		R[i]=R[i>>1]>>1|(i&1)<<t;
	LEN=qpow(len,mod-2);

	f[0][0]=1;
	for (i=1;i<=n;i++) g[i]=inv[i+2];DFT(g,len,1);
	for (i=0;i<m;i++) {
		for (j=0;j<=n;j++) {
			f[i+1][j]=(1LL*(j+1)*j/2+1)%mod*f[i][j]%mod;
			f[i][j]=1LL*f[i][j]*inv[j]%mod;
		}
		DFT(f[i],len,1);
		for (j=0;j<len;j++)
			f[i][j]=1LL*f[i][j]*g[j]%mod;
		DFT(f[i],len,-1);
		for (j=0;j<=n;j++)
			f[i+1][j]=(f[i+1][j]+1LL*f[i][j]*LEN%mod*fac[j+2])%mod;
	}
	int ans=0;
	for (j=0;j<=n;j++)
		ans=(ans+1LL*fac[n]*inv[j]%mod*inv[n-j]%mod*f[m][j])%mod;
	cout<<ans<<endl;
	return 0;
}