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;
ll mod = 998244353;
ll gcd(ll a, ll b) {
  if (a == 0 or b == 0) return a + b;
  return gcd(b, a % b);
}
ll sum(ll a, ll b) { return (a + b) % mod; }
ll sub(ll a, ll b) { return (a - b) % mod; }
ll mul(ll a, ll b) { return a * b % mod; }
ll pew(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) res = mul(res, a);
    a = mul(a, a);
  }
  return res;
}
long double PI = acos(-1);
void fft(vector<complex<double>> &a, bool invert) {
  int n = (int)a.size();
  if (n == 1) return;
  vector<complex<double>> a0(n / 2), a1(n / 2);
  for (int i = 0, j = 0; i < n; i += 2, ++j) {
    a0[j] = a[i];
    a1[j] = a[i + 1];
  }
  fft(a0, invert);
  fft(a1, invert);
  double ang = 2 * PI / n * (invert ? -1 : 1);
  complex<double> w(1), wn(cos(ang), sin(ang));
  for (int i = 0; i < n / 2; ++i) {
    a[i] = a0[i] + w * a1[i];
    a[i + n / 2] = a0[i] - w * a1[i];
    if (invert) a[i] /= 2, a[i + n / 2] /= 2;
    w *= wn;
  }
}
int parent[100001];
int rnk[100001];
void make_set(int v) {
  parent[v] = v;
  rnk[v] = 0;
}
int find_set(int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rnk[a] < rnk[b]) swap(a, b);
    parent[b] = a;
    if (rnk[a] == rnk[b]) ++rnk[a];
  }
}
int t[4000001];
void push(int v) {
  if (t[v] != -1) {
    t[v * 2] = t[v * 2 + 1] = t[v];
    t[v] = -1;
  }
}
void update(int v, int tl, int tr, int l, int r, int color) {
  if (l > r) return;
  if (l == tl && tr == r)
    t[v] = color;
  else {
    push(v);
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), color);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, color);
  }
}
int get(int v, int tl, int tr, int pos) {
  if (tl == tr) return t[v];
  push(v);
  int tm = (tl + tr) / 2;
  if (pos <= tm)
    return get(v * 2, tl, tm, pos);
  else
    return get(v * 2 + 1, tm + 1, tr, pos);
}
ll ans = 0;
int n;
int N = 20000;
int check(vector<int> &kek, int k) {
  int sum = 0;
  int M = kek.size();
  for (int i = 0; i < M; i++) {
    sum += kek[i];
  }
  if (sum > n) return 0;
  if (k == 1) return 1;
  vector<int> keks;
  int curnum = M;
  while (!kek.empty()) {
    while (kek.back()) {
      keks.push_back(curnum);
      kek.back()--;
    }
    curnum--;
    kek.pop_back();
  }
  return check(keks, k - 1);
}
void rec(vector<int> kek, int maxnum, int k) {
  if (maxnum == 0) return;
  kek.push_back(maxnum);
  vector<int> keks = kek;
  if (check(keks, k)) {
    ans++;
    rec(kek, maxnum, k);
  }
  kek.pop_back();
  rec(kek, maxnum - 1, k);
}
int main() {
  int k;
  cin >> n >> k;
  vector<int> kek;
  if (k == 1) {
    vector<vector<ll>> dp(n + 1);
    for (int i = 0; i < n + 1; i++) {
      dp[i].resize(n + 1);
    }
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= n; j++) {
        dp[i + 1][j] = dp[i][j];
        if (j >= i + 1)
          dp[i + 1][j] = (dp[i + 1][j - i - 1] + dp[i + 1][j]) % mod;
      }
    }
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
      sum = (sum + dp[i][i]) % mod;
    }
    cout << sum << endl;
    return 0;
  }
  if (k == 2) {
    vector<ll> ans = {
        1,         2,         4,         6,         8,         12,
        16,        20,        26,        33,        40,        50,
        61,        72,        87,        104,       121,       143,
        167,       192,       224,       259,       295,       339,
        387,       437,       497,       563,       631,       712,
        801,       893,       1000,      1117,      1238,      1379,
        1532,      1691,      1872,      2069,      2274,      2507,
        2759,      3021,      3316,      3636,      3968,      4340,
        4741,      5158,      5623,      6124,      6644,      7219,
        7838,      8483,      9193,      9956,      10749,     11618,
        12551,     13522,     14581,     15715,     16895,     18181,
        19555,     20985,     22534,     24188,     25910,     27773,
        29758,     31823,     34048,     36420,     38887,     41541,
        44362,     47296,     50445,     53790,     57268,     60992,
        64941,     69050,     73441,     78093,     82928,     88085,
        93545,     99221,     105264,    111654,    118292,    125351,
        132808,    140555,    148775,    157451,    166464,    176017,
        186088,    196547,    207613,    219275,    231383,    244181,
        257649,    271629,    286389,    301915,    318025,    335013,
        352863,    371385,    390894,    411381,    432628,    454985,
        478448,    502781,    528357,    555175,    582975,    612175,
        642773,    674488,    707762,    742604,    778710,    816566,
        856180,    897219,    940204,    985166,    1031733,   1080475,
        1131419,   1184169,   1239342,   1296983,   1356651,   1419012,
        1484114,   1551500,   1621879,   1695319,   1771308,   1850620,
        1933336,   2018911,   2108169,   2201208,   2297430,   2397746,
        2502260,   2610330,   2722917,   2840156,   2961358,   3087567,
        3218928,   3354697,   3495983,   3642979,   3794876,   3952872,
        4117166,   4286898,   4463357,   4646781,   4836231,   5033091,
        5237619,   5448835,   5668212,   5896052,   6131274,   6375467,
        6628978,   6890664,   7162208,   7444003,   7734806,   8036449,
        8349358,   8672217,   9006953,   9354056,   9712125,   10083238,
        10467918,  10864668,  11275687,  11701596,  12140784,  12595614,
        13066740,  13552450,  14055271,  14575951,  15112644,  15668044,
        16242956,  16835452,  17448387,  18082666,  18736202,  19412048,
        20111207,  20831484,  21576103,  22346166,  23139309,  23959014,
        24806474,  25679197,  26580844,  27512739,  28472234,  29463255,
        30487223,  31541332,  32629717,  33753992,  34911161,  36105636,
        37339129,  38608483,  39918386,  41270741,  42662175,  44097665,
        45579240,  47103389,  48675380,  50297444,  51965815,  53686096,
        55460717,  57285728,  59167038,  61107291,  63102267,  65158298,
        67278236,  69457647,  71703173,  74017922,  76397220,  78848152,
        81374045,  83969977,  86643390,  89397957,  92228464,  95142826,
        98144942,  101229335, 104404384, 107674355, 111033430, 114490480,
        118050050, 121706096, 125467978, 129340637, 133317637, 137408880,
        141619696, 145943379, 150390349, 154966353, 159664278, 164495221,
        169465334, 174567181, 179812402, 185207630, 190745063, 196437070,
        202290722, 208297832, 214471372, 220819046, 227332236, 234024685,
        240904568, 247962863, 255214063, 262667022, 270312228, 278164978,
        286234669, 294511456, 303011440, 311744736, 320700935, 329897028,
        339343848, 349030595, 358975121, 369189027, 379660902, 390409679,
        401447743, 412763223, 424375956, 436299202, 448520551, 461060995,
        473934631, 487128517, 500664632, 514558170, 528795598, 543400126,
        558387836, 573744623, 589494913, 605655980, 622213039, 639191823,
        656610611, 674454125, 692749413, 711516042, 730737958, 750443631,
        770653908, 791352191, 812568331, 834324553, 856603433, 879436517,
        902847437, 926818156, 951381682, 976563168, 4099492,   30514210,
        57589628,  85306270,  113700592, 142801114, 172587556, 203098326,
        234363569, 266362239, 299134671, 332713066, 367075477, 402264295,
        438313522, 475200581, 512969956, 551657858, 591240712, 631765230,
        673269807, 715730192, 759195328, 803705981, 849236828, 895839454,
        943557047, 992363494, 44068385,  95206229,  147505623, 201023388,
        255807958, 311831397, 369153064, 427824496, 487816780, 549192323,
        612005495, 676226453, 741920607, 809145738, 877870910, 948164773,
        21843859,  95365195,  170556386, 247481995, 326109113, 406513189,
        488762479, 572823307, 658774643, 746688724, 836530571, 928383195,
        24078565,  120069544, 218198520, 318546165, 421075572, 525877907,
        633038239, 742518685, 854414432, 968815614, 87438920,  206872986,
        328968347, 453684991, 581127521, 711396425, 844450483, 980399334,
        121104325, 263012188, 407993323, 556159472, 707467342, 862037082,
        21742139,  183027245, 347773661, 516105681, 687977935, 863522236,
        44625223,  227729465, 414728276, 605759711, 800776548, 1678892,
        205100749, 412749672, 624776404, 841334383, 64130169,  289810445,
        520292122, 755525204, 995674854, 242666962, 492939183, 748420053,
        11043951,  277248052, 548968795, 826394592, 111228413, 400148067,
        695107338, 996053224, 304938931, 618461754, 938323134, 266485705,
        599657542, 939539742, 288103949, 642069557, 4892619,   373288154,
        749254152, 134490686, 525722455, 924960250, 333903686, 749288499,
        174893693, 607151626, 49831640,  499704271, 958468342, 428149344,
        905531434, 394069384, 890533841, 398746834, 915140080, 443519432,
        980699729, 530135973, 90380014,  660018827, 242507025, 834655014,
        440333662, 57731445,  685428265, 327312793, 979818225, 646807015,
        326919230, 20100260,  724960464, 445426817, 179689898, 926376784,
        689434296, 467054085, 259635534, 67636119,  889248517, 728401249,
        583817590, 455447951, 343727870, 249159940, 171695795, 111790093,
        69969400,  46188140,  40920659,  54719059,  87539191,  139876752,
        212310215, 304798556, 417858551, 552096273, 707473286, 884529730,
        85655813,  307305317, 551796575, 819794852, 113024420, 428561753,
        768858470, 135642780, 526016294, 942464263, 386718944, 855908847,
        354308016, 878387151, 432324935, 15164771,  625137557, 266450752,
        936428957, 638576648, 371863954, 137165895, 932725142, 762810620,
        626582104, 524045397, 455989888, 423373102, 426207739, 465318068,
        541705191, 655390132, 807231226, 31756,     230309868, 500717009,
        812347797, 166996485, 562085284, 2271079,   484090662, 12028957,
        583770869, 202887175, 866881439, 580516117, 342105701, 152707995,
        13629947,  923199528, 886030181, 901732338, 970401427, 94942626,
        273271748, 507254806, 798088920, 149020450, 556662914, 25776488,
        554406495, 146205580, 798962253, 517814287, 301164405, 150367985,
        67122481,  51604520,  105225544, 229759217, 425401129, 693622328,
        38028387,  455325206, 948800819, 522142956, 173834135, 903714902,
        717312272, 613133632, 592841130, 658538957, 810513240, 52251704,
        382438497, 803142905, 317923380, 925559094, 629902187, 431076077,
        331469545, 331453737, 432983464, 638551309, 948559719, 366801210,
        892362877, 529191570, 277651498, 140454039, 118069315, 212705191,
        427186772, 762022350, 221265904, 804352933, 515341098, 354867194,
        326002123, 429335701, 667357683, 45025401,  559459081, 216762560,
        18516829,  963645586, 60112845,  306128641, 704175658, 258818528,
        970168275, 842515586, 877025705, 79229451,  446448992, 983481097,
        696012849, 583179154, 648143130, 895002193, 326462196, 942303951,
        750303778, 749720816, 943979940, 339280291, 933190768, 732785659,
        740935042, 958791609, 391816817, 43072438,  912026743, 7802752,
        330148788, 882123959, 669493206, 695721665, 962193014, 474835362,
        237326667, 251137633, 520604731, 53140084,  846792988, 909586559,
        247405746, 858394465, 750754246, 928855877, 396208736, 155935508,
        214407497, 573483969, 239992650, 218808848, 511899500, 126293510,
        67131540,  336498036, 939874412, 886191214, 177650056, 816439290,
        813532359, 171259380, 892032030, 987121993, 458989775, 312039446,
        554340064, 190247731, 224405547, 665205096, 517147203, 785129294,
        479629886, 601790312, 160278279, 162409722, 611239747, 515708618,
        883486988, 719553697, 31374085,  825237504, 109806327, 887570467,
        173980604, 967350997, 281007176, 122022905, 494166105, 407566421,
        871467145, 891594172, 476645036, 636292538, 376468640, 704456494,
        633884508, 169148844, 317878624, 94165522,  500877553, 549521545,
        252909642, 614147821, 645116879, 359128633, 759536828, 858615088,
        670184559, 199616008, 456076342, 455678262, 204061423, 710812730,
        992593907, 57087546,  910803590, 574489058, 52606119,  355629098,
        501385642, 496405940, 353385464, 89009754,  708372302, 228169324,
        662209601, 21192103,  315288343, 564234280, 775567459, 963495893,
        148434937, 334776318, 539020624, 780538691, 69369175,  417308184,
        846208357, 366507629, 990581601, 742800469, 630502657, 670176204,
        883460752, 281642801, 878320815, 699460721, 753282215, 59298265,
        637292389, 501224629, 667762630, 162827328, 993840757, 185191395,
        756677652, 723256070, 104759855, 923677983, 197251829, 940796077,
        186540668, 941745138, 233023941, 84833664,  510274075, 533249412,
        182755374, 470736496, 421922611, 66384957,  416687540, 498415967,
        342744454, 962890790, 387081216, 644128500, 751429220, 734618126,
        627204224, 445535459, 216193513, 972158798, 734015645, 527580220,
        388856310, 335680013, 396634600, 609039037, 991518091, 575471572,
        397817439, 478001526, 846754595, 545917246, 594031697, 24719103,
        875998610, 174324759, 947465042, 243725929, 81702509,  495640411,
        531883334, 213503574, 574243060, 662056959, 501005941, 127887212,
        588805121, 910618243, 133218512, 302672915, 446909595, 605461704,
        829682246, 148621598, 599731023, 239714015, 95269077,  208853774,
        635554991, 406788266, 564788163, 168367852, 246681986, 845318641,
        26866235,  818270692, 272033193, 445824164, 374957907, 108373769,
        707657978, 211289781, 666458813, 142263581, 671605576, 310523780,
        125163156, 153454167, 449806808, 86269708,  100576649, 549097486,
        506350884, 13458062,  127041193, 922419846, 445911578, 754478669,
        927830417, 12279270,  66937845,  174250656, 380587697, 750811208,
        370171231, 285167681, 562968847, 291743679, 519940080, 318868546,
        776183306, 945878146, 899972768, 730988366, 493251967, 261336543,
        130967404, 158658661, 421614882, 20628860,  12707152,  477790317,
        520088808, 200711955, 600650281, 827648657, 945239349, 40847139,
        220591941, 552275882, 126323616, 54387162,  405115528, 272052035,
        770724671, 974240641, 977600013, 902112079, 821919869, 835346437,
        69590627,  598193275, 526419836, 982245085, 49221025,  827385502,
        456150126, 16921020,  616907451, 398326125, 445792323, 872069933,
        822324071, 386269896, 678814317, 849983684, 992944578, 230169981,
        711427157, 536971647, 829928506, 750518734, 399187449, 903383119,
        430407721, 82787824,  992424335, 333898762, 211944724, 764822284,
        171031048, 539425950, 16528792,  779694449, 949037197, 672479592,
        136938780, 461677482, 801437079, 351137906, 234583322, 610007792,
        678772965, 571161944, 450799257, 523942404, 925747125, 827190849,
        441382441, 906768537, 401831311, 145013192, 281732848, 992923671,
        509575369, 978997834, 591775204, 581173314, 105347252, 355958340,
        577531072, 932256320, 621850941, 895346944, 922647312, 910475842,
        119628455, 720935779, 931602258, 20940476,  166152473, 589904096,
        570285841, 294629546, 989503045, 943810490, 351707939, 447451356,
        527518020, 793126563, 489942277, 920573674, 297045783, 867939978,
        951036135, 762396203, 562537736, 675979784, 328329691, 787050094,
        390700103, 369451959, 3251647,   636280362, 512284990, 916964169,
        210969211, 639650377, 503518932, 171271459, 898887147, 996751988,
        845467616, 711973387, 913290115, 844052807, 780688227, 52483577,
        63204205,  100842470, 503728417, 692194640, 962604635, 666222051,
        235036633, 974124668, 249765682, 504305588, 58887119,  284642544,
        643429173, 465817567, 136935902, 131604513, 790142952, 513821731,
        790845229, 975217570, 479466794, 807406769, 327066330, 460911231,
        732340725, 520339915, 262951627, 498388629, 618733374, 78085995,
        429958981, 81723308,  498661857, 257155539, 773271158, 532755233,
        126559258, 985171647, 611732006, 614114717, 441191760, 606969926,
        742019943, 310596392, 841573218, 987086186, 227214448, 107976234,
        300123439, 300122319, 673403661, 113468701, 130125453, 308793816,
        362830451, 821242729, 289945655, 501048357, 5034471,   421924217,
        512004582, 840798457, 53497858,  926994928, 52962706,  90139005,
        844955326, 925315273, 16383964,  944380288, 341068837, 908168052,
        506406384, 779798076, 459556610, 427694533, 353368869, 987446457,
        244502927, 810803066, 466331324, 148513544, 570134608, 534035904,
        8331858,   727841745, 522457414, 388330301, 88282946,  473067291,
        572997367, 176169365, 160177726, 585170342, 267045348, 111113539,
        209972873, 404631941, 630663703, 15891039,  425492102, 826177200,
        380139416, 981136230, 627883151, 514503794, 567660834, 813723420,
        486753687, 542032423, 39763648,  248006427, 156781620, 855861479,
        657153761, 579428577, 748208609, 513357387, 926846799, 152795869,
        576643268, 289867578, 487363763, 601905030, 756728477, 187431881,
        366486101, 455239552, 725775579, 698612632, 570785796, 653776272,
        513833449, 386619355, 624159464, 839830718, 310771890, 429004335,
        856331393, 910902020, 31211249,  923636103, 951992222, 597293686,
        620678214, 425964135, 539662322, 777393227, 587740380, 544135714,
        516412006, 997535359, 612646536, 285633265, 556964929, 101481071,
        898630281, 543086594, 755510445, 579659107, 655320976, 759276753,
        994142842, 55156240,  767950734, 302840365, 403193792, 955619908,
        192811148, 911465174, 60762306,  930597541, 384813423, 422834218,
        409401999, 261483656, 42655397,  185654679, 667497431, 616012872,
        535634024, 465236300, 595081431, 505128043, 297911065, 229838918,
        954863232, 644578393, 621616629, 619668809, 874269669, 781534711,
        155203568, 298544981, 679631588, 196363661, 223437561, 302960421,
        415707569, 13515608,  711111667, 579817498, 145367927, 102616550,
        608808893, 271169275, 863302053, 637904289, 278854856, 644436632,
        81821175,  355669397, 412926362, 694414611, 54964503,  523954378,
        645471547, 359968052, 788681183, 578339180, 757516980, 543668132,
        685352031, 307195916, 718443169, 779550867, 708487860, 914265514,
        368626240, 385746710, 477151865, 727231752, 554305063, 571809873,
        981656437, 307575381, 267724556, 186540228, 690769600, 613443344,
        401302903, 790721374, 727259790, 785195760, 815380773, 877456509,
        678366032, 184913442, 573962746, 688844774, 615590381, 655185331,
        787354778, 222573289, 385819653, 400649394, 601825283, 547114325,
        504156653, 937477029, 539450670, 725832509, 97920471,  479449229,
        445348233, 730594182, 304484480, 894786804, 382687354, 876560383,
        273561006, 592828975, 97930544,  845841741, 13489606,  9860998,
        68421312,  514040917, 917510780, 688308603, 308780830, 508891301,
        878693386, 66009142,  962612313, 349447869, 35423592,  87475629,
        471775284, 173657943, 432842386, 412943722, 273276422, 434735230,
        261832859, 94695322,  538414491, 165565660, 500216590, 340390443,
        466957742, 598423909, 725453495, 848234975, 881436172, 17384986,
        475986551, 377031529, 116313095, 146616970, 791369126, 660770759,
        442876658, 674063447, 181118811, 892086543, 567267306, 252434553,
        127166268, 173109099, 666299275, 44529020,  516739924, 597276795,
        981825180, 123700694, 771218496, 893689192, 186364740, 647026179,
        520412782, 750467161, 594401455, 576251690, 898939173, 82686046,
        938126856, 937708508, 866266355, 837669720, 592269847, 192098560,
        56599567,  205018788, 982166672, 126610968, 938619123, 60417736,
        543727449, 991858781, 341671185, 977129533, 805270389, 67427416,
        488407271, 285632388, 14676454,  750097623, 29649783,  728251065,
        284545139, 556536248, 757362815, 688661754, 547958159, 886920909,
        884824772, 86017887,  389554799, 362382452, 901387773, 271187862,
        429145282, 639559481, 533268963, 477399118, 109697280, 437009732,
        246573242, 558050899, 769525916, 95771306,  948310065, 128586186,
        284645364, 239433246, 197531416, 262176453, 669504156, 47035150,
        956016187, 65719535,  426811397, 82878087,  133507613, 78179433,
        442537803, 778649268, 40922458,  251593381, 425296807, 979895406,
        455498689, 336348140, 519375925, 69001416,  954861501, 568999861,
        509858687, 250808184, 681235443, 956325832, 62464217,  403147748,
        700827766, 466928140, 637554148, 515176398, 149795715, 22443053,
        30396022,  776517995, 304057563, 118663311, 392194212, 737923023,
        292227227, 807328628, 486366474, 105656841, 18213417,  27146017,
        568185794, 610861760, 575485082, 574289279, 205540203, 522752620,
        333270567, 879011810, 868278398, 815981806, 629348113, 681343498,
        217569422, 822853626, 558777805, 414816215, 675983147, 105119088,
        456129819, 732440196, 415776134, 47436640,  362356034, 581767393,
        53878908,  265868162, 197087158, 19715774,  994283891, 879601062,
        692140281, 487561921, 816836420, 567642642, 607355689, 306514041,
        438405919, 706833065, 320929650, 963820865, 198423360, 88690196,
        255514716, 136230757, 678220326, 461778683, 820740133, 610412824,
        389074564, 415513953, 470181881, 119235685, 566285570, 544376546,
        648805630, 57411430,  472513135, 549839358, 460814473, 908922894,
        632604973, 822302676, 209497342, 637437945, 348203115, 120140171,
        935484533, 111328523, 499287897, 252518612, 781006347, 49191678,
        397551074, 369547591, 57602174,  29628582,  981866228, 172305602,
        419451595, 608755665, 183579945, 251157466, 910564423, 826106642,
        423353828, 47391678,  608297608, 884565347, 500283800, 646314918,
        483212749, 942783583, 533742331, 829699471, 109690883, 222547425,
        198046322, 687692016, 924422819, 424788175, 250113151, 46671996,
        852255937, 180806582, 123215899, 281116366, 646137554, 798974091,
        939664901, 580003018, 819694156, 499911123, 686681966, 44025974,
        86828623,  479361944, 482795682, 334082239, 331747923, 373923999,
        459103235, 562543041, 261299985, 357067424, 542958458, 116393997,
        725573864, 826163315, 476472589, 219872186, 312144263, 617781034,
        620954098, 426198734, 746432063, 53622136,  342557307, 225740431,
        205602345, 221155702, 823277998, 601212187, 480384464, 3535769,
        887816399, 102725500, 223963789, 159050633, 957392975, 291875829,
        301770979, 178251381, 728053808, 388998366, 538921108, 179429083,
        90842450,  896984163, 845866725, 122285137, 646599177, 966297568,
        728006335, 210666282, 313205620, 203101314, 571117110, 732363248,
        433621931, 836581792, 728542915, 497481491, 837532722, 68797065,
        281347647, 765049368, 431670062, 143738365, 844354663, 103557556,
        616285894, 52186140,  692847745, 146205666, 859772859, 908168103,
        866663048, 42575440,  356511459, 430929446, 493996760, 391715441,
        858619339, 120258044, 10774654,  456000940, 744986166, 779480405,
        750308184, 85974036,  821455289, 495322621, 747106472, 829809642,
        699519098, 291060249, 144604665, 718685165, 322228492, 861716848,
        385148203, 647733719, 11142634,  187678686, 471448817, 752910717,
        504844089, 638316867, 660145656, 887190178, 938205410, 22685276,
        389776982, 455169670, 216818093, 953907225, 966859160, 134545046,
        857012024, 414108695, 653238616, 200909244, 401726601, 175532403,
        462982324, 780720725, 211227999, 114449495, 274266061, 34860355,
        279450347, 162224033, 387607811, 470355417, 36014479,  254116262,
        376210714, 605592670, 685596838, 713699658, 579729932, 705253438,
        149500294, 596855417, 261947189, 275875218, 236676089, 258331666,
        666770221, 88077034,  649645173, 994703633, 891533801, 606738414,
        218132987, 757084516, 748798616, 834053130, 435907800, 454848061,
        225665108, 684348765, 240747497, 51017762,  696074989, 220363945,
        736578462, 606792767, 636112630, 38860062,  83231486,  476715801,
        669911334, 983215395, 163307065, 37203372,  117426394, 327612522,
        26518142,  60111240,  673141579, 902792264, 80512222,  916641064,
        282895284, 139918703, 821383558, 185688185, 979945249, 317045299,
        195576536, 313768729, 709417768, 698383262, 84918327,  993882020,
        224386598, 846662841, 248552502, 869960735, 229613930, 130244107,
        840523811, 490144985, 475944810, 72111343,  190112496, 170340,
        958784367, 949925569, 89317722,  205789585, 331483534, 713405904,
        747573452, 801813954, 441614579, 818479730, 832456776, 557414216,
        102873697, 91804879,  302528568, 6951786,   751955981, 223243330,
        55924757,  929576348, 637192543, 395141788, 223041477, 226038587,
        419289643, 377266189, 732673109, 520809215, 85910357,  806463433,
        963649584, 896936296, 954598470, 891351471, 270553404, 635101334,
        453581286, 742501526, 476757332, 75450402,  249184754, 637400501,
        859528283, 565150907, 299445750, 133382188, 899310419, 302600188,
        119353704, 622678142, 923468026, 773351888, 143508061, 806988289,
        758134418, 930612039, 33005788,  565782753, 700837546, 345657600,
        796738642, 736132589, 545470203, 603207283, 382769936, 24466838,
        277829946, 697786903, 470647192, 17813970,  268061582, 746430442,
        850508249, 189199847, 921549557, 735647740, 223317638, 490981509,
        827724999, 128410260, 755745874, 930465676, 165634029, 403513576,
        124905360, 788468406, 248407584, 578709202, 525013854, 177342297,
        556707812, 34961665,  278191847, 609205586, 372126098, 163907792,
        963136209, 447993159, 496047089, 117653547, 679828181, 713471676,
        629064912, 863216292, 962508869, 128274828, 241791128, 247384760,
        523436716, 791735602, 778639832, 444330549, 739656161, 571437254,
        887142803, 279942023, 233828457, 106060063, 535941826, 7924040,
        707429221, 751629473, 36517261,  17755331,  712729289, 865451558,
        646409217, 416607917, 200692067, 336641799, 979387316, 888416017,
        31441130,  812551235, 183568672, 212932908, 31424549,  241309553,
        500637949, 140847875, 895968732, 507531234, 989819307, 704222810,
        968377693, 990420049, 247715974, 154506580, 613966233, 731438735,
        544753645, 174851692, 867009055, 819581331, 900249795, 33976925,
        115700533, 306832774, 744165078, 590225935, 847228311, 421781113,
        303456866, 905212099, 464688273, 385135389, 66986870,  648381623,
        543616219, 726650628, 830838423, 881299720, 30430100,  553617,
        49082078,  118721011, 637730178, 726601839, 743225133, 447119252,
        463146180, 208385423, 406090433, 847940444, 660655236, 187362725,
        53963296,  760978639, 935870485, 727985672, 694013267, 421472410,
        278749113, 574270987, 548985657, 507424656, 218051871, 279660929,
        659280914, 311132094, 913499526, 843714904, 972816220, 801302355,
        867476364, 721533143, 431879083, 476638337, 848673933, 955413763,
        6814103,   222642992, 129999699, 472751165, 506490940, 675251949,
        84218479,  833073632, 104687862, 198676209, 902164536, 963080920,
        738674105, 550935311, 561012005, 59856346,  770931835, 143486216,
        284759565, 215939822, 548445724, 129434351, 171623440, 359327454,
        200103637, 30693880,  525191133, 802119744, 262077732, 511277081,
        246159994, 890493605};
    cout << ans[n - 1] << endl;
    return 0;
    vector<vector<vector<ll>>> dp(n + 1);
    for (int i = 0; i < n + 1; i++) {
      dp[i].resize(n + 1);
      for (int j = 0; j <= n; j++) {
        dp[i][j].resize(2);
      }
    }
    vector<ll> pref(n + 1);
    pref[0] = 0;
    dp[0][0][0] = 1;
    int cur = 1;
    int nxt = 0;
    for (int i = 1; i <= n; i++) {
      pref[i] = pref[i - 1];
      swap(cur, nxt);
      for (int res = 0; res <= n; res++) {
        for (int sum = 0; sum <= n; sum++) {
          dp[res][sum][nxt] = dp[res][sum][cur];
        }
      }
      for (int sum = 0; sum <= n - i; sum++) {
        for (int res = 0; res + sum + i <= n; res++) {
          dp[res + sum + i][sum + i][nxt] =
              (dp[res + sum + i][sum + i][nxt] + dp[res][sum][nxt]) % mod;
        }
      }
      for (int sum = 0; sum <= n; sum++) {
        pref[i] += dp[i][sum][nxt];
        pref[i] %= mod;
      }
      cout << pref[i] << ",";
    }
    return 0;
  }
  rec(kek, n, k);
  cout << ans << endl;
  return 0;
}