Problem: Let's define the function f of multiset a as the multiset of number of occurences of every number, that is present in a.

E.g., f(\{5, 5, 1, 2, 5, 2, 3, 3, 9, 5\}) = \{1, 1, 2, 2, 4\}.

Let's define f^k(a), as applying f to array a k times: f^k(a) = f(f^{k-1}(a)), f^0(a) = a. 

E.g., f^2(\{5, 5, 1, 2, 5, 2, 3, 3, 9, 5\}) = \{1, 2, 2\}.

You are given integers n, k and you are asked how many different values the function f^k(a) can have, where a is arbitrary non-empty array with numbers of size no more than n. Print the answer modulo 998 244 353.

Input

The first and only line of input consists of two integers n, k (1 ≤ n, k ≤ 2020).

Output

Print one number — the number of different values of function f^k(a) on all possible non-empty arrays with no more than n elements modulo 998 244 353.

Examples

Input


3 1


Output


6


Input


5 6


Output


1


Input


10 1


Output


138


Input


10 2


Output


33

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
default_random_engine generator;
void solve();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(14) << fixed;
  cerr << setprecision(14) << fixed;
  int tests = 1;
  while (tests--) {
    solve();
  }
}
const int P = 998244353;
void add(int &a, int b) {
  a += b;
  if (a >= P) {
    a -= P;
  }
}
void mul(int &a, int b) { a = ll(a) * b % P; }
vector<int> f(const vector<int> &arr) {
  int x = arr[0];
  int cnt = 1;
  vector<int> res;
  for (int i = 1; i < (int)(arr).size(); ++i) {
    if (arr[i] == x) {
      ++cnt;
    } else {
      res.push_back(cnt);
      cnt = 1;
      x = arr[i];
    }
  }
  res.push_back(cnt);
  sort((res).begin(), (res).end());
  return res;
}
vector<int> fk(vector<int> arr, int k) {
  for (int i = 0; i < k; ++i) {
    arr = f(arr);
  }
  return arr;
}
vector<int> g(const vector<int> &arr) {
  vector<int> res;
  int x = 1;
  for (int i = (int)(arr).size() - 1; i >= 0; --i) {
    for (int j = 0; j < arr[i]; ++j) {
      res.push_back(x);
    }
    ++x;
  }
  return res;
}
int eval(const vector<int> &arr) {
  int x = 0;
  for (int i = 0; i < (int)(arr).size(); ++i) {
    x += ((int)(arr).size() - i) * arr[i];
  }
  return x;
}
vector<int> arr;
int cnt = 0;
set<vector<int>> setik;
void brute_force(int n, int k, int m = 1) {
  arr.push_back(m);
  if (eval(g(arr)) <= n) {
    setik.insert(fk(arr, k - 3));
    ++cnt;
    brute_force(n, k, m);
    arr.pop_back();
    brute_force(n, k, m + 1);
  } else {
    arr.pop_back();
  }
}
const int MAXN = 2022;
int dp[MAXN][MAXN];
void solve() {
  int n, k;
  cin >> n >> k;
  if (k >= 12) {
    cout << 1 << endl;
    return;
  }
  if (k == 1) {
    dp[0][0] = 1;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= i; ++j) {
        dp[i][j] = dp[i - 1][j - 1];
        add(dp[i][j], dp[i - j][j]);
        add(res, dp[i][j]);
      }
    }
    cout << res << endl;
  } else if (k == 2) {
    dp[0][0] = 1;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j * (j + 1) / 2 <= i; ++j) {
        dp[i][j] = dp[i - j][j - 1];
        add(dp[i][j], dp[i - j * (j + 1) / 2][j]);
        add(res, dp[i][j]);
      }
    }
    cout << res << endl;
  } else {
    brute_force(n, k);
    cout << (int)(setik).size() << endl;
  }
}