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

const int maxN = 4e4 + 10, mod = 998244353, g = 3, gi = 332748118;

int n, m;
int lim, cnt, r[maxN + 1];
int f[205][8005];
int A[maxN + 1], B[maxN + 1];
int fac[maxN + 1], inv[maxN + 1];

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 mpow(int a, int x)
{
	int ans = 1;
	while(x)
	{
		if(x & 1) ans = 1ll * ans * a % mod;
		a = 1ll * a * a % mod;
		x >>= 1;
	}
	return ans;
}

inline void NTT(int *a, int type)
{
	for(int i = 0; i < lim; i++)
		if(i < r[i]) swap(a[i], a[ r[i] ]);
	for(int mid = 1; mid < lim; mid <<= 1)
	{
		int wn = mpow(type == 1 ? g : gi, (mod - 1) / (mid << 1));
		for(int i = 0; i < lim; i += (mid << 1))
		{
			int w = 1;
			for(int j = 0; j < mid; j++, w = 1ll * w * wn % mod)
			{
				int x = a[i + j], y = 1ll * a[i + mid + j] * w % mod;
				a[i + j] = ADD(x, y); a[i + mid + j] = SUB(x, y);
			}
		}
	}
	if(type == -1)
	{
		int inv = mpow(lim, mod - 2);
		for(int i = 0; i < lim; i++) a[i] = 1ll * a[i] * inv % mod;
	}
}

inline int C(int n, int m)
{
	if(n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
	scanf("%d %d", &n, &m);

	fac[0] = 1;
	for(int i = 1; i <= n + 5; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n + 5] = mpow(fac[n + 5], mod - 2);
	for(int i = n + 4; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

	lim = 1, cnt = 0;
	while(lim <= n * 2) lim <<= 1, cnt ++;
	for(int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << cnt - 1);

	for(int i = 0; i <= n; i++) B[i] = inv[i + 3];
	NTT(B, 1);

	f[0][0] = 1;
	for(int i = 1; i <= m; i++)
	{
		for(int j = 0; j <= n; j++) A[j] = 1ll * f[i - 1][j] * inv[j] % mod;
		
		NTT(A, 1);
		for(int j = 0; j < lim; j++) A[j] = 1ll * A[j] * B[j] % mod;
		NTT(A, -1);

		f[i][0] = f[i - 1][0];
		for(int j = 1; j <= n; j++) 
			f[i][j] = ADD(1ll * fac[j + 2] * A[j - 1] % mod, 1ll * ADD(C(j + 1, 2), 1) * f[i - 1][j] % mod);

		for(int j = 0; j < lim; j++) A[j] = 0;
	}

	int ans = 0;
	for(int i = 0; i <= n; i++) ans = ADD(ans, 1ll * f[m][i] * C(n, i) % mod);

	printf("%d", ans);
	return 0;
}

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

const int maxN = 4e4 + 10, mod = 998244353, g = 3, gi = 332748118;

int n, m;
int lim, cnt, r[maxN + 1];
int f[205][8005];
int A[maxN + 1], B[maxN + 1];
int fac[maxN + 1], inv[maxN + 1];

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 mpow(int a, int x)
{
	int ans = 1;
	while(x)
	{
		if(x & 1) ans = 1ll * ans * a % mod;
		a = 1ll * a * a % mod;
		x >>= 1;
	}
	return ans;
}

inline void NTT(int *a, int type)
{
	for(int i = 0; i < lim; i++)
		if(i < r[i]) swap(a[i], a[ r[i] ]);
	for(int mid = 1; mid < lim; mid <<= 1)
	{
		int wn = mpow(type == 1 ? g : gi, (mod - 1) / (mid << 1));
		for(int i = 0; i < lim; i += (mid << 1))
		{
			int w = 1;
			for(int j = 0; j < mid; j++, w = 1ll * w * wn % mod)
			{
				int x = a[i + j], y = 1ll * a[i + mid + j] * w % mod;
				a[i + j] = ADD(x, y); a[i + mid + j] = SUB(x, y);
			}
		}
	}
	if(type == -1)
	{
		int inv = mpow(lim, mod - 2);
		for(int i = 0; i < lim; i++) a[i] = 1ll * a[i] * inv % mod;
	}
}

inline int C(int n, int m)
{
	if(n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main()
{
	scanf("%d %d", &n, &m);

	fac[0] = 1;
	for(int i = 1; i <= n + 5; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n + 5] = mpow(fac[n + 5], mod - 2);
	for(int i = n + 4; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

	lim = 1, cnt = 0;
	while(lim <= n * 2) lim <<= 1, cnt ++;
	for(int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << cnt - 1);

	for(int i = 0; i <= n; i++) B[i] = inv[i + 3];
	NTT(B, 1);

	f[0][0] = 1;
	for(int i = 1; i <= m; i++)
	{
		for(int j = 0; j <= n; j++) A[j] = 1ll * f[i - 1][j] * inv[j] % mod;
		
		NTT(A, 1);
		for(int j = 0; j < lim; j++) A[j] = 1ll * A[j] * B[j] % mod;
		NTT(A, -1);

		f[i][0] = f[i - 1][0];
		for(int j = 1; j <= n; j++) 
			f[i][j] = ADD(1ll * fac[j + 2] * A[j - 1] % mod, 1ll * ADD(C(j + 1, 2), 1) * f[i - 1][j] % mod);

		for(int j = 0; j < lim; j++) A[j] = 0;
	}

	int ans = 0;
	for(int i = 0; i <= n; i++) ans = ADD(ans, 1ll * f[m][i] * C(n, i) % mod);

	printf("%d", ans);
	return 0;
}

```