#include<bits/stdc++.h>
using namespace std;

const int p=998244353,maxN=1<<15,g=3,ig=332748118;
int W[maxN],iW[maxN];
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
    int ans=1;
    while(k){
        if(k&1) ans=1LL*ans*a%p;
        a=1LL*a*a%p;
        k>>=1;
    }
    return ans;
}
 
int R[maxN];
void NTT(int d[],int n0,bool flg){
    int x=1,len=0;while(x<n0) x<<=1,len++;
    for(int i=0;i<x;i++){
        R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
        if(i<R[i]) swap(d[i],d[R[i]]);
    }
    for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1)
    for(int j=0;j<x;j+=(i<<1))
    for(int k=0,u=0;k<i;k++,u+=l){
        int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p;
        d[j|k]=(a0+a1)%p;d[j|i|k]=a0-a1+p;
    	if(d[j|i|k]>=p)d[j|i|k]-=p;
	}
    if(flg){
        int invx=qpow(x,p-2);
        for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p;
    }
}

int N,M;

int F[205][maxN];
int G[maxN],H[maxN];

int C(int n,int m){
	if(n<m) return 0;
	return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;
}

int main(){
	int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN);
    W[0]=iW[0]=1;
    for(int i=1;i<maxN;i++)
        W[i]=1LL*W[i-1]*w%p,
        iW[i]=1LL*iW[i-1]*iw%p;
    inv[1]=ifac[0]=ifac[1]=fac[0]=fac[1]=1;
    for(int i=2;i<maxN;i++)
    	inv[i]=1LL*(p-p/i)*inv[p%i]%p,
    	fac[i]=1LL*fac[i-1]*i%p,
    	ifac[i]=1LL*ifac[i-1]*inv[i]%p;
    
    scanf("%d%d",&N,&M);
    F[0][0]=1;
    int n0=1;while(n0<((N+3)<<1)) n0<<=1;
    for(int j=1;j<=M;j++){
    	for(int i=0;i<n0;i++) G[i]=0;
    	for(int i=0;i<=N;i++) G[i]=1LL*F[j-1][i]*ifac[i]%p;
    	for(int i=0;i<n0;i++) H[i]=0;
    	for(int i=1;i<=N;i++) H[i]=ifac[i+2];
    	NTT(G,n0,0);NTT(H,n0,0);
    	for(int i=0;i<n0;i++) G[i]=1LL*G[i]*H[i]%p;
    	NTT(G,n0,1);
    	for(int i=0;i<=N;i++) F[j][i]=(1LL*fac[i+2]*G[i]%p+1LL*(1+i+C(i,2))%p*F[j-1][i]%p)%p;
	}
	
	int ans=0;
	for(int i=0;i<=N;i++) ans=(ans+1LL*C(N,i)*F[M][i]%p)%p;
	printf("%d\n",ans);
}
### Prompt

Please formulate 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<bits/stdc++.h>
using namespace std;

const int p=998244353,maxN=1<<15,g=3,ig=332748118;
int W[maxN],iW[maxN];
int fac[maxN],ifac[maxN],inv[maxN];
int qpow(int a,int k){
    int ans=1;
    while(k){
        if(k&1) ans=1LL*ans*a%p;
        a=1LL*a*a%p;
        k>>=1;
    }
    return ans;
}
 
int R[maxN];
void NTT(int d[],int n0,bool flg){
    int x=1,len=0;while(x<n0) x<<=1,len++;
    for(int i=0;i<x;i++){
        R[i]=(R[i>>1]>>1)|((i&1)<<(len-1));
        if(i<R[i]) swap(d[i],d[R[i]]);
    }
    for(int i=1,l=maxN/(i<<1);i<x;i<<=1,l>>=1)
    for(int j=0;j<x;j+=(i<<1))
    for(int k=0,u=0;k<i;k++,u+=l){
        int a0=d[j|k],a1=1LL*(flg?iW[u]:W[u])*d[j|i|k]%p;
        d[j|k]=(a0+a1)%p;d[j|i|k]=a0-a1+p;
    	if(d[j|i|k]>=p)d[j|i|k]-=p;
	}
    if(flg){
        int invx=qpow(x,p-2);
        for(int i=0;i<x;i++) d[i]=1LL*d[i]*invx%p;
    }
}

int N,M;

int F[205][maxN];
int G[maxN],H[maxN];

int C(int n,int m){
	if(n<m) return 0;
	return 1LL*fac[n]*ifac[m]%p*ifac[n-m]%p;
}

int main(){
	int w=qpow(g,(p-1)/maxN),iw=qpow(ig,(p-1)/maxN);
    W[0]=iW[0]=1;
    for(int i=1;i<maxN;i++)
        W[i]=1LL*W[i-1]*w%p,
        iW[i]=1LL*iW[i-1]*iw%p;
    inv[1]=ifac[0]=ifac[1]=fac[0]=fac[1]=1;
    for(int i=2;i<maxN;i++)
    	inv[i]=1LL*(p-p/i)*inv[p%i]%p,
    	fac[i]=1LL*fac[i-1]*i%p,
    	ifac[i]=1LL*ifac[i-1]*inv[i]%p;
    
    scanf("%d%d",&N,&M);
    F[0][0]=1;
    int n0=1;while(n0<((N+3)<<1)) n0<<=1;
    for(int j=1;j<=M;j++){
    	for(int i=0;i<n0;i++) G[i]=0;
    	for(int i=0;i<=N;i++) G[i]=1LL*F[j-1][i]*ifac[i]%p;
    	for(int i=0;i<n0;i++) H[i]=0;
    	for(int i=1;i<=N;i++) H[i]=ifac[i+2];
    	NTT(G,n0,0);NTT(H,n0,0);
    	for(int i=0;i<n0;i++) G[i]=1LL*G[i]*H[i]%p;
    	NTT(G,n0,1);
    	for(int i=0;i<=N;i++) F[j][i]=(1LL*fac[i+2]*G[i]%p+1LL*(1+i+C(i,2))%p*F[j-1][i]%p)%p;
	}
	
	int ans=0;
	for(int i=0;i<=N;i++) ans=(ans+1LL*C(N,i)*F[M][i]%p)%p;
	printf("%d\n",ans);
}
```