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 <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define mod 998244353
#define maxN 8027
#define maxM 222

ll poww(ll a, ll b) {
    ll ans = 1;
    while (b > 0) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}


const ll lim = 8005;
const ll sz = 14;
const ll dim = 1 << sz;
const ll inv_dim = poww(dim, mod - 2);
ll unity_root = 2;

int n, m, i;
ll fact[maxN], inv_fact[maxN];
ll dp[2][maxN], ss, dd;

ll a[1 << sz], b[1 << sz];
ll aux[1 << sz];


ll comb(ll n, ll k) {
    if (n < k) return 0;
    ll ans = (fact[n] * inv_fact[n - k]) % mod;
    return (ans * inv_fact[k]) % mod;
}

void add(ll &a, ll b) {
    if (b >= mod) b %= mod;
    a += b;
    if (a >= mod) a -= mod;
}

void rev(ll *work, int l, int r) {
    int i, p = l;

    if (l == r) return;

    for (i = l; i <= r; i++) aux[i] = work[i];
    for (i = l; i <= r; i += 2) work[p++] = aux[i];
    for (i = l + 1; i <= r; i += 2) work[p++] = aux[i];
    rev(work, l, (l + r) >> 1);
    rev(work, ((l + r) >> 1) + 1, r);
}

void fft(ll* work, double sgn) {
    int len, i, j, k;
    ll u, v, r, w;

    rev(work, 0, dim - 1);
    for (len = 1; 2 * len <= dim; len <<= 1) {
        r = poww(unity_root, (mod - 1) / (2 * len));
        if (sgn == -1) r = poww(r, mod - 2);

        for (i = 0; i < dim; i += 2 * len) {
            w = 1;

            for (j = 0; j < len; j++) {
                u = work[i + j];
                v = work[i + j + len];

                work[i + j] = (u + w * v) % mod;
                work[i + j + len] = (mod + u - ((w * v) % mod)) % mod;

                w *= r;
                w %= mod;
            }
        }
    }

    if (sgn < 0.00) {
        for (i = 0; i < dim; i++)
            work[i] = (work[i] * inv_dim) % mod;
    }
}

void convolute() {
    int i;

    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));

    for (i = 0; i <= n; i++) {
        a[i] = (dp[ss][i] * inv_fact[i]) % mod;
        b[i] = inv_fact[i + 2];
    }
    b[0] = 0;

    fft(a, +1);
    fft(b, +1);
    for (i = 0; i < dim; i++) a[i] = (a[i] * b[i]) % mod;
    fft(a, -1);

    //for (i = 0; i <= 10; i++) cerr << (fact[i + 2] * a[i]) % mod << ' ';
    //cerr << '\n';

    for (i = 0; i <= n; i++) {
        add(dp[dd][i], fact[i + 2] * a[i]);
    }
}

void solve() {
    int col, i, j;

    ss = 0; dd = 1;

    dp[ss][0] = 1;
    for (col = 1; col <= m; col++) {
        memset(dp[dd], 0, sizeof(dp[dd]));

        for (i = 0; i <= n; i++) {
            if (dp[ss][i] == 0) continue;

            //! add absolutely nothing
            add(dp[dd][i], dp[ss][i]);

            //! add 0 new lines
            add(dp[dd][i], dp[ss][i] * comb(i + 1, 2));

            //! add more new lines
            //for (j = 1; i + j <= n; j++)
            //    add(dp[dd][i + j], dp[ss][i] * comb(i + j + 2, j + 2));
        }

        convolute();

        swap(ss, dd);
    }

    ll ans = 0;
    for (i = 0; i <= n; i++)
        add(ans, dp[ss][i] * comb(n, i));

    cout << ans;
}

bool check(ll x) {
    if (poww(x, (mod - 1) / 2) == 1) return false;
    if (poww(x, (mod - 1) / 7) == 1) return false;
    if (poww(x, (mod - 1) / 17) == 1) return false;
    return true;
}

int main()
{
    //freopen("test.in","r",stdin);

    fact[0] = 1;
    for (i = 1; i <= lim; i++) fact[i] = (fact[i - 1] * i) % mod;
    inv_fact[lim] = poww(fact[lim], mod - 2);
    for (i = lim - 1; i >= 0; i--) inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % mod;

    while (!check(unity_root)) unity_root++;

    cin >> n >> m;
    solve();


    return 0;
}