#include <bits/stdc++.h>
using namespace std;
const long long M = 1e9 + 7;
long long N = 4004;
const long long MOD = 1e9 + 7;
long long add(long long x, long long y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
long long mul(long long x, long long y) { return (x * y) % MOD; }
long long binpow(long long x, long long y) {
  if (y == 0ll) {
    return 1ll;
  }
  if (y == 1ll) {
    return x;
  }
  long long z = binpow(x, y / 2);
  z = mul(z, z);
  if (y % 2 == 0ll) {
    return z;
  }
  z = mul(z, x);
  return z;
}
long long inv(long long x) { return binpow(x, MOD - 2); }
long long divide(long long x, long long y) { return mul(x, inv(y)); }
vector<long long> fact(N, 0);
void precalc() {
  fact[0] = 1;
  for (int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
}
int C(int n, int k) { return divide(fact[n], mul(fact[k], fact[n - k])); }
void print(vector<long long> &a) {
  int n = a.size();
  for (int i = 0; i < 10; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}
vector<long long> bell = {
    1,         1,         2,         5,         15,        52,
    203,       877,       4140,      21147,     115975,    678570,
    4213597,   27644437,  190899322, 382958538, 480142077, 864869230,
    76801385,  742164233, 157873304, 812832668, 706900318, 546020311,
    173093227, 759867260, 200033042, 40680577,  159122123, 665114805,
    272358185, 365885605, 744733441, 692873095, 463056339, 828412002,
    817756178, 366396447, 683685664, 681586780, 840750853, 683889724,
    216039853, 954226396, 858087702, 540284076, 514254014, 647209774,
    900185117, 348985796, 609459762, 781824096, 756600466, 654591160,
    171792186, 748630189, 848074470, 75742990,  352494923, 278101098,
    462072300, 334907097, 10474572,  495625635, 586051441, 159996073,
    479379757, 707597945, 561063550, 974840072, 209152841, 906106015,
    467465396, 82034048,  392794164, 700950185, 344807921, 475335490,
    496881113, 358229039, 519104519, 784488542, 665151655, 307919717,
    591199688, 692769253, 335414677, 884560880, 847374378, 791103220,
    200350027, 485480275, 557337842, 434181960, 73976309,  792463021,
    462067202, 677783523, 295755371, 435431099, 193120002, 513369106,
    134597056, 143018012, 353529690, 591382993, 163160926, 287984994,
    842145354, 703798750, 386436223, 618375990, 636477101, 536261496,
    574800957, 34046224,  167415054, 961776342, 807141069, 218578541,
    513967253, 460200768, 230725907, 239843627, 792763805, 368353031,
    740982762, 126993201, 967654419, 588554507, 728057622, 239984996,
    818342358, 882367644, 216705655, 267152940, 867213913, 330735015,
    934583772, 59261085,  443816525, 568733052, 754405433, 244324432,
    153903806, 292097031, 557968620, 311976469, 242994387, 773037141,
    549999484, 243701468, 941251494, 7149216,   932327662, 456857477,
    739044033, 645452229, 69273749,  304951367, 503353209, 243194926,
    688663125, 239795364, 522687881, 121506491, 835250259, 159173149,
    545801717, 19848500,  322507013, 106069527, 807985703, 290163328,
    971751677, 238407093, 981758956, 301257197, 728003485, 817681690,
    318332431, 864806329, 87958605,  929106232, 617996713, 519300437,
    307911059, 137306007, 887695462, 633135243, 442387331, 730250437,
    27723819,  80605394,  760335262, 822289356, 415861662, 558003999,
    645049413, 347692428, 380668983, 897875109, 278111491, 106909073,
    951914124, 374756177, 635211535, 286442394, 774619548, 756991257,
    929298287, 923425488, 182439740, 266683608, 415378498, 728411148,
    808161291, 436338820, 692451577, 228029692, 235546564, 895805974,
    758052804, 700926159, 226442121, 579900323, 96916377,  243044550,
    858703179, 30279679,  343764928, 100627558, 840734795, 291199760,
    989808717, 370270411, 158336199, 393391701, 881731480, 507200370,
    588418523, 340981140, 295449954, 683858381, 903859151, 866470542,
    4959332,   237784075, 861373023, 950693473, 955867890, 400039807,
    939877954, 124824910, 954530940, 204884446, 42218442,  234856311,
    189836713, 179563650, 683193288, 929322036, 73574908,  943547254,
    103031032, 141180580, 540183111, 680050153, 382916846, 948921599,
    252835397, 199109508, 551172546, 700090782, 44999714,  970123610,
    145637563, 33948107,  267648423, 504777414, 584919509, 212459491,
    242880452, 351366578, 345323768, 285497541, 692868556, 706562675,
    675626979, 620872182, 136458675, 971105139, 182064384, 948539342,
    186406165, 706529481, 790490927, 888369436, 784409511, 835815713,
    447895018, 17015606,  342727699, 321837918, 394134115, 563672582,
    70390332,  61116103,  949269501, 833942074, 581389345, 570974405,
    768179852, 765734098, 928340756, 541194960, 126833304, 427218334,
    75800034,  100445725, 242810216, 330081440, 986329793, 298082322,
    643160582, 505669854, 255287400, 403977567, 659185446, 596703087,
    289443930, 478095124, 920175726, 205886838, 729278433, 535998256,
    658801091, 606948240, 432632296, 552723022, 17794080,  234033713,
    189986528, 444922724, 263196004, 846019724, 684703320, 895782046,
    505050988, 44287113,  505335732, 436498414, 12098144,  714227851,
    643983136, 647148160, 579243434, 951209063, 511291462, 426622734,
    830870687, 949900312, 599926584, 633837711, 176405710, 913717356,
    753535741, 874916804, 956692925, 220742732, 649500982, 584759931,
    109573948, 937203173, 96881033,  305784835, 559854872, 894253854,
    746366726, 951492991, 532579856, 822308583, 572042503, 397665465,
    600979983, 914199453, 628402767, 594763006, 9791558,   451332658,
    516069180, 651367831, 962708649, 687016963, 539878802, 107278296,
    926059014, 371504543, 556987417, 447666745, 565595310, 778161513,
    995461128, 121460302, 599892490, 242414970, 900391574, 362620950,
    292857964, 495260535, 355054738, 176340034, 370047225, 509682533,
    459314034, 40869728,  534741938, 788604648, 945028000, 701904601,
    154924404, 695162652, 220536827, 615701976, 167761915, 833779942,
    52430883,  368585637, 936409860, 654822736, 613850019, 941559844,
    357840989, 218223326, 721900618, 171013438, 597980462, 193395922,
    949112044, 859322955, 354602094, 807705992, 347609311, 451694117,
    623122523, 252980054, 491785682, 13877214,  918727309, 750110421,
    114981703, 174636266, 363160184, 781715298, 30575457,  862940854,
    642129450, 34525888,  798422280, 792396821, 168367459, 344551406,
    799847612, 626838494, 671596530, 167280197, 959000039, 614621296,
    273560655, 8705247,   284372524, 940371542, 906010703, 582585495,
    929449942, 308961449, 768816240, 674729787, 279648144, 286568146,
    938661138, 536038536, 456529723, 18843013,  501518651, 457224675,
    520694423, 938573228, 179014658, 169719825, 459657583, 302109678,
    560375405, 556039265, 348713003, 957546568, 687116649, 3656313,
    562760316, 716689588, 324677598, 570275686, 60738163,  996201577,
    305457565, 38935942,  538451492, 228282207, 77975017,  389525459,
    25000235,  152169430, 62331625,  618611219, 462328092, 106666757,
    661839198, 177836427, 313546124, 392585017, 950280707, 551167559,
    389204003, 77447456,  158414991, 766574847, 941433736, 363591676,
    805565034, 312418363, 999641612, 122925536, 768845786, 608121932,
    373163730, 783033644, 74564718,  894150080, 796617981, 274365270,
    802488053, 947861187, 401960309, 143529635, 769621671, 249500752,
    619408647, 849453216, 354838551, 69741157,  944781258, 135254314,
    7413076,   416298064, 871313316, 343673168, 375656287, 868866230,
    179060630, 399560227, 852555486, 987661859, 165863065, 12882359,
    3688778,   380092596, 438366086, 720041886, 240796679, 588918084,
    14802664,  17188673,  504951961, 842108931, 839289310, 256364811,
    121095676, 164017670, 35340476,  875551801, 239615760, 262141182,
    262741417, 456560451, 350350882, 777143297, 264469934, 807530935,
    89546104,  246698645, 241166716, 125659016, 839103323, 418357064,
    186866754, 179291319, 326054960, 172454707, 430532716, 558625738,
    306201933, 61986384,  837357643, 575407529, 983555480, 13784333,
    311989892, 153386582, 633092291, 722816631, 633510090, 551352594,
    323601313, 248995449, 672011813, 612805937, 202743586, 215183002,
    32688571,  38454892,  245790100, 451190956, 823199664, 12164578,
    67389319,  584760532, 968838901, 307205626, 971537038, 836812364,
    663878188, 468850566, 647599527, 839342879, 242347168, 169911213,
    993779953, 251402771, 969281106, 416168275, 738337745, 8172262,
    852101376, 879373674, 929752458, 452163141, 48347012,  500253327,
    672444134, 406391337, 665852222, 499704706, 116418822, 67956495,
    994761753, 808150613, 251453632, 543431315, 143101466, 381253760,
    826943616, 763270983, 959511676, 323777679, 514214633, 669340157,
    471626592, 557874503, 304789863, 116939617, 503636634, 660499296,
    659726735, 273788323, 704107733, 718417780, 624033370, 355000823,
    194537583, 760997582, 289828020, 778033293, 933152490, 910945024,
    644565086, 434509630, 289427510, 502291783, 421699389, 159196930,
    834667293, 313599675, 560298831, 812176354, 865521998, 126796474,
    886921339, 937011401, 791993161, 583948688, 275408655, 665183437,
    130342900, 699431744, 117550047, 460234251, 56770880,  306091228,
    912949106, 626369877, 852501236, 241076503, 262988042, 737247015,
    831044258, 475123008, 928949542, 332750699, 696284377, 689111142,
    196862045, 570365577, 187156806, 451528865, 635110126, 385331290,
    263486377, 200189955, 206842029, 457862597, 450522487, 818984909,
    710634976, 461356455, 71985964,  781500456, 467334209, 46762760,
    97663653,  870671823, 255977331, 79650379,  32876340,  636190780,
    364339752, 597149326, 452604321, 748186407, 302032725, 779013981,
    111971627, 175687535, 399961122, 451853028, 798326812, 902775588,
    362836436, 498862780, 160000437, 629259604, 919729986, 5994845,
    631476109, 371320167, 76164236,  448643023, 945220853, 111192011,
    150577654, 827274836, 17668451,  938388515, 88566735,  27940328,
    882026632, 712756966, 83642744,  873585716, 638987456, 405271094,
    822216133, 345587303, 668558160, 314983205, 826678060, 563583341,
    516998387, 77703032,  726563479, 155257773, 49705622,  891556456,
    164127879, 842558039, 189099480, 956148983, 992226557, 671472701,
    137476493, 871069222, 78241093,  728497057, 278888712, 332713952,
    222597908, 235198692, 876216003, 167364357, 722341150, 519365334,
    604855967, 834816722, 850786742, 416385106, 608404143, 311628039,
    507077268, 571796589, 506398832, 305540948, 556971113, 444565912,
    866477296, 411983920, 905854221, 901986568, 512703782, 684027511,
    596294441, 916862272, 495347444, 802477106, 235968146, 257527513,
    528476230, 969655767, 772044489, 682345813, 66418556,  603372280,
    439233253, 278244332, 590581374, 353687769, 321352820, 245676729,
    325255315, 91010070,  923699200, 837616604, 736177081, 528261400,
    876353388, 339195128, 377206087, 769944080, 772953529, 123785293,
    35984916,  461119619, 236140329, 884137913, 625494604, 791773064,
    661436140, 308509072, 54134926,  279367618, 51918421,  149844467,
    308119110, 948074070, 941738748, 890320056, 933243910, 430364344,
    903312966, 574904506, 56353560,  861112413, 440392450, 937276559,
    944662107, 599470900, 458887833, 962614595, 589151703, 997944986,
    642961512, 63773929,  737273926, 110546606, 654813100, 374632916,
    327432718, 307869727, 387738989, 133844439, 688886605, 989252194,
    303514517, 79062408,  79381603,  941446109, 189307316, 728764788,
    619946432, 359845738, 216171670, 690964059, 337106876, 762119224,
    226624101, 401879891, 47069454,  41411521,  429556898, 188042667,
    832342137, 770962364, 294422843, 991268380, 137519647, 903275202,
    115040918, 521250780, 783585266, 98267582,  337193737, 717487549,
    510794369, 206729333, 248526905, 412652544, 146948138, 103954760,
    132289464, 938042429, 185735408, 640754677, 315573450, 956487685,
    454822141, 783819416, 882547786, 976850791, 307258357, 929434429,
    832158433, 334518103, 700273615, 734048238, 48618988,  693477108,
    12561960,  598093056, 154072663, 174314067, 345548333, 479759833,
    658594149, 282072153, 57970886,  905112877, 584117466, 472359245,
    776860470, 324216896, 334199385, 321245477, 508188925, 521442872,
    286692969, 245141864, 59342176,  896413224, 573301289, 869453643,
    87399903,  60102262,  835514392, 493582549, 649986925, 576899388,
    20454903,  271374500, 589229956, 505139242, 789538901, 243337905,
    248443618, 39334644,  831631854, 541659849, 159802612, 524090232,
    855135628, 542520502, 967119953, 597294058, 465231251, 234577286,
    719052510, 789471692, 411491704, 668377891, 706834582, 422023943,
    792130239, 56910783,  349097771, 439515696, 582793988, 156362001,
    871022818, 158045277, 730259816, 559426958, 256915266, 329283283,
    697482888, 960391034, 123468695, 579143166, 327986560, 79631804,
    964001442, 653086198, 325933878, 489825670, 951221162, 253447532,
    918073506, 495882514, 437557069, 568958468, 878752857, 195186711,
    862939349, 147129230, 115349386, 700159857, 901914597, 465268401,
    965390262, 480684700, 912028983, 463482127, 140321226, 622996408,
    650138382, 875669593, 293215106, 870247261, 647509675, 191356165,
    394191128, 264457287, 22229755,  885646235, 701645436, 689404012,
    591670570, 853743454, 343300941, 378943326, 701554144, 156225357,
    2889895,   342055363, 509897179, 551690113, 367720364, 376094487,
    849019040, 439429817, 252052684, 73868483,  760418168, 346915118,
    920898843, 447178329, 385053562, 971326177, 51306779,  868878877,
    918456746, 907129483, 469300868, 116182130, 263397251, 880193364,
    525080002, 122871305, 806849644, 530429964, 847669634, 687541589,
    667011277, 118523931, 170573127, 639392716, 932978326, 774343957,
    207807859, 842923829, 540551499, 416145341, 510754496, 816754956,
    141636722, 23806651,  797052893, 280494679, 862829535, 594152581,
    255543303, 115355697, 175045725, 753843569, 723238162, 747819906,
    386991553, 128492007, 832023330, 744470732, 863287191, 680479465,
    130566353, 522384815, 948060953, 988598293, 251269107, 279172248,
    330642890, 181200913, 328948704, 246020831, 591010814, 153193674,
    653998011, 556727834, 698201487, 743237304, 352457449, 890844797,
    603241917, 157033196, 449941679, 638367564, 984812222, 177998527,
    2571553,   750042962, 530815355, 288367133, 461215488, 306469961,
    992599117, 777647122, 399661615, 272381646, 374837119, 242312039,
    161562546, 827703689, 416130810, 268500166, 714440725, 924015517,
    810481760, 456828202, 72636095,  869441169, 135478090, 577861476,
    965681815, 770306429, 828371948, 121495878, 318644526, 214238807,
    375317282, 562894926, 654880919, 524133599, 836560943, 585920630,
    997910416, 42528257,  728160105, 603551810, 828625420, 554409298,
    238464512, 177161223, 100273300, 196375686, 910350531, 998271395,
    89571704,  388544422, 710014768, 792862078, 613945077, 723008570,
    686703020, 22036201,  441451327, 873721233, 952341622, 208401207,
    715584375, 789944965, 266619033, 217395995, 773848269, 890384827,
    300797636, 380816274, 34903719,  678806492, 676280389, 289577112,
    105926126, 869766187, 148780908, 257383939, 219966442, 803001268,
    700100239, 210002874, 301574146, 157478049, 840543689, 686351647,
    314215877, 410846915, 937595078, 977587055, 278410396, 246162057,
    596680745, 648102814, 608559339, 984991657, 553308172, 698308340,
    597673022, 215493168, 637106249, 635651739, 996417162, 20600016,
    45948552,  145419282, 398624765, 886248008, 280688420, 990103967,
    373976190, 463758914, 783793500, 187773366, 224028141, 773609709,
    441552870, 199621056, 40675250,  623126900, 565714966, 335545822,
    159154993, 85804280,  812981639, 368861355, 263240192, 915786186,
    213839773, 740984710, 485869373, 498675063, 165824754, 290318079,
    268829808, 783651320, 140938011, 452184509, 663073463, 628576393,
    561374703, 77531765,  675767665, 219965958, 79658403,  107004356,
    726095143, 920360,    616856163, 322049704, 990876102, 28813501,
    479588212, 607362861, 460280414, 510630785, 175868273, 203301031,
    485282804, 286980722, 878779105, 75802674,  482160716, 276534454,
    573231888, 255171286, 17004257,  477221305, 993797117, 887907148,
    900621768, 281553637, 974877491, 662837174, 881584284, 143891298,
    788461099, 484372545, 234443352, 97386042,  189777871, 766423259,
    328443566, 335362850, 282264191, 79108999,  502600487, 66831947,
    971718237, 145123063, 700669169, 23599039,  235633035, 21658772,
    153187595, 708544325, 422877598, 625792818, 435465528, 861682463,
    587577924, 669558001, 869495722, 230312480, 591055605, 666486499,
    243050200, 473838909, 27804857,  462415564, 950758578, 82353145,
    781652464, 797013128, 92616240,  57731412,  892900687, 229089402,
    904936873, 28021044,  317392328, 490036476, 341291194, 295406868,
    504259794, 904545162, 177495104, 126802846, 533220218, 170328984,
    481957953, 536305139, 91399510,  852175302, 527902344, 87661066,
    498256033, 911769401, 573782791, 711777167, 299000091, 513337058,
    706321263, 160995082, 814524139, 525871668, 195621157, 738132050,
    522997791, 2434339,   704677890, 179392879, 463736985, 195948444,
    891566998, 443954734, 659925991, 686116169, 118001951, 702122944,
    894935402, 524221451, 870490275, 257812667, 353690750, 79038280,
    51842966,  172006600, 855368423, 443051385, 833006149, 793388156,
    45047516,  310749296, 55334141,  476038106, 789821303, 989259156,
    92410347,  952627287, 780501091, 521607848, 414474244, 732354620,
    383953563, 446473628, 47798390,  211676203, 955208289, 430733124,
    736382777, 372402479, 892472676, 106885144, 711152183, 345330469,
    113176297, 583546541, 989005026, 879834861, 485880880, 956976046,
    984532018, 52156620,  47648864,  369256591, 762990216, 321648688,
    942471724, 27988621,  375153599, 201826211, 552096241, 849164915,
    410476603, 769539074, 245294254, 109098731, 364713315, 114339783,
    455317652, 924912076, 137615956, 395117205, 557940960, 863964666,
    105090076, 247801074, 24385891,  675217117, 148233675, 237796036,
    267148517, 747252134, 159286828, 772859689, 833502336, 12089815,
    579434685, 660378688, 142383709, 364553928, 506871962, 63571691,
    436656533, 189644737, 4484522,   875871934, 496258534, 98322767,
    206512541, 908548828, 186809636, 418511401, 370060629, 996606436,
    442572716, 154923425, 655048065, 843219464, 519344828, 890739475,
    728038428, 667374443, 105405472, 292120352, 508232068, 694276070,
    275896293, 616495821, 717513444, 672047542, 667827609, 286709621,
    704857149, 471988636, 773414271, 187159700, 149544869, 138170870,
    275199585, 858826314, 233329181, 362574598, 146271226, 662515245,
    829216547, 225214790, 124306162, 309454143, 197474276, 411732530,
    242616829, 533844820, 134228075, 970933446, 121050937, 143853408,
    213411089, 88503415,  587297673, 956972957, 898645724, 144360772,
    495393279, 240440157, 48990349,  125071961, 372998637, 993591967,
    447818597, 572817648, 570422850, 879902545, 103408312, 134259907,
    930409822, 164624487, 863575259, 498058201, 155498663, 836184597,
    458766416, 930173542, 571538117, 11418714,  840080841, 550409715,
    404747438, 623701621, 932591967, 629475701, 333771046, 357527706,
    50349542,  809404172, 32680726,  849209271, 654679673, 976256182,
    483903197, 443666371, 402713876, 474069026, 341242805, 911892825,
    675361308, 130029471, 591252074, 361253837, 913522319, 278883270,
    43794963,  721032507, 161360783, 145910425, 405754709, 481016777,
    984160489, 822457748, 928311887, 130974820, 814330706, 177596547,
    733463623, 621380033, 387616190, 517385408, 777415503, 153714220,
    110237540, 9459485,   42997688,  960820193, 653534059, 922402599,
    402532770, 710802128, 748496037, 6962540,   307859858, 895756782,
    173853056, 365387768, 285351176, 850992797, 171012376, 50849689,
    959534160, 983404681, 462930073, 986727862, 351078980, 113001189,
    540455687, 812936681, 344829242, 636939290, 665237416, 829160482,
    973596376, 437524867, 316466374, 748561837, 622585657, 72315288,
    709519702, 535489757, 179411549, 14687103,  766718776, 724290113,
    509214591, 798686957, 807530292, 780437674, 108972011, 66354235,
    288836149, 800959762, 56647494,  378319675, 484934256, 634925922,
    118283138, 572458963, 317907676, 592543101, 905775554, 280439197,
    958195289, 590807218, 612877898, 952147555, 84603090,  423405775,
    141749054, 745201534, 444958373, 246984748, 877512200, 773663916,
    713230134, 971631558, 825024421, 705218938, 498046250, 901741714,
    11204058,  973762786, 108832572, 657975477, 641555020, 752370849,
    662157143, 844714372, 71560016,  272265622, 769825878, 963355137,
    271925609, 601872616, 791371246, 985365315, 883526650, 143820141,
    681544627, 844266906, 816285053, 966773693, 452262255, 249464970,
    77561862,  707304052, 929265371, 267800589, 849423016, 370900035,
    899540394, 496756946, 419245752, 150124480, 355379985, 829768917,
    819198320, 321308816, 995185058, 180983950, 83286465,  585095540,
    818161019, 174613777, 715687449, 562738802, 101523867, 964327160,
    374016629, 999296099, 512710137, 381205438, 711887867, 298639663,
    807093917, 426312452, 960211071, 301947471, 948009687, 37226626,
    56446923,  6020904,   661481230, 969721602, 665206397, 545945632,
    119445627, 350615105, 415266278, 450388738, 582376903, 127332755,
    897189927, 82583193,  969330803, 584493269, 474288141, 812261520,
    918866178, 305252256, 496593547, 375145972, 845005953, 16384264,
    18866120,  291452703, 123859568, 84188419,  420335331, 701389288,
    635765443, 282586280, 819530631, 184344737, 302086904, 549271705,
    110885458, 404203288, 873436087, 664527613, 618848752, 424389906,
    133964398, 32248933,  991819218, 674742116, 976617480, 696056191,
    975648361, 22512421,  380736722, 472796955, 145592824, 733308250,
    839860963, 928844916, 526271384, 823978116, 935386950, 13742315,
    129661749, 286343623, 26005094,  650424222, 436019622, 841150055,
    847904089, 585813828, 866928172, 640895240, 927092785, 234673913,
    790416262, 601132552, 286508434, 37434388,  458552446, 225861108,
    938954209, 179547110, 623374115, 336961349, 778335347, 120759871,
    546685885, 169450333, 117137956, 907333492, 697929695, 73324777,
    5546281,   31038646,  272708278, 879099648, 725361184, 643797655,
    381543156, 201948307, 905097895, 5083747,   864509297, 418729921,
    758799900, 71385907,  56612274,  584054216, 422628745, 963836513,
    247866986, 468338401, 429731689, 301064989, 964252649, 754708694,
    789609947, 325094454, 48041674,  762490068, 872064887, 891148606,
    111273850, 528877281, 505307258, 927529311, 827023136, 927027842,
    480792693, 898759590, 336125656, 525799954, 262312932, 42566148,
    156437685, 312663449, 869490710, 110170793, 611737225, 489302480,
    962027769, 69292153,  877615246, 933395086, 623382750, 952249866,
    449250872, 44137878,  377547991, 8734456,   849028671, 689297867,
    880969148, 611297405, 699203445, 279063732, 985579869, 361286737,
    574192554, 210756284, 582330472, 687115287, 346797527, 68379989,
    367272674, 922968317, 923358181, 114269570, 643568783, 54463451,
    387194025, 448687201, 183771730, 508104225, 443537201, 16323128,
    434151553, 970819813, 254326763, 435712770, 366483023, 408137530,
    805502289, 467214548, 424919102, 892285776, 873646206, 416987903,
    259930584, 326240034, 983819250, 434558165, 163789709, 528191397,
    421000628, 742256219, 723869231, 905947997, 193529900, 451441953,
    664004027, 437922126, 29916435,  892121538, 122323150, 325806901,
    879829857, 669394967, 598444309, 424679948, 81290040,  463345756,
    781983914, 563036786, 484150060, 639468002, 313191411, 180413287,
    247502799, 528925528, 575480041, 635027335, 256975213, 912107856,
    494502312, 441723047, 683852309, 990247207, 92438089,  476487459,
    501906050, 463868265, 884062263, 124480261, 845159716, 789710443,
    527998839, 603629355, 145811239, 533233891, 588584475, 563430691,
    591671108, 370981332, 756530935, 80379648,  484171072, 175010221,
    373865064, 191818129, 464489510, 929000671, 391717125, 747091853,
    439867887, 903187939, 60434199,  688760991, 940581714, 174982608,
    664591196, 809151381, 512077202, 296167992, 253587796, 909751994,
    870392927, 50596757,  147012264, 145592173, 608048527, 790444659,
    695034282, 425391314, 566706,    238458278, 556740782, 530945616,
    37163071,  887535641, 336847666, 574020737, 251493906, 561926332,
    79276934,  598441685, 292718605, 741701246, 806386665, 781362104,
    601715998, 722420070, 71607129,  765657095, 577043295, 110457871,
    73278570,  917286450, 582688793, 233972812, 773838073, 563827083,
    665183297, 276385337, 284554052, 773942585, 709884270, 219724769,
    802098221, 40314526,  670328543, 116354242, 8105772,   138315187,
    437875308, 414489825, 792924722, 367103146, 598235884, 590708626,
    500134923, 616512272, 778674544, 24323011,  574009545, 753151007,
    445226007, 168408056, 814317714, 828678983, 445766238, 667740615,
    220352863, 408445465, 164002975, 751771873, 242270577, 244789471,
    960125783, 577250843, 986752672, 134975013, 857262769, 365449378,
    893920171, 521472111, 420799038, 55200287,  382558852, 460995662,
    287489292, 972216032, 928724755, 820330965, 844857857, 479505444,
    127468827, 342360282, 538971087, 991812633, 347890429, 352213886,
    719725575, 711601768, 345059156, 723718410, 2412874,   673137480,
    106246833, 845542253, 54784761,  441554946, 992084156, 896406516,
    423823171, 237959509, 611071505, 976306302, 127377556, 813035294,
    866686778, 797851519, 891038077, 446861418, 558723079, 335240540,
    933421654, 552658325, 101044567, 701569567, 79619708,  113230746,
    18709190,  489414563, 794070733, 654683423, 737364094, 603190309,
    709749175, 964043164, 743384329, 61722307,  357502072, 765005005,
    822707526, 522366109, 182415702, 12257063,  892793242, 776663000,
    209356976, 316188695, 464233826, 518121285, 702595779, 847947529,
    882970001, 24006933,  286967513, 743911598, 859784525, 468644940,
    151255407, 266755785, 749315764, 871214347, 732746484, 498557477,
    378659343, 284143015, 191315738, 524459024, 285599248, 93571847,
    232447141, 651095775, 327322781, 926249193, 301563041, 16861825,
    312874690, 968199568, 324054125, 476106501, 987634072, 405576308,
    579381657, 124890361, 469844398, 504791549, 309708702, 847186504,
    599043886, 784070324, 134489423, 968500796, 535624525, 557985688,
    739059475, 282824172, 962974241, 673756999, 629288514, 602290478,
    272032130, 947687367, 458958305, 939540040, 555038128, 725720859,
    249129551, 70784066,  779816802, 32338884,  936893404, 590996290,
    722093366, 943395887, 870675690, 794167051, 880783877, 567985820,
    122740218, 1655312,   513185141, 556598680, 964463302, 80469754,
    320171951, 916790701, 833281585, 803013531, 724614577, 817147362,
    215545611, 669243037, 468222858, 43075712,  259747142, 560617179,
    557232222, 815295691, 469821555, 88839134,  234345180, 504538244,
    931222273, 316768673, 93980273,  45787668,  385011442, 7000216,
    276055907, 901541982, 263333020, 711644240, 672882808, 208436297,
    874853962, 319638303, 709012275, 766991341, 242486025, 901858138,
    25494048,  914909510, 490103036, 270682019, 56150061,  827555535,
    441238409, 568638315, 609478787, 43668184,  778841493, 253152410,
    234178145, 558425422, 116282946, 484472427, 896792258, 158785628,
    612324179, 855203574, 567081270, 136783738, 955558104, 935056189,
    535784910, 760076361, 686203275, 790667727, 647858777, 739583434,
    514020926, 126992398, 285502081, 656335212, 647425455, 33377104,
    953034122, 533751604, 341214710, 51670793,  224130859, 79086450,
    751898173, 815278055, 368308879, 879753575, 570758226, 530448720,
    311816932, 24499573,  385102108, 314279398, 823094070, 57424571,
    801802086, 649238305, 71828091,  22610945,  465622250, 634357293,
    250987906, 279815083, 399059669, 993491643, 764518066, 954449466,
    786784520, 7214491,   309348562, 967927912, 814966044, 398277161,
    145302827, 317133297, 555908849, 763209806, 713959725, 917219494,
    614866982, 743039617, 6642256,   191926249, 75564780,  402715373,
    438757202, 956548036, 88836445,  126738459, 148256690, 758649280,
    233870039, 618496251, 809592911, 4143797,   913788017, 867201282,
    838208226, 17995950,  926304169, 323062065, 147836722, 23987125,
    10273949,  318414676, 859196334, 785963456, 319241611, 41814946,
    97841520,  709446413, 819366149, 257049767, 457365516, 227964197,
    837685221, 538289909, 799856513, 966795605, 976754791, 178585858,
    773647150, 490152461, 338761936, 704848398, 751454546, 275917899,
    266521387, 379163892, 732553223, 468451968, 912252890, 353635318,
    325580773, 655087561, 66231223,  390508011, 709093080, 917609272,
    118217468, 342802338, 425495681, 210359565, 872062939, 114650850,
    798178048, 240314279, 461414970, 850135439, 678881360, 816005189,
    344526423, 545625731, 814858100, 282298848, 248261162, 441581677,
    613473579, 62751489,  33573817,  398948289, 990945304, 957428734,
    586423324, 374186675, 501817598, 451350729, 667813355, 230043968,
    430675019, 792996317, 514624055, 229390940, 191135921, 92904209,
    991467282, 756118622, 897899024, 86813518,  245048982, 128292209,
    304817237, 405182882, 719453056, 948320663, 716710140, 287983103,
    891632298, 470908467, 296100190, 863281789, 611713021, 526088214,
    378706769, 954194006, 547356546, 897702735, 776099604, 536261363,
    118236230, 77446392,  871928365, 712237602, 734212251, 530900683,
    264862566, 573128964, 269332327, 501953313, 731839605, 324552247,
    548793873, 732865174, 679223519, 153195583, 391080223, 137458334,
    111476085, 941570307, 599582551, 860117991, 24311430,  568378943,
    976453414, 93140555,  924998399, 797791391, 305274325, 933544108,
    966122171, 199072647, 554723613, 123210567, 237194670, 939649941,
    874393737, 68963050,  248387629, 921696393, 100076405, 553210,
    553123253, 383040408, 860520334, 542130950, 780888751, 804728977,
    530996929, 227054360, 801731642, 988113522, 23599213,  912821640,
    452000676, 273952452, 785650598, 957099748, 263587335, 191147876,
    369131002, 581437918, 75734722,  972440694, 949336980, 681719418,
    303142016, 282497467, 84697781,  656044124, 602133016, 542205342,
    67532450,  649765731, 327502924, 870829264, 157614729, 290634638,
    28895643,  756796380, 66928168,  908244149, 336235000, 798635646,
    531101996, 308603330, 965459608, 802063684, 630259662, 25285254,
    127977391, 731151666, 816996517, 5941805,   863406538, 534030846,
    760562334, 177298416, 74254907,  61946069,  701173267, 849123211,
    223920336, 402070982, 451070134, 290145526, 801137767, 361873174,
    226033212, 345711558, 976935938, 727275819, 657949261, 558334514,
    348442214, 92188878,  65931989,  884423257, 273776772, 82578780,
    21964812,  692310791, 421747940, 508956345, 829867055, 712216434,
    176263570, 238968707, 885589964, 2338761,   920235106, 44122910,
    32361391,  987895225, 198653318, 438724958, 821576158, 413646707,
    734510118, 694541860, 478236028, 871307989, 619578531, 583875161,
    538665108, 498234236, 109168946, 711366765, 383677711, 189350089,
    431386463, 405617925, 478935614, 186431243, 998817197, 151404153,
    870193461, 686428096, 703459265, 503264393, 571307514, 950023327,
    52020851,  422745802, 801945360, 920055073, 915984291, 347325376,
    98035239,  768254438, 950963903, 843326252, 776558676, 625359570,
    136688769, 938973757, 513573431, 218450925, 304988995, 255220477,
    170773124, 502830499, 706620213, 747086020, 19911621,  347253477,
    413125153, 150131943, 714133549, 831405303, 873772059, 433086939,
    505167849, 521500425, 39997099,  218457179, 141292841, 227146672,
    516991167, 631669176, 520404230, 157222018, 152022453, 786192855,
    867580315, 257431544, 642749792, 259184063, 423248728, 481776217,
    381066154, 161987227, 908479451, 229680706, 4607796,   335963167,
    659541556, 124330160, 563861103, 945052724, 252546645, 796966099,
    986082050, 874261765, 930288819, 330451071, 823023820, 393946353,
    443991161, 659431769, 598434736, 320551388, 826940781, 349722244,
    927104771, 902855425, 99775627,  210252064, 588340945, 190379481,
    33740332,  282387632, 302756352, 997374101, 68047725,  104398307,
    210353356, 835930466, 462528846, 257838917, 145554240, 495502023,
    182049010, 207210386, 332673437, 984949587, 646987066, 242536749,
    961166177, 743023397, 178108654, 533313586, 2523508,   123632073,
    920760453, 876215269, 694623347, 576910047, 13998909,  432579306,
    821994396, 188161473, 532239165, 398969517, 805882924, 572487140,
    324260878, 780110448, 998237225, 671389723, 217079591, 64156923,
    701874462, 402932050, 868969247, 250055006, 307603415, 902155269,
    432776345, 123649275, 43843299,  467745849, 427227918, 348782844,
    208429155, 939342091, 583928755, 24727360,  605633247, 506517137,
    134487038, 141711391, 852373938, 803417028, 981730834, 781218680,
    368454373, 731000220, 700286474, 535838839, 93732613,  806735582,
    444862454, 793071677, 404775345, 760935573, 234741359, 126536891,
    752651452, 274374188, 971026218, 714658459, 451790511, 985231339,
    672712756, 803040018, 510520992, 547998421, 286082520, 335454992,
    294741562, 198101705, 274996785, 919806186, 194403413, 368313678,
    793945588, 840134358, 497861696, 674089807, 486053576, 756708235,
    775885307, 753307778, 78059116,  530511749, 242555288, 720602980,
    668724632, 543930645, 759067502, 813824210, 518108164, 87623363,
    404803860, 601147669, 681300598, 912536592, 564743137, 425731312,
    765623182, 756271461, 802910224, 312059493, 853998841, 209903286,
    641228584, 998778463, 548722153, 23286197,  186002856, 149093256,
    796935817, 569560120, 939030507, 23065276,  615945246, 567464926,
    520594270, 609042093, 964853363, 227264175, 350138850, 675012989,
    102765593, 69280617,  158825574, 648868661, 163570693, 757437549,
    925804636, 570754867, 805613198, 926112760, 653862900, 954295487,
    312827086, 150778409, 706495883, 540114444, 289948046, 977757745,
    572076667, 954401054, 877219043, 630010040, 768113291, 261966834,
    334008263, 634421112, 445932311, 970883941, 415840474, 73583190,
    115547261, 230769726, 248921513, 752058877, 494518837, 784955440,
    76806346,  783891026, 629506235, 173700082, 12516760,  832882264,
    897704072, 856345120, 377590660, 3991684,   830913453, 206929253,
    230294838, 357503801, 579705509, 977384894, 681905980, 79909239,
    447541551, 7742855,   966838690, 485329071, 267788198, 353199712,
    716743917, 615389391, 257812554, 614776630, 833547538, 934946282,
    84784365,  932460698, 591304822, 657760700, 625210023, 546945046,
    155462373, 657439817, 28204066,  960569202, 802685196, 805100004,
    168310959, 637231710, 801092711, 686896377, 325954515, 772086933,
    174154800, 968758045, 290125431, 924062606, 676500183, 766331753,
    543812360, 545688026, 992636566, 600415168, 495578897, 149898661,
    206181268, 160006748, 482372979, 340076727, 380981376, 992266501,
    965982115, 651321357, 710190883, 460264183, 746530090, 921510687,
    859010088, 744989130, 914531666, 774265021, 767425610, 803604743,
    903328371, 203905462, 323178647, 218539877, 540423239, 206565172,
    447749162, 59294271,  657333616, 600021767, 248327314, 224811759,
    133852147, 773357564, 491237982, 749602560, 927334495, 258767729,
    902840608, 737965679, 175911702, 908641897, 171726886, 399437317,
    33798079,  983592077, 657297361, 586413721, 367033979, 763419961,
    400211983, 381627208, 916325875, 521711639, 968152365, 814438783,
    984832168, 850240512, 385942548, 477002462, 873399057, 851752845,
    760779790, 954009553, 286598146, 234257516, 893488895, 915147590,
    824057314, 754759283, 924203373, 166308788, 377655329, 658356191,
    77925001,  642953992, 53133798,  249284,    163196894, 516480739,
    956481041, 511884676, 479584457, 418868828, 445432156, 253676843,
    882495293, 347065993, 960581459, 776809266, 575402256, 715362343,
    326651615, 410750796, 178282727, 488073348, 213287200, 315163398,
    654280910, 214733146, 910676638, 392774266, 89042697,  122304384,
    671346513, 899072602, 223545271, 112553393, 545595520, 667136246,
    923338807, 389766173, 642823657, 225009453, 237976685, 603952906,
    604954431, 448286978, 6116509,   822661601, 839922055, 885169106,
    2937602,   100272146, 242769044, 754102777, 186552416, 726462905,
    479285748, 799251243, 656307405, 404811396, 114671384, 157884003,
    373007875, 136394658, 303714946, 887751292, 319702126, 976827776,
    24664677,  956252457, 580872506, 795184938, 446039064, 584389535,
    280081251, 98086984,  898636541, 351914721, 56123220,  217802329,
    239031186, 263830759, 787721167, 432493263, 136308350, 410148768,
    665331271, 116382935, 881785773, 158247199, 976010538, 287627545,
    344091402, 517265690, 502754944, 867634704, 127924474, 994063228,
    438228974, 252509498, 917547774, 219351222, 179140586, 879570145,
    446424791, 598664872, 810091669, 811051967, 41766801,  77999985,
    347379651, 837204262, 751450824, 137422154, 489004480, 77481844,
    968707898, 627565028, 446603792, 997709702, 905638002, 314900064,
    584913495, 679282762, 63151571,  613579483, 176773581, 639714930,
    124697076, 29154835,  221402002, 602862274, 573127297, 55105017,
    86489221,  636535824, 558948002, 373064984, 96055774,  341955245,
    979618769, 139761536, 608115079, 46321679,  819080491, 363627264,
    908523899, 25426621,  736776258, 728028104, 722340331, 679437585,
    92361862,  268276865, 957316642, 775877878, 517199404, 55339976,
    337173128, 16244235,  73548531,  907247809, 614722723, 676737112,
    797697740, 970384411, 819153580, 746413406, 336362789, 143903898,
    325601510, 660427306, 646556777, 705705150, 825596521, 899167909,
    974149295, 801608882, 435642318, 339748548, 145532586, 188124599,
    202038073, 537935910, 19852239,  618405925, 836694540, 257290432,
    99624063,  205521165, 480524942, 764214187, 983058658, 739181349,
    991588823, 821479637, 474896491, 843125404, 902902039, 434038615,
    482005052, 309778524, 213890893, 112548009, 228170300, 228913858,
    237742538, 98260579,  875715955, 847340252, 482823108, 994685812,
    634317804, 73086060,  974987285, 171715192, 400561524, 84120543,
    398246975, 400053735, 614594517, 273094925, 487841415, 96109528,
    254121341, 188862888, 129402910, 285303332, 224944190, 876461045,
    497121551, 883257886, 628585763, 813420929, 602398325, 846247642,
    781797790, 159486538, 191652286, 363752408, 119574782, 119404407,
    473428778, 422808713, 834257584, 729883291, 605323235, 531666959,
    752855907, 297473757, 587854857, 466104689, 309490685, 429817962,
    29259486,  655583795, 878261213, 162463164, 216924466, 793782283,
    253707580, 493516383, 747785119, 860008982, 883607144, 571176958,
    469930743, 720448928, 864437165, 911798790, 773745200, 553284135,
    12852523,  149561968, 705585339, 912838263, 196729971, 974700392,
    576403540, 845337039, 407576381, 51759145,  842628006, 225798491,
    45357354,  207017510, 278908914, 147436429, 369028530, 914688682,
    656017784, 148577916, 481996096, 917870766, 665474094, 954582480,
    702918162, 852176976, 799952889, 105752755, 797498417, 657272247,
    764507070, 721071560, 340462765, 44054647,  982826883, 722125878,
    807752721, 237409731, 118387213, 598872761, 861864667, 868816504,
    37907354,  90650401,  759048609, 948653472, 740914704, 986035761,
    337866534, 813652821, 112621335, 967270715, 808673012, 513731357,
    157139524, 608329815, 714568737, 620341980, 176690553, 10113164,
    670818247, 992055431, 829652132, 442439145, 915160932, 227405442,
    843505121, 361934917, 606719558, 865219010, 901434008, 961736267,
    95726579,  456117795, 959699774, 632613691, 215707123, 766649783,
    17628901,  957876411, 610734863, 286613402, 84080236,  454755231,
    362500700, 951384565, 938767647, 157215866, 606952868, 562260315,
    147423970, 847327703, 953247710, 684617511, 425416127, 158231183,
    113300833, 26208012,  223900820, 178943327, 124889390, 974154272,
    345108497, 183157298, 482172561, 954456090, 33723553,  348234673,
    512960465, 901999824, 75690657,  892258917, 376253853, 197124773,
    573851514, 825365830, 876668772, 492221683, 370194627, 230411712,
    73665816,  746855386, 774149580, 447221572, 242944596, 1657073,
    937093884, 275909647, 159195660, 196231989, 13719266,  377406663,
    878733209, 284975277, 697022838, 163930514, 685660859, 573490971,
    219464572, 792207680, 419915378, 59755527,  711995865, 352172770,
    177458894, 549207120, 84952794,  845536171, 229070291, 595646501,
    444678650, 843197768, 598895566, 829022322, 702880311, 299504453,
    612917898, 530129405, 799105762, 739366183, 924364333, 267696814,
    162727362, 179490331, 473432331, 534991212, 637821704, 914797165,
    86383160,  342204576, 739970551, 205511980, 148448232, 50125077,
    216839688, 609597924, 295307892, 100383201, 687425809, 496401478,
    942621091, 866842266, 584698063, 600559163, 244630378, 41673212,
    289077711, 5288572,   166011867, 568093562, 38011190,  66596430,
    720417597, 730781882, 938845175, 41401250,  581549495, 247564101,
    915116130, 737120686, 904114788, 238643084, 361049116, 58769726,
    374829370, 347538358, 73610328,  535972073, 760057616, 332914393,
    348872182, 312207668, 239902718, 416281963, 799744812, 665295661,
    475400552, 764453293, 785167864, 820492158, 652958242, 396013593,
    186417701, 266654097, 62481151,  457851029, 710106631, 894980823,
    918511639, 424847839, 83377735,  676032451, 232747963, 55363287,
    864883312, 652840853, 792577297, 340806898, 7129019,   79786334,
    71917363,  988353583, 756506058, 877086952, 226602674, 755229910,
    205075489, 665223599, 36302441,  641526304, 394191337, 395816116,
    40058788,  26003088,  884574270, 346259015, 156934965, 150286058,
    532806541, 783628257, 761162536, 269330915, 515571949, 125265189,
    868585662, 15193317,  13638524,  445397865, 789071500, 429865568,
    692525633, 571151495, 468589097, 985078585, 8738505,   768737652,
    424149800, 927933306, 595753133, 147471344, 752747830, 810662695,
    229721846, 276497895, 80673101,  40982210,  664566533, 418384873,
    509565544, 396261051, 198805918, 376916007, 520445351, 26069264,
    746547119, 827177752, 890439530, 208117151, 662149483, 902873967,
    89656728,  626577454, 525778994, 448966716, 294496090, 589827651,
    485410307, 81055823,  163094560, 430841743, 227755451, 350559889,
    400457233, 763171482, 625836500, 22834179,  627459637, 664571725,
    641091398, 87523890,  835619132, 264622955, 556433972, 234037235,
    740015592, 749448018, 136705743, 875958200, 781727755, 262593950,
    377071112, 287361259, 251459000, 226506094, 785011112, 182617900,
    503067523, 177491367, 744791485, 841391868, 991362407, 72771080,
    15897432,  634435647, 536730331, 75564272,  592474472, 767669679,
    932661486, 545933473, 828204225, 23364141,  206055418, 99433027,
    450395917, 828580982, 994101286, 730199262, 834474789, 942235184,
    438458343, 831232641, 170237827, 176653711, 28851952,  898612582,
    955949959, 284592263, 598083729, 72026978,  833361823, 997336279,
    802780162, 257571932, 913260521, 131092923, 179299796, 430029308,
    80200796,  748675279, 394460945, 223224805, 861541957, 648625724,
    952835950, 714212697, 712630553, 827068254, 6220258,   862718436,
    758717398, 134000853, 890452087, 954037300, 700137921, 52400131,
    737449453, 778818328, 964440109, 157556106, 862098819, 475886813,
    188169591, 321844941, 358187617, 486076988, 371752732, 522436829,
    458363370, 916042824, 824282493, 870368749, 234090231, 382254470,
    876009198, 867379440, 441874017, 451889445, 401002002, 71565786,
    578553363, 952110616, 375047959, 82296421,  820671977, 991031494,
    495553975, 318393614, 289645491, 303940736, 310305295, 139833848,
    171735903, 680918939, 870950039, 80820134,  533787967, 990752242,
    733762005, 684973377, 618675448, 697509683, 21524406,  161487408,
    89900746,  616581800, 938589544, 739300366, 264491524, 95000259,
    620335204, 720102819, 910541916, 60553591,  930484845, 126379946,
    769095987, 241468798, 87438169,  978752999, 735173042, 784079655,
    406982274, 462126006, 593737770, 631469321, 930967998, 571662179,
    414460993, 940595606, 646681502, 834242172, 705344102, 163724492,
    540216275, 798619927, 296094961, 388793049, 446892341, 245592617,
    405829736, 826625617, 541696816, 924110952, 571386583, 170381588,
    286440531, 628592057, 240312304, 815798324, 212958782, 786830092,
    591593879, 447466194, 110458675, 922095238, 406807928, 192139628,
    586822468, 127221551, 756211583, 215304909, 120911147, 421620406,
    706780593, 813893815, 871456528, 657374484, 602303197, 818093979,
    977823052, 292502231, 776865831, 997676763, 191433620, 367547362,
    21503695,  406665710, 19987461,  675020083, 270495383, 233560344,
    809495165, 374861604, 714274215, 134544133, 988366311, 610257209,
    952056745, 682142075, 351829212, 394867876, 585591636, 105599323,
    502791075, 745532176, 40805281,  952359136, 372616020, 507150746,
    736192706, 24232366,  936897605, 889827967, 310611568, 70117444,
    425197583, 438973825, 164021800, 930036413, 278611346, 557614674,
    807094155, 702391648, 892745100, 892395502, 566001463, 874744568,
    798254209, 409070955, 277287968, 779725312, 564826386, 248823665,
    439014091, 453864182, 82310077,  523719495, 884719908, 367078309,
    769582346, 186453072, 436344662, 842542610, 64026800,  53524784,
    263749441, 299146392, 859167627, 935835473, 785705548, 616397911,
    606920755, 790680780, 634846197, 434587374, 186487729, 499104654,
    344330262, 715699561, 628078626, 605771597, 70487383,  343223891,
    752937849, 414188067, 769799762, 371825239, 26923284,  818781627,
    753855864, 117207524, 777841219, 608522344, 816502171, 582680182,
    897108924, 188534252, 438303291, 820885423, 997723443, 529276926,
    868914102, 40097003,  907739860, 472268254, 223037992, 823452096,
    718169879, 818390870, 376429882, 362812972, 92777704,  198068356,
    782299298, 710773810, 442428234, 147032138, 506762167, 75284454,
    828127288, 460728417, 465771610, 129280457, 56518298,  526169490,
    22870610,  773784392, 338004662, 364339685, 887653491, 794428738,
    766509836, 844507281, 200575233, 649289655, 363310915, 227906214,
    93451726,  705458004, 474628201, 630159548, 40287296,  991660114,
    586390492, 835385204, 606806472, 791964565, 291340569, 954203886,
    367205272, 173093021, 646417616, 567714666, 586450479, 973384943,
    120357827, 680985174, 584654760, 551749292, 938508141, 675599597,
    431026254, 651606249, 87317591,  975058789, 858268476, 336829061,
    346661179, 277280102, 440695193, 681141685, 813901363, 947983277,
    650584680, 560353134, 220529568, 900969931, 958148974, 858561835,
    505039535, 39342836,  36970983,  319680707, 722380935, 719445202,
    505095219, 941973263, 919945575, 700533449, 825368358, 167302508,
    121996895, 209905596};
void fill(long long n) {
  for (long long k = 0; k < n; k++) {
    long long term = mul(C(n - 1, k), bell[k]);
    bell[n] = add(bell[n], term);
  }
}
void ini() {
  precalc();
  bell[0] = 1;
  for (long long i = 1; i < N; i++) {
    fill(i);
  }
}
long long solve(long long n) {
  precalc();
  long long ans = 0;
  for (long long k = 0; k < n; k++) {
    long long term = mul(C(n, n - k), bell[k]);
    ans = add(ans, term);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long ans = solve(n);
  cout << ans << endl;
  return 0;
}
