#include <bits/stdc++.h>
using namespace std;
const int maxn = 4010;
const int MOD = 1000000007;
const int B[] = {
    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};
int C[maxn][maxn];
int n;
void init() {
  C[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
}
int main() {
  scanf("%d", &n);
  init();
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans = (ans + (long long)C[n][i] * B[n - i]) % MOD;
  }
  printf("%I64d\n", ans);
  return 0;
}
