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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long long MOD = 998244353;
long long add(long long x, long long y) {
  x += y;
  if (x >= MOD) return x - MOD;
  return x;
}
long long sub(long long x, long long y) {
  x -= y;
  if (x < 0) return x + MOD;
  return x;
}
long long mult(long long x, long long y) { return (x * y) % MOD; }
const int N = 2024;
long long P[N];
long long dp[2][N][N];
int C;
int k;
long long ans = 0;
int a[N];
int b[2][N];
int sz;
bool check() {
  int t = 0, nt = 1;
  int s1 = 0, s2 = 0;
  for (int i = 0; i < sz; i++) b[t][s1++] = a[i];
  int kk = k;
  while (kk > 2) {
    kk--;
    swap(t, nt);
    s2 = s1;
    s1 = 0;
    for (int i = 1; i <= s2; i++) {
      if (s1 + b[nt][s2 - i] > 65) return false;
      for (int j = 0; j < b[nt][s2 - i]; j++) b[t][s1++] = i;
    }
  }
  int sum = 0, sumAll = 0;
  for (int i = 0; i < s1; i++) {
    sum += b[t][i];
    sumAll += sum;
    if (sumAll > C) return false;
  }
  return true;
}
void brute(int p) {
  a[sz++] = p;
  if (!check()) {
    sz--;
    return;
  }
  sz--;
  brute(p + 1);
  for (int i = 1;; i++) {
    a[sz++] = p;
    if (!check()) {
      sz -= i;
      return;
    }
    ans++;
    brute(p + 1);
  }
}
void brute3(int p, int sum, int sumAll) {
  if (sumAll + sum + p > C) return;
  brute3(p + 1, sum, sumAll);
  for (int i = 1;; i++) {
    sum += p;
    sumAll += sum;
    if (sumAll > C) return;
    ans++;
    brute3(p + 1, sum, sumAll);
  }
}
int main() {
  scanf("%d%d", &C, &k);
  if (k == 1) {
    P[0] = 1;
    for (int x = 1; x <= C; x++) {
      P[x] = 0;
      for (int t = 1;; t++) {
        if (t * (3 * t - 1) > 2 * x) break;
        if (t & 1)
          P[x] = add(P[x], P[x - t * (3 * t - 1) / 2]);
        else
          P[x] = sub(P[x], P[x - t * (3 * t - 1) / 2]);
        if (t * (3 * t + 1) > 2 * x) break;
        if (t & 1)
          P[x] = add(P[x], P[x - t * (3 * t + 1) / 2]);
        else
          P[x] = sub(P[x], P[x - t * (3 * t + 1) / 2]);
      }
    }
    for (int i = 1; i <= C; i++) ans = add(ans, P[i]);
    printf("%lld\n", ans);
    return 0;
  }
  if (k == 2) {
    dp[0][C][C] = 1;
    for (int t = 1; t <= C; t++) {
      for (int i = 0; i * t <= C; i++)
        for (int j = 0; j <= C; j++) dp[1][i][j] = 0;
      for (int i = C / t; i > 0; i--)
        for (int x = i * t; x <= C; x++) {
          dp[0][i - 1][x] = add(dp[0][i - 1][x], dp[0][i][x]);
          int y = x - i * t;
          dp[1][min(i, y / (t + 1))][y] =
              add(dp[1][min(i, y / (t + 1))][y], dp[0][i][x]);
        }
      for (int i = 0; i * t <= C; i++)
        for (int j = 0; j <= C; j++) {
          ans = add(ans, dp[1][i][j]);
          if (i > 0) dp[0][i][j] = dp[1][i][j];
        }
    }
    printf("%lld\n", ans);
    return 0;
  }
  brute(1);
  printf("%lld\n", ans);
  return 0;
}