#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1<<14|1,P=998244353;
int n,m,lim,fac[N],ifac[N],w[N],rev[N],f[N],g[N],t[N];
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
void dec(int&a,int b){a-=b,a+=a>>31&P;}
void mul(int&a,int b){a=1ll*a*b%P;}
int pow(int a,int b){int r=1;for(;b;b>>=1,mul(a,a))if(b&1)mul(r,a);return r;}
void init(int n)
{
    int half=(lim=1<<(33-__builtin_clz(n)))/2,g=pow(3,(P-1)/lim);
    w[half]=fac[0]=ifac[0]=1;
    for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|(i&1? half:0),mul(fac[i]=fac[i-1],i),ifac[i]=pow(fac[i],P-2);
    for(int i=half+1;i<lim;++i) mul(w[i]=w[i-1],g);
    for(int i=half-1;i;--i) w[i]=w[i<<1];
}
void NTT(int*a,int f)
{
    if(!~f) std::reverse(a+1,a+lim);
    for(int i=1;i<lim;++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int i=1;i<lim;i<<=1) for(int j=0,d=i<<1;j<lim;j+=d) for(int k=0,x;k<i;++k) x=1ll*a[i+j+k]*w[i+k]%P,dec(a[i+j+k]=a[j+k],x),inc(a[j+k],x);
    if(!~f) for(int i=0,x=P-(P-1)/lim;i<lim;++i) mul(a[i],x);
}
int main()
{
    int n=read(),m=read(),ans=0;
    init(n),memcpy(g+1,ifac+3,4*n),NTT(g,1),f[0]=t[0]=1;
    for(int i=1;i<=m;++i)
    {
	NTT(f,1);
	for(int j=0;j<lim;++j) mul(f[j],g[j]);
	NTT(f,-1);
        for(int j=0;j<=n;++j) t[j]=(1ll*f[j]*fac[j+2]+t[j]*(j*(j+1)/2+1ll))%P,mul(f[j]=t[j],ifac[j]);
	memset(f+n+1,0,4*(lim-n-1));
    }
    for(int i=0;i<=n;++i) inc(ans,1ll*ifac[i]*ifac[n-i]%P*t[i]%P);
    mul(ans,fac[n]),printf("%d",ans);
}

### Prompt

Please create a solution in Cpp 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<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1<<14|1,P=998244353;
int n,m,lim,fac[N],ifac[N],w[N],rev[N],f[N],g[N],t[N];
int read(){int x=0,c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
void dec(int&a,int b){a-=b,a+=a>>31&P;}
void mul(int&a,int b){a=1ll*a*b%P;}
int pow(int a,int b){int r=1;for(;b;b>>=1,mul(a,a))if(b&1)mul(r,a);return r;}
void init(int n)
{
    int half=(lim=1<<(33-__builtin_clz(n)))/2,g=pow(3,(P-1)/lim);
    w[half]=fac[0]=ifac[0]=1;
    for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|(i&1? half:0),mul(fac[i]=fac[i-1],i),ifac[i]=pow(fac[i],P-2);
    for(int i=half+1;i<lim;++i) mul(w[i]=w[i-1],g);
    for(int i=half-1;i;--i) w[i]=w[i<<1];
}
void NTT(int*a,int f)
{
    if(!~f) std::reverse(a+1,a+lim);
    for(int i=1;i<lim;++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int i=1;i<lim;i<<=1) for(int j=0,d=i<<1;j<lim;j+=d) for(int k=0,x;k<i;++k) x=1ll*a[i+j+k]*w[i+k]%P,dec(a[i+j+k]=a[j+k],x),inc(a[j+k],x);
    if(!~f) for(int i=0,x=P-(P-1)/lim;i<lim;++i) mul(a[i],x);
}
int main()
{
    int n=read(),m=read(),ans=0;
    init(n),memcpy(g+1,ifac+3,4*n),NTT(g,1),f[0]=t[0]=1;
    for(int i=1;i<=m;++i)
    {
	NTT(f,1);
	for(int j=0;j<lim;++j) mul(f[j],g[j]);
	NTT(f,-1);
        for(int j=0;j<=n;++j) t[j]=(1ll*f[j]*fac[j+2]+t[j]*(j*(j+1)/2+1ll))%P,mul(f[j]=t[j],ifac[j]);
	memset(f+n+1,0,4*(lim-n-1));
    }
    for(int i=0;i<=n;++i) inc(ans,1ll*ifac[i]*ifac[n-i]%P*t[i]%P);
    mul(ans,fac[n]),printf("%d",ans);
}

```