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;
template <class T>
int chkmax(T& a, T b) {
  if (b > a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
int chkmin(T& a, T b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <class iterator>
void output(iterator begin, iterator end, ostream& out = cerr) {
  while (begin != end) {
    out << (*begin) << " ";
    begin++;
  }
  out << endl;
}
template <class T>
void output(T x, ostream& out = cerr) {
  output(x.begin(), x.end(), out);
}
void fast_io() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
vector<vector<int> > vectors = {{1},
                                {2},
                                {3},
                                {4},
                                {5},
                                {6},
                                {7},
                                {8},
                                {9},
                                {10},
                                {11},
                                {12},
                                {13},
                                {14},
                                {15},
                                {16},
                                {17},
                                {18},
                                {19},
                                {20},
                                {21},
                                {22},
                                {9, 9},
                                {8, 8},
                                {8, 9},
                                {8, 10},
                                {7, 7},
                                {7, 8},
                                {7, 9},
                                {7, 10},
                                {7, 11},
                                {7, 12},
                                {6, 6},
                                {6, 7},
                                {6, 8},
                                {6, 9},
                                {6, 10},
                                {6, 11},
                                {6, 12},
                                {6, 13},
                                {6, 14},
                                {5, 5},
                                {5, 6},
                                {5, 7},
                                {5, 8},
                                {5, 9},
                                {5, 10},
                                {5, 11},
                                {5, 12},
                                {5, 13},
                                {5, 14},
                                {5, 15},
                                {5, 5, 5},
                                {4, 4},
                                {4, 5},
                                {4, 6},
                                {4, 7},
                                {4, 8},
                                {4, 9},
                                {4, 10},
                                {4, 11},
                                {4, 12},
                                {4, 13},
                                {4, 14},
                                {4, 15},
                                {4, 16},
                                {4, 17},
                                {4, 6, 6},
                                {4, 5, 5},
                                {4, 5, 6},
                                {4, 5, 7},
                                {4, 5, 8},
                                {4, 4, 4},
                                {4, 4, 5},
                                {4, 4, 6},
                                {4, 4, 7},
                                {4, 4, 8},
                                {4, 4, 9},
                                {3, 3},
                                {3, 4},
                                {3, 5},
                                {3, 6},
                                {3, 7},
                                {3, 8},
                                {3, 9},
                                {3, 10},
                                {3, 11},
                                {3, 12},
                                {3, 13},
                                {3, 14},
                                {3, 15},
                                {3, 16},
                                {3, 17},
                                {3, 18},
                                {3, 6, 6},
                                {3, 6, 7},
                                {3, 6, 8},
                                {3, 5, 5},
                                {3, 5, 6},
                                {3, 5, 7},
                                {3, 5, 8},
                                {3, 5, 9},
                                {3, 5, 10},
                                {3, 4, 4},
                                {3, 4, 5},
                                {3, 4, 6},
                                {3, 4, 7},
                                {3, 4, 8},
                                {3, 4, 9},
                                {3, 4, 10},
                                {3, 4, 11},
                                {3, 3, 3},
                                {3, 3, 4},
                                {3, 3, 5},
                                {3, 3, 6},
                                {3, 3, 7},
                                {3, 3, 8},
                                {3, 3, 9},
                                {3, 3, 10},
                                {3, 3, 11},
                                {3, 3, 12},
                                {3, 3, 13},
                                {3, 3, 3, 3},
                                {3, 3, 3, 4},
                                {3, 3, 3, 5},
                                {2, 2},
                                {2, 3},
                                {2, 4},
                                {2, 5},
                                {2, 6},
                                {2, 7},
                                {2, 8},
                                {2, 9},
                                {2, 10},
                                {2, 11},
                                {2, 12},
                                {2, 13},
                                {2, 14},
                                {2, 15},
                                {2, 16},
                                {2, 17},
                                {2, 18},
                                {2, 19},
                                {2, 7, 7},
                                {2, 7, 8},
                                {2, 6, 6},
                                {2, 6, 7},
                                {2, 6, 8},
                                {2, 6, 9},
                                {2, 6, 10},
                                {2, 5, 5},
                                {2, 5, 6},
                                {2, 5, 7},
                                {2, 5, 8},
                                {2, 5, 9},
                                {2, 5, 10},
                                {2, 5, 11},
                                {2, 5, 12},
                                {2, 4, 4},
                                {2, 4, 5},
                                {2, 4, 6},
                                {2, 4, 7},
                                {2, 4, 8},
                                {2, 4, 9},
                                {2, 4, 10},
                                {2, 4, 11},
                                {2, 4, 12},
                                {2, 4, 13},
                                {2, 4, 4, 4},
                                {2, 3, 3},
                                {2, 3, 4},
                                {2, 3, 5},
                                {2, 3, 6},
                                {2, 3, 7},
                                {2, 3, 8},
                                {2, 3, 9},
                                {2, 3, 10},
                                {2, 3, 11},
                                {2, 3, 12},
                                {2, 3, 13},
                                {2, 3, 14},
                                {2, 3, 15},
                                {2, 3, 5, 5},
                                {2, 3, 4, 4},
                                {2, 3, 4, 5},
                                {2, 3, 4, 6},
                                {2, 3, 3, 3},
                                {2, 3, 3, 4},
                                {2, 3, 3, 5},
                                {2, 3, 3, 6},
                                {2, 3, 3, 7},
                                {2, 3, 3, 8},
                                {2, 2, 2},
                                {2, 2, 3},
                                {2, 2, 4},
                                {2, 2, 5},
                                {2, 2, 6},
                                {2, 2, 7},
                                {2, 2, 8},
                                {2, 2, 9},
                                {2, 2, 10},
                                {2, 2, 11},
                                {2, 2, 12},
                                {2, 2, 13},
                                {2, 2, 14},
                                {2, 2, 15},
                                {2, 2, 16},
                                {2, 2, 5, 5},
                                {2, 2, 5, 6},
                                {2, 2, 5, 7},
                                {2, 2, 4, 4},
                                {2, 2, 4, 5},
                                {2, 2, 4, 6},
                                {2, 2, 4, 7},
                                {2, 2, 4, 8},
                                {2, 2, 4, 9},
                                {2, 2, 3, 3},
                                {2, 2, 3, 4},
                                {2, 2, 3, 5},
                                {2, 2, 3, 6},
                                {2, 2, 3, 7},
                                {2, 2, 3, 8},
                                {2, 2, 3, 9},
                                {2, 2, 3, 10},
                                {2, 2, 3, 11},
                                {2, 2, 2, 2},
                                {2, 2, 2, 3},
                                {2, 2, 2, 4},
                                {2, 2, 2, 5},
                                {2, 2, 2, 6},
                                {2, 2, 2, 7},
                                {2, 2, 2, 8},
                                {2, 2, 2, 9},
                                {2, 2, 2, 10},
                                {2, 2, 2, 11},
                                {2, 2, 2, 12},
                                {2, 2, 2, 3, 3},
                                {2, 2, 2, 3, 4},
                                {2, 2, 2, 2, 2},
                                {2, 2, 2, 2, 3},
                                {2, 2, 2, 2, 4},
                                {2, 2, 2, 2, 5},
                                {2, 2, 2, 2, 6},
                                {1, 1},
                                {1, 2},
                                {1, 3},
                                {1, 4},
                                {1, 5},
                                {1, 6},
                                {1, 7},
                                {1, 8},
                                {1, 9},
                                {1, 10},
                                {1, 11},
                                {1, 12},
                                {1, 13},
                                {1, 14},
                                {1, 15},
                                {1, 16},
                                {1, 17},
                                {1, 18},
                                {1, 19},
                                {1, 20},
                                {1, 8, 8},
                                {1, 8, 9},
                                {1, 7, 7},
                                {1, 7, 8},
                                {1, 7, 9},
                                {1, 7, 10},
                                {1, 6, 6},
                                {1, 6, 7},
                                {1, 6, 8},
                                {1, 6, 9},
                                {1, 6, 10},
                                {1, 6, 11},
                                {1, 6, 12},
                                {1, 5, 5},
                                {1, 5, 6},
                                {1, 5, 7},
                                {1, 5, 8},
                                {1, 5, 9},
                                {1, 5, 10},
                                {1, 5, 11},
                                {1, 5, 12},
                                {1, 5, 13},
                                {1, 5, 14},
                                {1, 4, 4},
                                {1, 4, 5},
                                {1, 4, 6},
                                {1, 4, 7},
                                {1, 4, 8},
                                {1, 4, 9},
                                {1, 4, 10},
                                {1, 4, 11},
                                {1, 4, 12},
                                {1, 4, 13},
                                {1, 4, 14},
                                {1, 4, 15},
                                {1, 4, 5, 5},
                                {1, 4, 4, 4},
                                {1, 4, 4, 5},
                                {1, 4, 4, 6},
                                {1, 4, 4, 7},
                                {1, 3, 3},
                                {1, 3, 4},
                                {1, 3, 5},
                                {1, 3, 6},
                                {1, 3, 7},
                                {1, 3, 8},
                                {1, 3, 9},
                                {1, 3, 10},
                                {1, 3, 11},
                                {1, 3, 12},
                                {1, 3, 13},
                                {1, 3, 14},
                                {1, 3, 15},
                                {1, 3, 16},
                                {1, 3, 17},
                                {1, 3, 5, 5},
                                {1, 3, 5, 6},
                                {1, 3, 5, 7},
                                {1, 3, 4, 4},
                                {1, 3, 4, 5},
                                {1, 3, 4, 6},
                                {1, 3, 4, 7},
                                {1, 3, 4, 8},
                                {1, 3, 4, 9},
                                {1, 3, 3, 3},
                                {1, 3, 3, 4},
                                {1, 3, 3, 5},
                                {1, 3, 3, 6},
                                {1, 3, 3, 7},
                                {1, 3, 3, 8},
                                {1, 3, 3, 9},
                                {1, 3, 3, 10},
                                {1, 3, 3, 11},
                                {1, 2, 2},
                                {1, 2, 3},
                                {1, 2, 4},
                                {1, 2, 5},
                                {1, 2, 6},
                                {1, 2, 7},
                                {1, 2, 8},
                                {1, 2, 9},
                                {1, 2, 10},
                                {1, 2, 11},
                                {1, 2, 12},
                                {1, 2, 13},
                                {1, 2, 14},
                                {1, 2, 15},
                                {1, 2, 16},
                                {1, 2, 17},
                                {1, 2, 18},
                                {1, 2, 6, 6},
                                {1, 2, 6, 7},
                                {1, 2, 6, 8},
                                {1, 2, 5, 5},
                                {1, 2, 5, 6},
                                {1, 2, 5, 7},
                                {1, 2, 5, 8},
                                {1, 2, 5, 9},
                                {1, 2, 5, 10},
                                {1, 2, 4, 4},
                                {1, 2, 4, 5},
                                {1, 2, 4, 6},
                                {1, 2, 4, 7},
                                {1, 2, 4, 8},
                                {1, 2, 4, 9},
                                {1, 2, 4, 10},
                                {1, 2, 4, 11},
                                {1, 2, 3, 3},
                                {1, 2, 3, 4},
                                {1, 2, 3, 5},
                                {1, 2, 3, 6},
                                {1, 2, 3, 7},
                                {1, 2, 3, 8},
                                {1, 2, 3, 9},
                                {1, 2, 3, 10},
                                {1, 2, 3, 11},
                                {1, 2, 3, 12},
                                {1, 2, 3, 13},
                                {1, 2, 3, 3, 3},
                                {1, 2, 3, 3, 4},
                                {1, 2, 3, 3, 5},
                                {1, 2, 2, 2},
                                {1, 2, 2, 3},
                                {1, 2, 2, 4},
                                {1, 2, 2, 5},
                                {1, 2, 2, 6},
                                {1, 2, 2, 7},
                                {1, 2, 2, 8},
                                {1, 2, 2, 9},
                                {1, 2, 2, 10},
                                {1, 2, 2, 11},
                                {1, 2, 2, 12},
                                {1, 2, 2, 13},
                                {1, 2, 2, 14},
                                {1, 2, 2, 15},
                                {1, 2, 2, 4, 4},
                                {1, 2, 2, 4, 5},
                                {1, 2, 2, 4, 6},
                                {1, 2, 2, 3, 3},
                                {1, 2, 2, 3, 4},
                                {1, 2, 2, 3, 5},
                                {1, 2, 2, 3, 6},
                                {1, 2, 2, 3, 7},
                                {1, 2, 2, 3, 8},
                                {1, 2, 2, 2, 2},
                                {1, 2, 2, 2, 3},
                                {1, 2, 2, 2, 4},
                                {1, 2, 2, 2, 5},
                                {1, 2, 2, 2, 6},
                                {1, 2, 2, 2, 7},
                                {1, 2, 2, 2, 8},
                                {1, 2, 2, 2, 9},
                                {1, 2, 2, 2, 10},
                                {1, 2, 2, 2, 2, 2},
                                {1, 1, 1},
                                {1, 1, 2},
                                {1, 1, 3},
                                {1, 1, 4},
                                {1, 1, 5},
                                {1, 1, 6},
                                {1, 1, 7},
                                {1, 1, 8},
                                {1, 1, 9},
                                {1, 1, 10},
                                {1, 1, 11},
                                {1, 1, 12},
                                {1, 1, 13},
                                {1, 1, 14},
                                {1, 1, 15},
                                {1, 1, 16},
                                {1, 1, 17},
                                {1, 1, 18},
                                {1, 1, 19},
                                {1, 1, 7, 7},
                                {1, 1, 7, 8},
                                {1, 1, 6, 6},
                                {1, 1, 6, 7},
                                {1, 1, 6, 8},
                                {1, 1, 6, 9},
                                {1, 1, 6, 10},
                                {1, 1, 5, 5},
                                {1, 1, 5, 6},
                                {1, 1, 5, 7},
                                {1, 1, 5, 8},
                                {1, 1, 5, 9},
                                {1, 1, 5, 10},
                                {1, 1, 5, 11},
                                {1, 1, 5, 12},
                                {1, 1, 4, 4},
                                {1, 1, 4, 5},
                                {1, 1, 4, 6},
                                {1, 1, 4, 7},
                                {1, 1, 4, 8},
                                {1, 1, 4, 9},
                                {1, 1, 4, 10},
                                {1, 1, 4, 11},
                                {1, 1, 4, 12},
                                {1, 1, 4, 13},
                                {1, 1, 4, 4, 4},
                                {1, 1, 3, 3},
                                {1, 1, 3, 4},
                                {1, 1, 3, 5},
                                {1, 1, 3, 6},
                                {1, 1, 3, 7},
                                {1, 1, 3, 8},
                                {1, 1, 3, 9},
                                {1, 1, 3, 10},
                                {1, 1, 3, 11},
                                {1, 1, 3, 12},
                                {1, 1, 3, 13},
                                {1, 1, 3, 14},
                                {1, 1, 3, 15},
                                {1, 1, 3, 4, 4},
                                {1, 1, 3, 4, 5},
                                {1, 1, 3, 4, 6},
                                {1, 1, 3, 3, 3},
                                {1, 1, 3, 3, 4},
                                {1, 1, 3, 3, 5},
                                {1, 1, 3, 3, 6},
                                {1, 1, 3, 3, 7},
                                {1, 1, 3, 3, 8},
                                {1, 1, 2, 2},
                                {1, 1, 2, 3},
                                {1, 1, 2, 4},
                                {1, 1, 2, 5},
                                {1, 1, 2, 6},
                                {1, 1, 2, 7},
                                {1, 1, 2, 8},
                                {1, 1, 2, 9},
                                {1, 1, 2, 10},
                                {1, 1, 2, 11},
                                {1, 1, 2, 12},
                                {1, 1, 2, 13},
                                {1, 1, 2, 14},
                                {1, 1, 2, 15},
                                {1, 1, 2, 16},
                                {1, 1, 2, 5, 5},
                                {1, 1, 2, 5, 6},
                                {1, 1, 2, 5, 7},
                                {1, 1, 2, 4, 4},
                                {1, 1, 2, 4, 5},
                                {1, 1, 2, 4, 6},
                                {1, 1, 2, 4, 7},
                                {1, 1, 2, 4, 8},
                                {1, 1, 2, 4, 9},
                                {1, 1, 2, 3, 3},
                                {1, 1, 2, 3, 4},
                                {1, 1, 2, 3, 5},
                                {1, 1, 2, 3, 6},
                                {1, 1, 2, 3, 7},
                                {1, 1, 2, 3, 8},
                                {1, 1, 2, 3, 9},
                                {1, 1, 2, 3, 10},
                                {1, 1, 2, 2, 2},
                                {1, 1, 2, 2, 3},
                                {1, 1, 2, 2, 4},
                                {1, 1, 2, 2, 5},
                                {1, 1, 2, 2, 6},
                                {1, 1, 2, 2, 7},
                                {1, 1, 2, 2, 8},
                                {1, 1, 2, 2, 9},
                                {1, 1, 2, 2, 10},
                                {1, 1, 2, 2, 11},
                                {1, 1, 2, 2, 12},
                                {1, 1, 2, 2, 3, 3},
                                {1, 1, 2, 2, 3, 4},
                                {1, 1, 2, 2, 2, 2},
                                {1, 1, 2, 2, 2, 3},
                                {1, 1, 2, 2, 2, 4},
                                {1, 1, 2, 2, 2, 5},
                                {1, 1, 2, 2, 2, 6},
                                {1, 1, 1, 1},
                                {1, 1, 1, 2},
                                {1, 1, 1, 3},
                                {1, 1, 1, 4},
                                {1, 1, 1, 5},
                                {1, 1, 1, 6},
                                {1, 1, 1, 7},
                                {1, 1, 1, 8},
                                {1, 1, 1, 9},
                                {1, 1, 1, 10},
                                {1, 1, 1, 11},
                                {1, 1, 1, 12},
                                {1, 1, 1, 13},
                                {1, 1, 1, 14},
                                {1, 1, 1, 15},
                                {1, 1, 1, 16},
                                {1, 1, 1, 17},
                                {1, 1, 1, 18},
                                {1, 1, 1, 6, 6},
                                {1, 1, 1, 6, 7},
                                {1, 1, 1, 5, 5},
                                {1, 1, 1, 5, 6},
                                {1, 1, 1, 5, 7},
                                {1, 1, 1, 5, 8},
                                {1, 1, 1, 5, 9},
                                {1, 1, 1, 4, 4},
                                {1, 1, 1, 4, 5},
                                {1, 1, 1, 4, 6},
                                {1, 1, 1, 4, 7},
                                {1, 1, 1, 4, 8},
                                {1, 1, 1, 4, 9},
                                {1, 1, 1, 4, 10},
                                {1, 1, 1, 4, 11},
                                {1, 1, 1, 3, 3},
                                {1, 1, 1, 3, 4},
                                {1, 1, 1, 3, 5},
                                {1, 1, 1, 3, 6},
                                {1, 1, 1, 3, 7},
                                {1, 1, 1, 3, 8},
                                {1, 1, 1, 3, 9},
                                {1, 1, 1, 3, 10},
                                {1, 1, 1, 3, 11},
                                {1, 1, 1, 3, 12},
                                {1, 1, 1, 3, 13},
                                {1, 1, 1, 3, 3, 3},
                                {1, 1, 1, 3, 3, 4},
                                {1, 1, 1, 3, 3, 5},
                                {1, 1, 1, 2, 2},
                                {1, 1, 1, 2, 3},
                                {1, 1, 1, 2, 4},
                                {1, 1, 1, 2, 5},
                                {1, 1, 1, 2, 6},
                                {1, 1, 1, 2, 7},
                                {1, 1, 1, 2, 8},
                                {1, 1, 1, 2, 9},
                                {1, 1, 1, 2, 10},
                                {1, 1, 1, 2, 11},
                                {1, 1, 1, 2, 12},
                                {1, 1, 1, 2, 13},
                                {1, 1, 1, 2, 14},
                                {1, 1, 1, 2, 4, 4},
                                {1, 1, 1, 2, 4, 5},
                                {1, 1, 1, 2, 3, 3},
                                {1, 1, 1, 2, 3, 4},
                                {1, 1, 1, 2, 3, 5},
                                {1, 1, 1, 2, 3, 6},
                                {1, 1, 1, 2, 3, 7},
                                {1, 1, 1, 2, 2, 2},
                                {1, 1, 1, 2, 2, 3},
                                {1, 1, 1, 2, 2, 4},
                                {1, 1, 1, 2, 2, 5},
                                {1, 1, 1, 2, 2, 6},
                                {1, 1, 1, 2, 2, 7},
                                {1, 1, 1, 2, 2, 8},
                                {1, 1, 1, 2, 2, 9},
                                {1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 2},
                                {1, 1, 1, 1, 3},
                                {1, 1, 1, 1, 4},
                                {1, 1, 1, 1, 5},
                                {1, 1, 1, 1, 6},
                                {1, 1, 1, 1, 7},
                                {1, 1, 1, 1, 8},
                                {1, 1, 1, 1, 9},
                                {1, 1, 1, 1, 10},
                                {1, 1, 1, 1, 11},
                                {1, 1, 1, 1, 12},
                                {1, 1, 1, 1, 13},
                                {1, 1, 1, 1, 14},
                                {1, 1, 1, 1, 15},
                                {1, 1, 1, 1, 16},
                                {1, 1, 1, 1, 5, 5},
                                {1, 1, 1, 1, 5, 6},
                                {1, 1, 1, 1, 4, 4},
                                {1, 1, 1, 1, 4, 5},
                                {1, 1, 1, 1, 4, 6},
                                {1, 1, 1, 1, 4, 7},
                                {1, 1, 1, 1, 4, 8},
                                {1, 1, 1, 1, 3, 3},
                                {1, 1, 1, 1, 3, 4},
                                {1, 1, 1, 1, 3, 5},
                                {1, 1, 1, 1, 3, 6},
                                {1, 1, 1, 1, 3, 7},
                                {1, 1, 1, 1, 3, 8},
                                {1, 1, 1, 1, 3, 9},
                                {1, 1, 1, 1, 3, 10},
                                {1, 1, 1, 1, 2, 2},
                                {1, 1, 1, 1, 2, 3},
                                {1, 1, 1, 1, 2, 4},
                                {1, 1, 1, 1, 2, 5},
                                {1, 1, 1, 1, 2, 6},
                                {1, 1, 1, 1, 2, 7},
                                {1, 1, 1, 1, 2, 8},
                                {1, 1, 1, 1, 2, 9},
                                {1, 1, 1, 1, 2, 10},
                                {1, 1, 1, 1, 2, 11},
                                {1, 1, 1, 1, 2, 3, 3},
                                {1, 1, 1, 1, 2, 2, 2},
                                {1, 1, 1, 1, 2, 2, 3},
                                {1, 1, 1, 1, 2, 2, 4},
                                {1, 1, 1, 1, 2, 2, 5},
                                {1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 2},
                                {1, 1, 1, 1, 1, 3},
                                {1, 1, 1, 1, 1, 4},
                                {1, 1, 1, 1, 1, 5},
                                {1, 1, 1, 1, 1, 6},
                                {1, 1, 1, 1, 1, 7},
                                {1, 1, 1, 1, 1, 8},
                                {1, 1, 1, 1, 1, 9},
                                {1, 1, 1, 1, 1, 10},
                                {1, 1, 1, 1, 1, 11},
                                {1, 1, 1, 1, 1, 12},
                                {1, 1, 1, 1, 1, 13},
                                {1, 1, 1, 1, 1, 4, 4},
                                {1, 1, 1, 1, 1, 3, 3},
                                {1, 1, 1, 1, 1, 3, 4},
                                {1, 1, 1, 1, 1, 3, 5},
                                {1, 1, 1, 1, 1, 3, 6},
                                {1, 1, 1, 1, 1, 2, 2},
                                {1, 1, 1, 1, 1, 2, 3},
                                {1, 1, 1, 1, 1, 2, 4},
                                {1, 1, 1, 1, 1, 2, 5},
                                {1, 1, 1, 1, 1, 2, 6},
                                {1, 1, 1, 1, 1, 2, 7},
                                {1, 1, 1, 1, 1, 2, 8},
                                {1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 2},
                                {1, 1, 1, 1, 1, 1, 3},
                                {1, 1, 1, 1, 1, 1, 4},
                                {1, 1, 1, 1, 1, 1, 5},
                                {1, 1, 1, 1, 1, 1, 6},
                                {1, 1, 1, 1, 1, 1, 7},
                                {1, 1, 1, 1, 1, 1, 8},
                                {1, 1, 1, 1, 1, 1, 9},
                                {1, 1, 1, 1, 1, 1, 2, 2},
                                {1, 1, 1, 1, 1, 1, 1, 1},
                                {1, 1, 1, 1, 1, 1, 1, 2},
                                {1, 1, 1, 1, 1, 1, 1, 3},
                                {1, 1, 1, 1, 1, 1, 1, 4}};
const int INF = 1e9;
const int MOD = 998244353;
const int mx = 2040;
int dp0[mx][mx], n, k;
vector<int> low_rev_f(vector<int> a) {
  reverse(a.begin(), a.end());
  vector<int> res;
  for (int i = 0; i < a.size(); ++i) {
    for (int j = 0; j < a[i]; ++j) {
      res.push_back(i + 1);
    }
  }
  return res;
}
int flex(vector<int> v) {
  if (v.size() == 1 && v[0] == 1) {
    return INF;
  }
  int res = 0, sum, req_sum = -1;
  while (true) {
    sum = 0;
    for (auto x : v) {
      sum += x;
    }
    if (sum > n) {
      return res;
    }
    v = low_rev_f(v);
    res++;
  }
}
vector<vector<int> > ans23 = {
    {1,         1,         1,         2,         2,         2,
     4,         4,         4,         6,         7,         7,
     10,        11,        11,        15,        17,        17,
     22,        24,        25,        32,        35,        36,
     44,        48,        50,        60,        66,        68,
     81,        89,        92,        107,       117,       121,
     141,       153,       159,       181,       197,       205,
     233,       252,       262,       295,       320,       332,
     372,       401,       417,       465,       501,       520,
     575,       619,       645,       710,       763,       793,
     869,       933,       971,       1059,      1134,      1180,
     1286,      1374,      1430,      1549,      1654,      1722,
     1863,      1985,      2065,      2225,      2372,      2467,
     2654,      2821,      2934,      3149,      3345,      3478,
     3724,      3949,      4109,      4391,      4652,      4835,
     5157,      5460,      5676,      6043,      6390,      6638,
     7059,      7457,      7747,      8220,      8676,      9013,
     9553,      10071,     10459,     11066,     11662,     12108,
     12798,     13468,     13980,     14760,     15526,     16110,
     16988,     17850,     18522,     19509,     20487,     21247,
     22357,     23463,     24333,     25576,     26818,     27800,
     29200,     30598,     31715,     33274,     34842,     36106,
     37856,     39614,     41039,     42985,     44962,     46567,
     48742,     50944,     52750,     55173,     57641,     59668,
     62361,     65102,     67386,     70379,     73440,     75989,
     79312,     82716,     85575,     89258,     93039,     96222,
     100316,    104514,    108070,    112587,    117239,    121202,
     126209,    131361,    135769,    141286,    146996,    151897,
     157996,    164294,    169732,    176459,    183424,    189450,
     196860,    204528,    211216,    219377,    227840,    235222,
     244193,    253511,    261686,    271544,    281795,    290803,
     301643,    312909,    322859,    334736,    347103,    358069,
     371113,    384680,    396750,    411019,    425909,    439188,
     454830,    471126,    485710,    502821,    520680,    536693,
     555400,    574912,    592496,    612935,    634279,    653536,
     675846,    699159,    720277,    744619,    770063,    793143,
     819705,    847460,    872723,    901647,    931895,    959495,
     991021,    1023968,   1054109,   1088385,   1124275,   1157169,
     1194475,   1233493,   1269354,   1309903,   1352355,   1391434,
     1435490,   1481575,   1524149,   1571991,   1622064,   1668371,
     1720281,   1774621,   1825011,   1881310,   1940253,   1994976,
     2056031,   2119938,   2179411,   2245526,   2314749,   2379298,
     2450932,   2525893,   2595932,   2673413,   2754567,   2830507,
     2914362,   3002116,   3084393,   3175049,   3269971,   3359075,
     3457050,   3559570,   3656046,   3761882,   3872659,   3977000,
     4091243,   4210816,   4323683,   4446970,   4576004,   4697925,
     4830943,   4970113,   5101847,   5245221,   5395228,   5537433,
     5692007,   5853652,   6007110,   6173540,   6347674,   6513190,
     6692449,   6879883,   7058295,   7251200,   7452959,   7645206,
     7852750,   8069691,   8276787,   8499984,   8733296,   8956199,
     9196093,   9446820,   9686747,   9944526,   10213906,  10471875,
     10748777,  11038064,  11315480,  11612733,  11923246,  12221349,
     12540444,  12873636,  13193886,  13536115,  13893538,  14237428,
     14604528,  14987710,  15356787,  15750290,  16161067,  16557059,
     16978784,  17418788,  17843514,  18295288,  18766629,  19221916,
     19705673,  20210277,  20698283,  21216140,  21756222,  22278880,
     22833084,  23410920,  23970719,  24563526,  25181486,  25780677,
     26414718,  27075418,  27716642,  28394322,  29100522,  29786442,
     30510770,  31265243,  31998670,  32772432,  33578395,  34362411,
     35188818,  36049227,  36887059,  37769375,  38687902,  39582854,
     40524518,  41504577,  42460385,  43465136,  44510653,  45530847,
     46602626,  47717593,  48806447,  49949244,  51137844,  52299394,
     53517765,  54784570,  56023439,  57321667,  58671432,  59992284,
     61375543,  62813172,  64220958,  65694154,  67225131,  68725172,
     70293863,  71923439,  73521336,  75191191,  76925609,  78627118,
     80404076,  82249290,  84060828,  85951336,  87914081,  89841847,
     91852624,  93939723,  95990979,  98128976,  100347645, 102529407,
     104802335, 107160332, 109480446, 111895747, 114401182, 116867659,
     119434066, 122095361, 124716644, 127442530, 130268904, 133054058,
     135948851, 138949344, 141907863, 144981135, 148166149, 151307870,
     154569740, 157949410, 161285106, 164746416, 168332020, 171872254,
     175544301, 179347340, 183104242, 186998811, 191031435, 195016837,
     199146697, 203421857, 207648923, 212026732, 216557979, 221040139,
     225680276, 230481677, 235233082, 240149650, 245236461, 250272221,
     255480870, 260868251, 266204101, 271720743, 277425797, 283078174,
     288919654, 294959271, 300945886, 307130060, 313522823, 319861380,
     326406924, 333171837, 339882200, 346808560, 353965608, 361067415,
     368395535, 375965998, 383480887, 391231769, 399237795, 407187789,
     415384813, 423849547, 432257933, 440924367, 449872631, 458764071,
     467925355, 477382090, 486782303, 496464457, 506457346, 516393246,
     526623705, 537180297, 547680597, 558488394, 569638813, 580732551,
     592147989, 603923001, 615642136, 627696820, 640128881, 652505432,
     665233143, 678356568, 691425383, 704860204, 718710706, 732507434,
     746686886, 761301865, 775864142, 790825802, 806244938, 821612398,
     837397085, 853660694, 869874714, 886524272, 903676423, 920780208,
     938338651, 956423660, 974463093, 992976872, 13798400,  32820132,
     52337561,  72433463,  92488341,  113059995, 134237722, 155377013,
     177056444, 199370436, 221649504, 244491258, 267998277, 291473921,
     315537333, 340296717, 365028663, 390373514, 416447969, 442499034,
     469189903, 496643522, 524079135, 552182137, 581084189, 609972786,
     639557548, 669978205, 700392044, 731531659, 763546294, 795559247,
     828329831, 862015837, 895707646, 930188844, 965627567, 2834637,
     39110329,  76387123,  113684941, 151841094, 191044883, 230278112,
     270407141, 311630788, 352893041, 395088799, 438430148, 481819583,
     526182648, 571741912, 617360659, 663994264, 711879031, 759833937,
     808846647, 859166305, 909569581, 961075006, 15702157,  68669089,
     122785552, 178329122, 233983058, 290834114, 349175883, 407642464,
     467357927, 528630007, 590043438, 652756673, 717096387, 781594471,
     847447933, 914998849, 982726392, 53621024,  124533673, 195641912,
     268221199, 342650412, 417296819, 493475613, 571586490, 649935532,
     729880767, 811841723, 894065713, 977951851, 65697827,  151974283,
     239982817, 330186793, 420704408, 513024828, 607635714, 702587446,
     799418243, 898637821, 998228545, 101529727, 205567845, 310008410,
     416485844, 525561667, 635073046, 746704281, 861046894, 975859629,
     94635876,  214481581, 334835578, 457487907, 583087029, 709232518,
     837770449, 969379282, 103333578, 238021982, 375912071, 514433680,
     655547832, 799998622, 945128757, 94711612,  246015796, 398047017,
     552887223, 711349747, 870591664, 34510119,  200448099, 367219541,
     537032105, 710776105, 885410658, 64963976,  246859063, 429704356,
     615841755, 806244180, 997661391, 194259124, 393544704, 593910477,
     797839244, 8149383,   217856567, 431269561, 649499974, 868954305,
     94020362,  322346036, 551975171, 785613600, 26228459,  266471349,
     510886701, 760735658, 13810966,  269467098, 530779706, 793652904,
     62793571,  336063540, 610988719, 890604134, 178101631, 465597212,
     757971125, 58471989,  359076472, 664753034, 977060551, 293090652,
     612638363, 939082383, 269366496, 603376376, 944561155, 289703195,
     638789234, 995337422, 355971374, 720772650, 95089963,  470112135,
     851294024, 242300618, 634152020, 34157816,  440799549, 850186460,
     267982091, 692744945, 122160426, 556732320, 2131443,   448830025,
     902713224, 367778370, 834311062, 310064741, 793863419, 282813176,
     777764140, 284654490, 793370393, 311900532, 839260082, 372143200,
     911644669, 463900724, 20127027,  583295217, 159647502, 738420455,
     327987854, 927672367, 533508689, 148729780, 774531251, 406712031,
     48643992,  701632450, 361238179, 30969058,  712256107, 400408195,
     99078260,  809813824, 527675802, 256460334, 997846273, 746627514,
     506751307, 281781177, 62737992,  853716044, 661929821, 476361414,
     303022979, 145756544, 993264651, 855223877, 733868643, 619362548,
     518041375, 434040277, 357226855, 294096240, 248945937, 211333179,
     187928434, 183183397, 186341381, 204244306, 241518067, 287074837,
     347939009, 428900173, 518543625, 624073972, 750463221, 885946541,
     39673547,  213284548, 396426402, 596678014, 819384259, 53821494,
     304260403, 577994124, 862176593, 166538001, 493309051, 831013429,
     189594991, 571486257, 964822771, 379748138, 818918128, 271818199,
     743544248, 243988944, 755204470, 289523156, 850054076, 425440411,
     22975337,  647750315, 287981122, 949430468, 642706699, 350302583,
     81728427,  842572840, 620146336, 422434779, 257047284, 107300720,
     981433259, 890830451, 816575588, 768902407, 755965285, 760101200,
     791808928, 859520443, 945068056, 60954587,  212404437, 382479054,
     582197834, 820590220, 80184087,  368753069, 697407004, 48114451,
     428931759, 851279507, 296570502, 773140283, 294505240, 836220933,
     413937902, 36242923,  679864593, 360739486, 87813899,  837193335,
     625125624, 460917909, 321813122, 220844622, 169454403, 144236680,
     158552109, 224220542, 317183705, 451109425, 638227345, 853799415,
     113584697, 426701217, 769477628, 157999897, 601824042, 78314134,
     598636655, 179791947, 791404457, 452006854, 173790971, 927378096,
     731660215, 599284209, 501876156, 455169032, 474049121, 529341995,
     637162557, 812883729, 28291011,  296352641, 634707253, 14306941,
     448520837, 955497751, 505351531, 113583131, 795378653, 521736085,
     308567091, 173351748, 82693206,  54658575,  107312811, 206337041,
     370223511, 617604376, 913240803, 277801166, 727019185, 228196401,
     797172819, 457314760, 169694840, 952338975, 829259951, 760507954,
     766328929, 867875214, 27691257,  262956221, 597258331, 990322645,
     465083165, 42298491,  678867500, 399938326, 226998376, 117590692,
     93852143,  179744802, 331683941, 572292087, 926307899, 350728366,
     865180860, 498672636, 203515970, 3359372,   922756419, 918052143,
     13426568,  232488543, 528602648, 926470914, 455825249, 65220293,
     778164477, 627008977, 559015247, 599986431, 779663027, 47466198,
     426277610, 948498491, 562190178, 292544421, 171169367, 142960894,
     235469756, 481257176, 823788843, 292956859, 918834581, 646913068,
     504195670, 525268955, 650624456, 909636511, 339718780, 876290315,
     552877560, 404453117, 368394902, 475347195, 763165657, 169342748,
     721686748, 462703541, 324738702, 339759597, 547945180, 881689769,
     375424470, 68765173,  890633332, 877881666, 73143147,  401804721,
     899688077, 612435945, 465386096, 493307127, 741426234, 136719656,
     711190823, 514896051, 469422465, 611021723, 987642463, 522418291,
     250611088, 221572732, 354725248, 687838974, 273496003, 27300368,
     986072883, 207396966, 601307324, 210666479, 87582571,  145211997,
     423751623, 978626098, 722588058, 694873499, 952551798, 406141802,
     95743417,  80066664,  265608543, 695060067, 430631397, 374716462,
     570894195, 83096157,  809604421, 798385886, 113442048, 650594260,
     458720403, 601894362, 976996209, 632044041, 633028715, 874248981,
     404679179, 292249395, 428681166, 862112908, 665996880, 727615688,
     97864841,  846959981, 864750124, 201316728, 929007045, 934879773,
     270039703, 10720628,  37638265,  402885947, 188466223, 270409995,
     701861769, 567058935, 739088035, 273885367, 254539906, 552825884,
     225755425, 358786629, 820632747, 669362688, 992912964, 658538439,
     721923132, 277023498, 184372341, 502493577, 327939975, 517903914,
     133844901, 271429494, 786243543, 740856065, 235437002, 120344745,
     457596974, 351872986, 650008680, 416938549, 756738035, 516115619,
     757728428, 592048378, 858612389, 624804712, 2382711,   825321396,
     165778166, 135050017, 566820802, 530976826, 145512968, 238372615,
     879006139, 192147205, 998243233, 373281342, 438309393, 16656752,
     178668363, 54036635,  458412278, 466947279, 211102702, 502230467,
     416889746, 90080365,  328793875, 210943754, 873497070, 124212131,
     37176299,  754816321, 80359947,  89313044,  927996324, 394932902,
     567099215, 596482685, 273391692, 678002887, 966382276, 923918689,
     634077588, 255300823, 566300139, 653772611, 680426573, 421621064,
     962145649, 472540307, 719509887, 792860022, 864117240, 698196998,
     384784345, 99930076,  601416351, 982252714, 424992616, 680119359,
     842312544, 98859334,  194659068, 226031762, 383471689, 409601063,
     400685098, 552206569, 600996814, 644991274, 884864996, 53157040,
     246062586, 671274620, 55278736,  495975578, 208242779, 907019546,
     699079859, 799536635, 920519169, 168780032, 763393131, 413489412,
     224193423, 423847399, 711468663, 197496185, 114541267, 154823447,
     428947757, 179054220, 88753451,  270536027, 971081406, 870417517,
     82990476,  858301530, 871030259, 237540109, 215671254, 469185525,
     118232445, 427327058, 54570627,  118553582, 892424854, 28356119,
     643545817, 23384528,  803530274, 113698187, 237730905, 808591506,
     954639687, 970520645, 481123353, 613355530, 671231082, 271331664,
     542760495, 797149210, 642700666, 212423851, 822393015, 75661869,
     103955777, 234866089, 59257751,  712794494, 533133984, 100353427,
     552426116, 235435593, 718654026, 147541485, 869835235, 452460235,
     38020795,  984812134, 850326010, 779416094, 142999282, 481842752,
     946759794, 917865505, 927846629, 129845131, 908290965, 791027375,
     930172206, 725024314, 687959514, 975282589, 996296533, 254600860,
     905509395, 371913210, 143341413, 381086607, 514976426, 27073900,
     79522860,  112747148, 596052392, 697596059, 866950184, 563794782,
     955492976, 506192343, 660604735, 592132778, 772846589, 639194920,
     365581776, 435628896, 273848222, 57256965,  281488249, 358794245,
     468989875, 121517169, 712740858, 428713131, 787902350, 179177800,
     784395505, 141683899, 620088238, 411247253, 61107698,  927181346,
     205777654, 452605079, 17120470,  91405155,  250079887, 825317664,
     17504810,  409846564, 324163297, 958393528, 917060025, 504229372,
     920918097, 786103912, 389418471, 934782769, 57935970,  30185013,
     62075736,  799153876, 504791763, 389049304, 114882028, 924989960,
     39594950,  132169447, 433462864, 163246364, 14829741,  201175889,
     943533395, 955286681, 433320376, 600217994, 186381839, 370332315,
     381528758, 964143357, 285245949, 572134651, 590302324, 486144903,
     493873029, 395244976, 319267969, 503345922, 747911197, 165892218,
     994615745, 58560314,  445619605, 403469863, 769042176, 618716580,
     200110471, 369802085, 185560109, 896603171, 385079909, 684220076,
     52052037,  384299655, 700127012, 259184443, 978345689, 858577053,
     161458808, 825341982, 831106816, 443719169, 625395522, 334650930,
     838418206, 126567299, 131466167, 127029586, 122781480, 33201197,
     134193167, 458601565, 899289331, 737525919, 30303875,  644752156,
     867645986, 780350252, 231186789, 505299717, 710967732, 673425116,
     683411600, 872976068, 45942831,  493190176, 376474098, 472210904,
     80536871,  384548385, 140119867, 647517802, 122470696, 290919901,
     460661439, 871630956, 230054379, 842178647, 980094588, 322687483,
     181991226, 855440810, 997826005, 926802200, 969647718, 752844480,
     598073066, 862745360, 148419221, 777147884, 142688649, 812008155,
     120042966, 483309713, 448131332, 348056757, 635458348, 826385209,
     260401380, 420979855, 795469470, 727288419, 735421169, 277796513,
     698601282, 554538427, 271991109, 200826567, 929543292, 857540758,
     338962750, 996148216, 199437468, 303536912, 971072006, 539005321,
     368044442, 157957420, 210414199, 891953835, 942374508, 630542515,
     327312452, 807807863, 311477657, 211475017, 324489743, 852538759,
     178520474, 156059178, 953032235, 956342523, 64645037,  407327703,
     375775347, 908981037, 107947701, 361091862, 654311043, 50629526,
     942916173, 364358370, 336111465, 260517543, 210670923, 173703426,
     554598599, 473847636, 879093804, 183027785, 547869844, 885860085,
     612382713, 939103179, 739193850, 430427259, 275090389, 104382738,
     340683531, 297680018, 764344727, 170626008, 875866603, 632863670,
     870891691, 7952969,   746121973, 525783921, 812850101, 273530901,
     345728811, 552548557, 515101401, 677282199, 617534720, 910800929,
     8932600,   541039777, 42675966,  962867675, 997048550, 629495277,
     317212417, 808762300, 545741243, 987510941, 945947761, 811610660,
     51995385,  534470277, 605284204, 734168532, 854282763, 261166932,
     427380294, 351010731, 276310377, 681580291, 629904859, 314919394,
     219411359, 470355868, 211989254, 929463349, 820872969, 974568117,
     883561524, 810783572, 793665993, 329274499, 749050575, 39713047,
     697402705, 131891878, 268427146, 612340938, 642891215, 232846848,
     888511189, 166824520, 878960394, 541989569, 781802710, 358961450,
     787917044, 776906093, 26439389,  54667928,  647298157, 447049885,
     976335329, 104429084, 406850153, 415101705, 77326223,  909219468,
     448108421, 721926432, 189697703, 385439019, 427940603, 709009523,
     770181409, 815344362, 174088343, 387959374, 751475068, 528487735,
     266429684, 348359396, 970240870, 686298936, 970270761, 952237646,
     188683727, 247145993, 189304070, 573068633, 67577521,  659406957,
     913786572, 595491539, 622282203, 560905930, 276267739, 613962806,
     146031118, 835142184, 459570834, 589203101, 295957140, 278235765,
     112856542, 973743250, 489645694, 236730803, 498609709, 823569329,
     794803198, 805583941, 326794998, 940653670, 157900467, 365021188,
     152836537, 140690810, 638582470, 239691138, 678461320, 186770843,
     355588361, 42802649,  392533321, 3433738,   849530910, 995910037,
     42176076,  85179236,  103439806, 697001297, 95767439,  185891034,
     571679892, 609179867, 100589451, 648553627, 741643950, 92272077,
     305636771, 3173064,   803488989, 320233329, 305434426, 288935171,
     881427477, 978106267, 15553357,  602122296, 776178542, 877416630,
     521395658, 884280630, 213153454, 121238289, 933331197, 798342342,
     332727207, 9895150,   874724755, 549802427, 659188911, 149922742,
     638752328, 909657720, 806141713, 947126915, 274662765, 524314040,
     319698391, 759953120, 480904300, 102539338, 888140047, 368015796,
     161246138, 699503036, 402959861, 890205476, 767182929, 340051231,
     229508696, 212550582, 483701721, 664865047, 710312656, 700616298,
     257447246, 512728338, 434144599, 640661605, 451602274, 713567193,
     48395244,  956739298, 174156745, 313936019, 74417987,  63067314,
     895963034, 466903898, 259883058, 888760963, 445226286, 288985226,
     34494239,  969072132, 333910205, 735481253, 672111685, 251783851,
     82703170,  867953809, 589785504, 851788769, 574080500, 601787680,
     539488356, 521675708, 262585516, 361653268, 176536052, 283770131,
     281461900, 750177725, 133472778, 21828789,  227044522, 51015232,
     82724219,  367091706, 65392688,  759892776, 737089132, 12951935,
     165930239, 722466978, 555341024, 239129921, 545914981, 200817357,
     772050155, 287449921, 317738401, 428751627, 901465849, 159816566,
     758838647, 244589992, 881018039, 225383778, 82747606,  563903415,
     218101783, 122094452, 229381956, 80004168,  28102820,  864274627,
     125523506, 442491209, 447355123, 663336125, 13928029,  959045224,
     21655577,  408438555, 419551166, 561568139, 345058460, 895074521,
     713448966, 609638926, 538951529, 989958453, 85254514,  600099023,
     18940261,  769061400, 458683657, 554643085, 808514618, 645057227,
     522533309, 516214517, 868458658, 29319863,  400991785, 44371424,
     393484315, 193195533, 313304061, 178336023, 872140660, 80223022,
     210186128, 697149973, 33593098,  613030339, 229650685, 175964311,
     836128842, 364498573, 855267772, 681464855, 362548980, 794257064,
     335344403, 876775590, 118192193, 395649039, 987209847, 384779418,
     908963693, 228748931, 622276243, 400134014, 621408233, 357897548,
     898874530, 710279704, 647865527, 984044178, 594410886, 118001153,
     808302197, 958614027, 989385555, 137636506, 116471863, 125693949,
     381922370, 34167548,  54240502,  638044978, 376865151, 13977046,
     723201793, 543703834, 987175535, 210723689, 702667571, 745004195,
     469531702, 830925780, 873651591, 705860548, 756193598, 826144042,
     2997110,   193251056, 956220899, 355406920, 786380459, 563345495,
     720553076, 157186151, 931531065, 57662174,  934997354, 377446286,
     364547930, 816724305, 288920240, 732500159, 596937423, 173734352,
     388215747, 222127782, 703866977, 732539196, 832180791, 765928231,
     401534122, 814997869, 503324438, 300789884, 848128215, 368400526,
     663480228, 949390482, 172477621, 100638102, 532776965, 135054793,
     643064407, 451081042, 937638300, 807581967, 57737080,  777807006,
     639941255, 253363108, 419956957, 771104642, 545411131, 250247612,
     478368860, 104077807, 336935951, 732349710, 812342536, 485914251,
     267663871, 336743490, 298929614, 627335614, 174719802, 233412706,
     237879547, 719636137, 663563046, 458183531, 330301618, 944549005,
     650572796, 379365515, 476498206, 243230182, 331013739, 761164865,
     790026047, 799228417, 483101303, 48053930,  619850811, 562174634,
     33643495,  913837589, 234151380, 99292577,  164010312, 113516300,
     5593632,   276051956, 268298886, 985148583, 663935070, 295325612,
     830025446, 315705549, 391043573, 952130787, 870475959, 429881763,
     470226567, 699505181, 44200252,  283132141, 979482423, 694973958,
     152722269, 779202012, 768443053, 782328503, 135949732, 642745517,
     907273054, 141269466, 781110105, 369261790, 29364236,  816735994,
     209885004, 259328396, 638454279, 755120857, 609806855, 482288073,
     712647856, 264154883, 22042356,  255540278, 905034959, 459459653,
     117472502, 811559263, 628342400, 692157363, 950816629, 80668464,
     131971483, 81723608,  191132241, 437332304, 844305210, 257002376,
     572797155, 879920106, 601755233, 557720527, 918691469, 680095834,
     581394753, 893478949, 183034409, 104187795, 50461297,  147374733,
     968367870, 48528461,  69638933,  519009167, 88871661,  16623294,
     702138472, 16026928,  743483596, 197705010, 441850011, 810959145,
     524951842, 864844924, 707015343, 174891846, 790359540, 964271948,
     725703496, 855521056, 295521874, 972959023, 956683352, 708871568,
     61609058,  379619985, 650095533, 602367432, 928459731, 129101316,
     826730488, 66174009,  852301132, 708590293, 44759254,  372035596,
     106739830, 49644693,  215828889, 905601060, 342751466, 33739775,
     168761009, 407210883, 748855153, 269858583, 93988347,  703488327,
     60916384,  773837538, 810505559, 10076694,  497088694, 711075489,
     370798734, 141273349, 929424610, 332505902, 579232980, 42189089,
     187704014, 839020536, 828834596},
    {0,   1,   0,   1,   1,   0,   1,   1,   0,   0,   2,   1,   0,   1,
     1,   1,   1,   0,   1,   1,   1,   1,   2,   0,   1,   2,   0,   1,
     2,   1,   0,   2,   1,   0,   2,   3,   1,   1,   1,   2,   1,   2,
     2,   1,   0,   1,   3,   1,   2,   2,   2,   1,   1,   1,   1,   4,
     4,   0,   3,   2,   0,   3,   1,   2,   1,   3,   2,   2,   1,   2,
     4,   3,   2,   3,   1,   1,   3,   3,   1,   4,   5,   2,   3,   1,
     3,   2,   3,   0,   4,   2,   3,   4,   3,   2,   4,   2,   3,   4,
     3,   1,   4,   6,   2,   3,   2,   5,   3,   3,   4,   4,   2,   3,
     4,   5,   1,   3,   5,   1,   3,   5,   6,   3,   3,   3,   4,   5,
     7,   5,   2,   4,   5,   2,   5,   6,   5,   1,   6,   6,   2,   7,
     6,   4,   3,   3,   4,   4,   5,   7,   4,   5,   3,   6,   5,   2,
     8,   8,   2,   4,   7,   4,   5,   10,  5,   7,   7,   2,   5,   5,
     6,   3,   7,   8,   5,   4,   5,   12,  7,   6,   8,   3,   1,   7,
     5,   4,   8,   9,   6,   7,   6,   5,   7,   11,  8,   6,   8,   6,
     6,   6,   2,   12,  10,  7,   7,   8,   5,   5,   11,  6,   7,   9,
     9,   7,   7,   7,   7,   6,   12,  8,   8,   5,   9,   8,   5,   8,
     9,   12,  11,  7,   7,   9,   10,  8,   13,  8,   8,   7,   10,  10,
     9,   8,   6,   14,  9,   8,   13,  10,  9,   8,   9,   9,   8,   12,
     9,   11,  8,   9,   13,  10,  7,   9,   12,  12,  9,   13,  6,   13,
     15,  9,   9,   12,  13,  11,  14,  12,  9,   10,  9,   10,  12,  13,
     16,  13,  9,   10,  13,  10,  17,  17,  5,   12,  19,  12,  12,  9,
     12,  11,  13,  7,   14,  11,  15,  15,  12,  15,  14,  8,   11,  15,
     18,  11,  19,  23,  10,  8,   12,  17,  12,  14,  14,  14,  11,  11,
     20,  20,  16,  14,  15,  13,  13,  19,  14,  16,  21,  11,  15,  20,
     13,  13,  13,  22,  12,  17,  16,  14,  17,  13,  15,  20,  12,  15,
     15,  18,  14,  17,  16,  17,  24,  20,  20,  16,  19,  18,  16,  13,
     20,  22,  17,  17,  14,  14,  20,  18,  20,  23,  17,  18,  19,  18,
     22,  24,  22,  21,  19,  15,  16,  25,  24,  12,  17,  23,  16,  19,
     23,  16,  22,  20,  23,  21,  17,  15,  22,  28,  23,  20,  16,  22,
     27,  24,  18,  25,  22,  12,  20,  30,  18,  23,  31,  21,  16,  27,
     25,  21,  23,  23,  23,  21,  27,  24,  26,  16,  29,  27,  18,  24,
     30,  17,  20,  33,  22,  26,  24,  29,  21,  18,  29,  26,  21,  30,
     26,  22,  18,  36,  32,  19,  30,  28,  20,  26,  25,  27,  25,  32,
     35,  25,  31,  15,  27,  30,  23,  32,  31,  28,  25,  27,  23,  34,
     41,  27,  28,  33,  28,  22,  22,  36,  29,  33,  35,  31,  26,  25,
     32,  36,  27,  23,  36,  23,  36,  33,  26,  27,  41,  36,  28,  32,
     28,  28,  36,  28,  27,  30,  36,  34,  34,  29,  33,  39,  41,  37,
     30,  34,  29,  31,  31,  29,  30,  43,  42,  28,  32,  31,  34,  34,
     41,  37,  28,  35,  42,  35,  38,  43,  35,  40,  43,  37,  36,  37,
     39,  31,  36,  29,  40,  37,  27,  49,  41,  42,  37,  38,  28,  32,
     39,  51,  43,  39,  35,  37,  38,  46,  40,  47,  39,  32,  37,  34,
     41,  38,  44,  51,  39,  34,  37,  51,  40,  42,  55,  39,  38,  46,
     33,  39,  47,  41,  42,  45,  45,  44,  47,  45,  52,  43,  38,  45,
     38,  43,  45,  60,  44,  41,  52,  46,  50,  50,  53,  34,  42,  46,
     58,  43,  30,  51,  49,  38,  62,  51,  39,  44,  59,  37,  44,  57,
     46,  43,  60,  46,  51,  59,  55,  47,  45,  43,  55,  60,  45,  51,
     46,  44,  40,  53,  55,  51,  62,  57,  43,  52,  58,  52,  56,  59,
     56,  57,  54,  53,  55,  42,  57,  59,  49,  65,  56,  52,  45,  62,
     60,  54,  59,  59,  57,  58,  56,  55,  51,  63,  54,  55,  52,  60,
     66,  57,  55,  57,  63,  65,  59,  51,  44,  73,  63,  56,  66,  52,
     61,  66,  63,  65,  61,  58,  66,  61,  60,  62,  60,  48,  60,  69,
     66,  66,  71,  53,  59,  64,  65,  78,  77,  52,  59,  71,  67,  65,
     75,  71,  59,  69,  69,  55,  66,  77,  70,  73,  72,  65,  59,  54,
     73,  63,  72,  81,  74,  65,  62,  72,  70,  75,  76,  66,  67,  66,
     74,  80,  72,  69,  72,  67,  70,  70,  79,  69,  74,  78,  60,  82,
     83,  78,  69,  73,  74,  73,  77,  73,  62,  82,  78,  76,  84,  67,
     75,  78,  81,  88,  77,  78,  66,  88,  76,  78,  91,  76,  81,  86,
     77,  78,  88,  75,  81,  72,  82,  91,  85,  85,  84,  84,  62,  89,
     90,  86,  75,  91,  71,  72,  91,  93,  92,  94,  91,  69,  85,  84,
     94,  87,  79,  95,  96,  81,  90,  80,  76,  84,  105, 85,  90,  97,
     92,  94,  84,  89,  85,  91,  81,  102, 87,  66,  106, 109, 83,  88,
     95,  89,  91,  100, 90,  86,  99,  104, 94,  82,  92,  99,  110, 107,
     103, 93,  81,  103, 107, 88,  104, 111, 93,  82,  102, 98,  90,  128,
     98,  77,  97,  109, 98,  103, 100, 94,  107, 109, 98,  112, 91,  113,
     119, 95,  95,  104, 112, 82,  128, 123, 98,  105, 116, 97,  92,  111,
     106, 101, 112, 106, 105, 99,  113, 120, 106, 114, 113, 108, 109, 98,
     109, 100, 116, 112, 107, 113, 97,  127, 120, 114, 129, 108, 111, 103,
     120, 109, 128, 126, 104, 106, 118, 108, 121, 125, 112, 112, 120, 121,
     138, 122, 103, 124, 126, 116, 110, 139, 114, 116, 130, 109, 111, 127,
     130, 127, 117, 134, 124, 112, 121, 132, 145, 126, 119, 134, 99,  113,
     137, 146, 131, 135, 132, 112, 114, 133, 138, 133, 149, 130, 116, 117,
     121, 142, 131, 139, 138, 114, 116, 145, 121, 126, 147, 148, 127, 130,
     132, 123, 143, 156, 148, 135, 132, 141, 133, 118, 136, 150, 127, 138,
     164, 129, 136, 148, 151, 137, 150, 140, 137, 151, 147, 139, 125, 142,
     155, 140, 135, 148, 145, 137, 147, 154, 149, 157, 164, 141, 139, 153,
     161, 150, 163, 142, 142, 145, 139, 158, 160, 127, 159, 172, 141, 144,
     167, 142, 143, 179, 134, 148, 169, 169, 151, 153, 160, 145, 163, 153,
     158, 155, 148, 185, 165, 151, 154, 162, 155, 146, 163, 168, 158, 181,
     164, 153, 157, 154, 153, 177, 174, 159, 184, 160, 153, 178, 173, 187,
     188, 166, 148, 164, 183, 168, 182, 163, 162, 167, 163, 166, 160, 181,
     181, 192, 173, 168, 176, 143, 179, 197, 176, 175, 185, 186, 165, 186,
     170, 178, 192, 198, 174, 177, 180, 171, 190, 177, 194, 189, 185, 175,
     180, 166, 200, 188, 188, 173, 190, 188, 184, 188, 176, 179, 206, 188,
     182, 185, 184, 197, 196, 201, 171, 207, 159, 209, 211, 179, 178, 203,
     216, 177, 211, 187, 186, 197, 224, 205, 188, 193, 193, 194, 192, 202,
     208, 191, 195, 233, 196, 203, 214, 192, 191, 220, 218, 180, 203, 223,
     202, 214, 214, 212, 177, 201, 220, 222, 207, 199, 221, 197, 207, 224,
     209, 224, 224, 218, 215, 184, 203, 224, 227, 233, 233, 203, 193, 225,
     225, 212, 224, 249, 233, 204, 211, 212, 218, 236, 245, 222, 216, 215,
     236, 227, 190, 221, 239, 220, 211, 234, 219, 219, 261, 238, 217, 230,
     236, 225, 231, 217, 240, 235, 240, 248, 227, 223, 234, 254, 227, 214,
     251, 231, 244, 263, 221, 226, 265, 263, 246, 234, 240, 219, 237, 239,
     248, 256, 251, 239, 238, 219, 227, 259, 247, 255, 277, 250, 243, 257,
     246, 253, 240, 285, 260, 245, 253, 236, 245, 252, 257, 263, 249, 261,
     270, 236, 250, 269, 260, 271, 295, 254, 255, 293, 252, 249, 261, 244,
     264, 276, 246, 274, 265, 262, 276, 293, 254, 250, 270, 270, 261, 269,
     266, 264, 301, 281, 266, 253, 273, 276, 275, 275, 274, 269, 263, 306,
     270, 279, 269, 308, 297, 266, 299, 279, 282, 293, 254, 275, 306, 263,
     289, 307, 278, 276, 321, 287, 264, 305, 285, 283, 302, 288, 280, 286,
     299, 282, 288, 293, 285, 320, 296, 288, 298, 306, 287, 324, 291, 299,
     332, 302, 291, 320, 317, 285, 321, 289, 312, 300, 291, 279, 316, 314,
     327, 334, 319, 308, 301, 312, 321, 305, 313, 288, 306, 311, 301, 306,
     336, 330, 321, 328, 310, 293, 308, 324, 355, 340, 307, 337, 307, 329,
     361, 312, 301, 351, 304, 304, 326, 319, 326, 350, 334, 315, 328, 339,
     340, 337, 324, 341, 342, 327, 361, 340, 316, 338, 369, 357, 316, 348,
     358, 303, 348, 334, 324, 354, 366, 350, 324, 342, 324, 349, 346, 353,
     371, 351, 365, 386, 345, 320, 360, 356, 320, 354, 360, 348, 365, 362,
     377, 352, 363, 383, 349, 346, 357, 367, 374, 367, 385, 349, 360, 414,
     373, 345, 359, 412, 358, 340, 382, 364, 364, 343, 392, 380, 350, 388,
     373, 360, 383, 407, 360, 361, 394, 406, 368, 394, 398, 368, 380, 360,
     392, 387, 381, 389, 401, 381, 377, 396, 372, 366, 413, 435, 393, 381,
     418, 373, 410, 416, 375, 385, 407, 416, 419, 348, 394, 429, 373, 427,
     415, 383, 389, 435, 410, 373, 399, 420, 392, 438, 436, 407, 389, 428,
     437, 389, 395, 421, 436, 388, 401, 446, 414, 413, 422, 406, 393, 446,
     434, 424, 446, 459, 419, 413, 414, 423, 444, 438, 483, 449, 377, 428,
     448, 413, 448, 463, 427, 406, 453, 437, 421, 454, 442, 433, 471, 401,
     438, 475, 417, 455, 455, 440, 445, 472, 443, 428, 463, 471, 425, 445,
     463, 429, 471, 463, 449, 455, 460, 481, 462, 462, 489, 479, 454, 435,
     456, 445, 465, 484, 461, 463, 446, 465, 465, 501, 475, 443, 474, 474,
     464, 515, 462, 455, 514, 452, 487, 487, 480, 457, 535, 483, 448, 464,
     480, 492, 510, 457, 484, 500, 506, 488, 508, 487, 464, 541, 503, 493,
     493, 492, 474, 515, 487, 453, 496, 553, 497, 517, 515, 485, 502, 479,
     515, 517, 489, 542, 564, 489, 499, 562, 553, 482, 507, 506, 498, 528,
     552, 509, 480, 521, 534, 521, 510, 544, 506, 534, 524, 535, 513, 541,
     534, 555, 504, 555, 542, 549, 577, 527, 502, 517, 524, 514, 549, 496,
     572, 568, 527, 546, 576, 534, 554, 593, 522, 537, 583, 555, 497, 582,
     568, 549, 560, 561, 542, 543, 578, 579, 574, 536, 527, 538, 566, 544,
     585, 575, 538, 589, 583, 533, 600, 596, 592, 620, 544, 543, 568, 585,
     591, 587, 559, 602, 583, 573, 560, 601, 555, 591, 629, 567, 557, 589,
     620, 569, 611, 631, 607, 607, 630, 560, 588, 598, 613, 603, 598, 580,
     622, 581, 570, 631, 608, 600, 639, 614, 584, 605, 656, 613, 623, 598,
     608, 632, 614, 626, 609, 590, 646, 661, 616, 606, 650, 595, 590, 649,
     647, 616, 632, 672, 630, 600, 674, 640, 620, 656, 614, 631, 619, 665,
     679, 644, 634, 681, 652, 607, 663, 644, 623, 643, 661, 649, 630, 677,
     641, 626, 673, 689, 690, 663, 664, 652, 615, 682, 693, 657, 627, 676,
     686, 660, 685, 683, 703, 630, 671, 691, 655, 663, 685, 721, 687, 679,
     715, 659, 680, 745, 661, 672, 735, 710, 642, 688, 691, 688, 719, 691,
     695, 693, 696, 742, 723, 689, 682, 725, 696, 679, 743, 678, 698, 758,
     728, 689, 744, 710, 701, 735, 708, 688, 737, 733, 715, 734, 666, 723,
     775, 776, 714, 734, 711, 704, 738, 763, 694, 752, 769, 740, 704, 724,
     760, 747, 779, 731, 762, 716, 730, 747, 761, 716, 777, 757, 759, 782,
     758, 764, 794, 764, 706, 764, 746, 793, 767, 740, 771, 794, 728, 783,
     779, 772, 749, 801, 755, 749, 827, 784, 786, 782, 776, 738, 846, 813,
     785, 781, 819, 752, 742, 805, 775, 785, 809, 809, 824, 798, 776, 825,
     795, 811, 822, 809, 771, 828, 806, 801, 821, 816, 833, 848, 773, 819,
     833, 812, 833, 830, 823, 818, 863, 806, 794, 846}};
signed main() {
  fast_io();
  for (int i = 0; i < mx; ++i) {
    for (int j = 0; j < mx; ++j) {
      if (j > 0 && j <= i) {
        dp0[i][j] = (dp0[i][j - 1] + dp0[i - j][j]) % MOD;
      }
      if (j > i) {
        dp0[i][j] = dp0[i][i];
      }
      if (i == 0 && j == 0) {
        dp0[i][j] = 1;
      }
      if (i && j == 0) {
        dp0[i][j] = 0;
      }
    }
  }
  cin >> n >> k;
  if (k == 1) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
      sum = (sum + dp0[i][i]) % MOD;
    }
    cout << sum << endl;
  }
  if (k >= 4) {
    int res = 0;
    for (auto v : vectors) {
      if (flex(v) >= k) {
        res++;
      }
    }
    cout << res << endl;
  }
  if (k == 2 || k == 3) {
    int pos = k - 2;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans = (ans + ans23[pos][i]) % MOD;
    }
    cout << ans << endl;
  }
}