Planeetat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

const int N = 100;
ll fact[N+1];
ll inv_fact[N+1];

vector<ll> precalc = {0, 1, 3, 17, 142, 1569, 21576, 355081, 6805296, 148869153, 660215659, 920608908, 836504326, 639554500, 466620985, 872046927, 308717370, 502812808, 646301526, 985602096, 8033007, 199948617, 265123234, 963316760, 97012001, 520509077, 963089188, 609109590, 475681640, 268714573, 138142320, 659323185, 432287876, 833911481, 580044808, 724047794, 752488773, 369844336, 411404305, 966444867, 966304277, 670002988, 356672355, 499497440, 858083915, 849461059, 699627096, 696125320, 569657991, 589455080, 637699856, 159331976, 253230028, 126065421, 190780359, 657860743, 35914725, 627548423, 786042624, 88732365, 595484631, 907204844, 310896156, 654434332, 999859588, 891860619, 760802640, 321240817, 284705446, 581193655, 540500946, 828699763, 86377965, 299422367, 636989116, 804687707, 341628824, 969661800, 493359322, 269113227, 2788545, 136045625, 319856162, 734688215, 933443980, 548820306, 844116817, 949670148, 893770986, 562714601, 464787503, 785661356, 27520011, 33434941, 651969158, 596069751, 447474780, 454137267, 430168215, 427270537, 894456323, 432736565, 541462563, 580395437, 926815786, 263023838, 779713525, 129353767, 254646934, 327058306, 318061585, 873404148, 546897006, 256895690, 845805366, 521993981, 151412543, 452233370, 169107595, 352810726, 932989581, 82660203, 144142246, 7983114, 841762719, 398368184, 36362596, 5939420, 621718875, 180998347, 89322205, 709123956, 45239813, 623512817, 592243835, 375742205, 13182108, 741093354, 954650126, 632161601, 323889231, 855586538, 576541114, 402077493, 420399764, 23768284, 168259101, 986206037, 639024795, 827219225, 972138947, 118660280, 935496148, 260619316, 568756388, 474316106, 90646046, 327256160, 906940925, 61315684, 100123479, 904812330, 341615294, 269531078, 100088684, 608203198, 84183940, 718793427, 269849284, 338624606, 60645067, 579226929, 140045143, 723080187, 393278301, 585228375, 59206357, 101985982, 672040685, 139906388, 744500615, 662412691, 158778780, 73399837, 332041241, 281105866, 957970313, 29966196, 815538417, 292300246, 570909748, 771503216, 214191103, 101730853, 63227600, 308932805, 811045900, 464333632, 357992660, 77607798, 507287768, 341677483, 72934014, 46989119, 114936355, 602267494, 906589693, 582034332, 895922440, 156857108, 618036646, 157634170, 761405010, 817859847, 467337486, 632543264, 517776051, 994834897, 687965083, 457907638, 825497422, 243467865, 14399121, 407258784, 98570234, 748959757, 297443300, 406918679, 871245292, 252946284, 452320327, 942393032, 318555470, 766642481, 981668534, 724552884, 301298708, 142719827, 453758144, 985372383, 718141077, 18615310, 590242901, 715391284, 471018736, 571254190, 833968271, 832120869, 945980567, 722309937, 54672675, 115490430, 187087627, 626363638, 686555146, 318156532, 972513131, 167214298, 90260614, 306880672, 32986840, 478943540, 672206708, 393818545, 416131966, 388360852, 956022816, 146560536, 392214273, 327393841, 526526895, 175253967, 352945422, 306638803, 941328742, 230321990, 570405207, 35763767, 385325705, 457471115, 680333391, 913022330, 507476085, 625156383, 460862378, 719762476, 612136402, 543142329, 910689236, 864620931, 94770086, 124023110, 936801504, 312536722, 840866722, 550990595, 847033780, 9264261, 210329044, 369392790, 722084766, 940376498, 107971898, 858413915, 472976473, 311774094, 267458901, 145925718, 338817999, 630914080, 579431167, 386296719, 138838078, 585741448, 847119734, 643211690, 268683825, 351931792, 735656552, 8097207, 868683252, 134721277, 751435055, 835490594, 768101286, 361829871, 395204061, 571729313, 121053572, 334933401, 823546703, 791822392, 196085636, 914631844, 921218256, 269969740, 960245594, 308426560, 50228312, 203517952, 816105383, 292189633, 32732523, 666262122, 437188886, 72215308, 918176539, 415978508, 85324969, 769013382, 647852341, 689378978, 613167392, 340915335, 831071843, 565517411, 255908828, 91838622, 605127507, 57150948, 686992820, 685954022, 342552285, 849812665, 260415783, 694407779, 131097970, 232078836, 790843917, 602509046, 136064185, 155679521, 958411398, 943708467, 206313402, 358630277, 411970955, 489455840, 988325815, 978309818, 166561041, 394433021, 617840127, 693970966, 995469520, 143162639, 766345048, 552437316, 141371172, 32069679, 516006699, 884187788, 608358064, 219163692, 387670703, 175148085, 17199999, 180488480, 660440926, 864052274, 765128850, 483638267, 499688410, 640750115, 524434952, 827157815, 514841947, 891119953, 537621015, 892118064, 928120221, 364674640, 992761107, 724302220, 924628854, 760255237, 769488054, 235556227, 244177714, 854964962, 259182566, 77503409, 507837049, 779838104, 423943877, 886744385, 958705993, 455048970, 824356123, 713721861, 331904766, 623348072, 614726681, 902610163, 946917405, 630933809, 683877164, 640836005, 535209373, 166585714, 161480461, 455967117, 252642116, 897912756, 319743887, 916746661, 702589733, 778455519, 494137733, 289013415, 719760981, 955879877, 505371826, 707573819, 803154268, 969112213, 221690942, 226656978, 735346391, 982277351, 592777469, 447310232, 172403391, 748268363, 601914711, 314744304, 694374706, 788244971, 937988296, 79919141, 145294051, 52674283, 265392050, 996188166, 381465305, 372742716, 485059689, 315704434, 844900882, 764763714, 332232108, 961793773, 365663110, 538922989, 601146238, 25707931, 555697561, 878705277, 319447511, 428853013, 742394955, 53270809, 647847019, 542010010, 434050460, 846597947, 956068884, 662776175, 977629798, 900768919, 129073991, 76026409, 498192056, 215123369, 917836934, 826637623, 435940858, 632532526, 979699864, 273969950, 101600462, 797914606, 356500503, 216770185, 381331949, 326172660, 937009827, 853670387, 682492038, 972664354, 284139447, 315944240, 791739438, 46026170, 412249526, 789973123, 832181317, 394745079, 241250226, 163080658, 90324747, 780658649, 40050836, 753363258, 490090701, 507159728, 175535065, 880542882, 601405007, 875042173, 988657013, 624703488, 609933868, 870319039, 865917489, 237139139, 171461911, 722145611, 176534686, 748791413, 777888894, 189895535, 127548304, 62907885, 838377878, 35812203, 917533875, 810336630, 926341711, 888415765, 670767852, 513394863, 223454100, 439177115, 658683635, 622286412, 444809364, 970826379, 277126519, 793591686, 965618620, 524560088, 518622823, 740934331, 615919709, 579173509, 11324360, 445025848, 856961685, 923580922, 185212905, 392675418, 727388601, 865839801, 76975614, 882654461, 676444158, 68254115, 309825214, 324465365, 841768008, 273959910, 438044305, 547731766, 711485207, 611633037, 901608514, 588206840, 824678995, 715062417, 384420191, 339850593, 508303398, 393630144, 829399774, 404455930, 437595436, 84921880, 407863020, 683956864, 584483785, 227026419, 772984782, 401523829, 185477490, 738922901, 327552152, 770760761, 378607522, 394710363, 763322048, 572718610, 939574117, 900466080, 869504287, 674683595, 842164179, 895649271, 202668486, 109169255, 216662266, 371897295, 625604906, 869773593, 833554505, 306574822, 731350505, 654193167, 960565833, 804819530, 279245477, 885855615, 215870028, 964455102, 544427865, 470123903, 23511463, 264092633, 638794607, 79622179, 474381606, 554791439, 330903508, 511020268, 932195757, 352156109, 244536936, 294113392, 142386392, 964997788, 373655410, 830312898, 163010932, 863889744, 102244077, 676493916, 189730587, 400057013, 465021266, 603765333, 103120244, 784797374, 373899879, 595340442, 425658649, 294186115, 670989044, 79022991, 21873737, 425688347, 89846397, 488428951, 746805572, 248666732, 753576270, 684601776, 236729218, 422757346, 848575098, 293549644, 980667733, 772661211, 276677051, 501793049, 880460037, 883830717, 950820192, 307979260, 751943962, 510752702, 744824767, 442457467, 149970957, 528163627, 696218575, 25298630, 747095783, 884906140, 909133547, 733653555, 146854917, 937116871, 163855877, 659732814, 709087432, 19492549, 147701829, 364984477, 953983272, 567675621, 499525550, 157113580, 398331965, 653488931, 868545818, 937865416, 255354491, 424337212, 586865979, 617557895, 111291906, 81586380, 386029611, 722531365, 497424224, 534960648, 559936484, 225894714, 573885746, 447007271, 10245498, 561579300, 766053818, 530349910, 398231244, 729004111, 108441817, 872910612, 602083783, 995052453, 821631128, 269715702, 456899624, 348077669, 325709455, 866705688, 860556688, 386447238, 115474755, 884458677, 446486925, 965099577, 72891374, 77737598, 502245864, 129016649, 826847537, 819513705, 43884324, 555472343, 326476625, 762976966, 402514248, 839207200, 38977123, 705559546, 562644196, 350626583, 9509184, 130499500, 108601600, 132081101, 366869182, 458726032, 29886768, 148686953, 885348268, 801459787, 139572747, 673185038, 991695943, 862630555, 522110620, 80076634, 966502459, 477995047, 21572279, 721384935, 193349150, 242811185, 37255341, 604049970, 825401160, 507527461, 726484848, 396061745, 203154030, 58041031, 640367423, 318384869, 608357962, 824194966, 825656956, 77368019, 478243250, 106866672, 641605168, 666826892, 406075975, 779083698, 310454415, 342169482, 803327115, 807386468, 255782051, 744364732, 950122691, 232360024, 943838879, 865866499, 288404715, 96301762, 280687956, 545244197, 915823587, 417570436, 387247458, 160322947, 244425439, 789934672, 680056276, 214979299, 860921706, 107319155, 316165313, 965981656, 606430957, 841585452, 501119730, 668310812, 378443564, 371207456, 755942925, 528113576, 983914180, 986125547, 848006220, 419529610, 53751915, 659806304, 597702448, 208134673, 783769758, 974670184, 515677410, 141562686, 300791432, 937938694, 650736657, 422159400, 666732079, 947382007, 87673516, 55967662, 804678627, 661131710, 692785158, 841985974, 201632612, 945517170, 692816862, 817773860, 168951065, 445290969, 34875543, 652783472, 664136292, 389817602, 117154460, 622797299, 148415442, 5708337, 666556057, 755755784, 366882575, 914194185, 906339336, 741626213, 90170576, 471762897, 438418175, 550769962, 595559461, 905064324, 917231767, 964520213, 358490848, 81057698, 247832532, 341219882, 100102824, 341934238, 396889111, 209145178, 923964885, 559093402, 365469193, 120384141, 903956071, 152602509, 267601813, 978731849, 532938250, 594199322, 785028054, 456440644, 567440735, 988054619, 405996756, 699153707, 894273966, 877916508, 328571157, 127445368, 597814206, 421399429, 993196046, 417582204, 988281451, 517534077, 352254670, 336896544, 306733391, 963995186, 727299010, 750107064, 516100901, 451617315, 252736041, 547822253, 519556226, 161488653, 609702989, 962913750, 244708312, 871684984, 846374473, 601268294, 272544856, 214984956, 266321320, 450324802, 794618905, 329197003, 720425508, 718926483, 305295730, 175588666, 373544508, 720535299, 10433899, 109859248, 764634302, 147733353, 337233802, 560942707, 93268801, 831913393, 916124868, 415567211, 362520882, 687700843, 108480217, 487643969, 769614190, 164330043, 964265852, 326198123, 61287690, 497760458, 950598050, 461145285, 595217468, 597316323, 933967768, 13002237, 366847138, 513592965, 196084977, 337595660, 887375487, 394116005, 268719147, 459011241, 478586418, 428004344, 427585581, 398347825, 485529467, 974262726, 877043992, 865496933, 485169739, 204160831, 360850302, 826629207, 948631754, 572802768, 516487919, 507452190, 288860343, 55078051, 213000963, 750687739, 609530984, 502955628, 309477459, 723217487, 466348093, 987825043, 579172097, 899724792, 969650508, 53819821, 930938165, 806298514, 503183988, 215659602, 759949498, 275591144, 217965476, 112032447, 988483485, 689931614, 626024891, 585826791, 195944299, 406008749, 229336021, 971100806, 60752686, 672600506, 133860303, 975641493, 422579410, 522726497, 323293715, 589942941, 785922954, 511312487, 159512465, 831212924, 250550884, 82741720, 22404601, 650217395, 146107983, 551526542, 575599957, 162521050, 149485478, 152610625, 13547158, 605288134, 299255862, 647616848, 828357658, 519541900, 261610452, 808475240, 533655987, 830462483, 219754438, 998148668, 633792537, 339771115, 515071927, 732601227, 695109360, 138661897, 614396758, 953160893, 704575139, 483861263, 410546807, 751806895, 843172949, 945088802, 160043091, 275894659, 146367349, 827732507, 693846770, 740601331, 10258522, 879124922, 323026593, 107712067, 405595743, 949933359, 469293333, 89871061, 732935377, 637412130, 373131056, 701665527, 666687613, 101838884, 966450421, 697501479, 703016989, 537524642, 774468498, 460330472, 766502143, 391420755, 253300533, 915709450, 446285682, 564846955, 118204760, 337019520, 804948067, 456302554, 61797347, 51076318, 158135891, 663869420, 557790962, 404915771, 74671362, 20711704, 14956290, 535197310, 404342843, 489805444, 161980354, 790800991, 974413024, 243540404, 552360264, 310175781, 985139294, 939287185, 499443741, 88975671, 340441619, 881094737, 302635619, 130301897, 397900099, 229678788, 770583889, 479735507, 313647083, 264764513, 991014386, 57611778, 564681517, 451193458, 116090524, 847697460, 532190580, 173977459, 309076340, 604949964, 216552014, 145171809, 327972078, 263989410, 100043439, 736012429, 866499995, 884626657, 353718712, 217010272, 123616700, 87385887, 793180764, 730307885, 446934334, 304557638, 240613545, 103101145, 545905497, 958176451, 488859248, 736039744, 713924701, 528239124, 76186716, 674023710, 444760072, 207779409, 195285135, 22298341, 652813306, 460938297, 344108813, 504361467, 864850223, 836750902, 563978111, 415339206, 933932555, 740260623, 329318287, 618428005, 710468127, 599104505, 907596106, 380515644, 235540730, 7879934, 249935739, 72942155, 70396755, 166358717, 285269760, 265468928, 455214955, 452157803, 25983969, 709639725, 33830386, 157529403, 346365116, 656968732, 144719168, 278138424, 50820837, 946264276, 163727272, 258384742, 964406934, 799852861, 771053678, 169132451, 482537949, 64604156, 184280519, 171230101, 308345068, 341336338, 75168247, 536935039, 689188119, 67360753, 603173504, 670370518, 233307305, 689561519, 470268287, 476808633, 741232555, 163372059, 890258227, 243234423, 570016344, 291095796, 389144970, 604367506, 812364795, 639211190, 374673593, 643972257, 523643744, 581238074, 859458958, 417191144, 577066225, 538448905, 241997711, 918275880, 666246025, 131624812, 586080391, 926113190, 367261302, 406172656, 888822051, 791671956, 992691833, 896860338, 731476336, 340683838, 722018153, 603954875, 240415991, 914463313, 318635211, 462768445, 414769319, 215134114, 521981506, 109137710, 284869584, 190346789, 293587178, 297631576, 808988257, 759135362, 932671361, 651013182, 149916701, 691760897, 750845414, 773748256, 795192319, 677616235, 94707751, 399251900, 844271990, 671301281, 106302520, 979560697, 297771366, 996756387, 926745288, 201000826, 669551589, 129453456, 693720496, 195628289, 498319867, 26812051, 476790258, 829386451, 930112253, 648275620, 618703631, 290218657, 88607275, 1200672, 22405429, 674894420, 253505052, 653670382, 980980984, 930844464, 281769048, 90797988, 215696044, 374726585, 780747353, 306685454, 889272301, 765470161, 377559977, 705918916, 835109163, 577654011, 737910162, 373518888, 272501802, 179656415, 455661117, 699693335, 490520141, 177093291, 781087158, 355547351, 256376388, 737702465, 67213703, 998894074, 777469062, 388474393, 427836691, 735278945, 410947150, 174677846, 136816945, 514264351, 469203099, 322490285, 967355424, 905416692, 364346247, 393428828, 683717231, 959694394, 375656193, 263311206, 377345022, 448259578, 62559453, 871426787, 16063672, 216227970, 413472183, 294338702, 124742406, 368533829, 915811262, 455618200, 165103901, 105187597, 290257731, 905865070, 751442265, 959101200, 863673731, 284333975, 219994111, 472805270, 192803852, 236347493, 35838278, 578869230, 212826892, 336073580, 839734678, 948681412, 109190209, 899657927, 589454565, 336773664, 319509465, 369929180, 330762061, 19770397, 927775675, 141907744, 169812915, 648276330, 347402841, 542422794, 126844813, 782723668, 69780198, 525739674, 237163551, 807230045, 398257178, 438753251, 936407958, 408977043, 941614569, 76437249, 22756969, 143757883, 760571434, 142149384, 624015837, 509633305, 901496324, 247310440, 295777188, 838768355, 619230275, 384330411, 86979896, 430702197, 226255491, 34214979, 144974499, 700808601, 62406725, 216039073, 908837732, 958475708, 116583662, 585111215, 90813303, 162751614, 846140462, 106802344, 389967952, 758705544, 12849946, 504013457, 202064369, 665708800, 312723830, 886442339, 627905461, 869903657, 969368659, 43542077, 454973797, 284259581, 135506856, 101417859, 132762556, 521532173, 843823048, 269414249, 223957190, 917166265, 215870187, 666442624, 36627373, 415444695, 574045413, 894494518, 79545474, 147406106, 348644712, 358438843, 761889196, 407110455, 350154324, 767726348, 20973018, 900847880, 210048644, 453362472, 812994799, 586161557, 43737178, 771071019, 99257392, 794326090, 227323117, 784420803, 798161652, 184516839, 585048757, 905414087, 228572897, 20792888, 48674592, 35109037, 858856997, 482939343, 691497624, 736405920, 901878734, 115539394, 228023460, 785402156, 520427158, 922101358, 219102984, 396023544, 238648036, 630220161, 227499274, 976699026, 401811965, 930814837, 851703333, 131415861, 450680419, 171710506, 98260444, 127499037, 940906471, 835324889, 904622756, 327464727, 979124001, 828823086, 741140794, 8763114, 298833773, 148656667, 479871943, 332165838, 672986068, 569935137, 442666914, 305605820, 554526509, 127705959, 530197838, 720708852, 723365804, 316834289, 337306520, 993610902, 329563558, 827471057, 817436607, 249225746, 563436543, 929272423, 972994703, 828990426, 146680658, 580683029, 332257009, 794144698, 903212046, 995334761, 569737526, 600014167, 600222492, 16480554, 154565505, 188519003, 141558598, 640185469, 878330294, 161286841, 249823219, 30748011, 871343226, 936412327, 579915552, 41743671, 571409418, 218279418, 414871310, 347359586, 800247247, 402166513, 999609821, 858108743, 705347102, 383248803, 533527407, 296803185, 311723160, 408817433, 257155948, 23414381, 522811718, 992725928, 704468715, 352192762, 159535781, 923781957, 140046353, 694167441, 532897681, 54608212, 805417900, 950045390, 187315947, 591328380, 858092214, 855635258, 213561992, 181150307, 168164139, 842487048, 545807526, 789933840, 788670946, 542604319, 504380577, 99451960, 877652189, 888109682, 796945469, 594338173, 77435343, 768246289, 385634838, 201596138, 631358257, 578288128, 614478129, 952109492, 436914306, 73014869, 562722258, 498441255, 435355775, 346743378, 549322172, 219777368, 333392054, 637356257, 74647259, 231996286, 596446889, 907423454, 982984944, 500668735, 825671303, 533192508, 375379512, 503133099, 628952766, 285769391, 388604307, 58009570, 639746735, 786936348, 435379854, 586310453, 25336216, 233310661, 659450199, 12920439, 670399289, 176166311, 58225420, 51950318, 647246245, 6331365, 532828466, 413899240, 971357128, 942236429, 553840351, 694668344, 859366896, 46807404, 712607156, 847220336, 348142604, 911372159, 652726300, 873196192, 654359829, 726271686, 96152885, 737277252, 764257498, 506283430, 621086593, 316871958, 368300980, 886425026, 575655006, 848597916, 912809765, 51554468, 129588377, 962252654, 248915923, 708238892, 394677524, 295698523, 311466999, 223704752, 560219765, 87267233, 291141544, 551876609, 754909600, 310558042, 925331373, 970955971, 169993248, 954434931, 299072169, 938806175, 329528015, 726485203, 710291978, 768065915, 429286787, 983836380, 395182432, 89487541, 394700227, 284071906, 390484454, 696963386, 156356047, 415670157, 539228685, 718178253, 619046136, 37016650, 740357679, 988472816, 599095964, 177496149, 80904144, 699787891, 700108970, 446943812, 541792351, 905407899, 759770365, 388852112, 459613304, 76277874, 932401191, 349129570, 856063611, 844731435, 724914323, 515326089, 689992038, 186456829, 96909515, 484835936, 845500789, 650427093, 920345549, 985824718, 395038118, 767495750, 476465662, 678274921, 730170172, 524733807, 383915060, 500204591, 353386990, 541534086, 559520665, 93581061, 648288858, 575846005, 859017740, 749314656, 404731191, 973499840, 168965558, 102795381, 459853681, 560002872, 594695596, 112391320, 361177654, 849673628, 852477919, 851124775, 650043365, 674643401, 231740881, 835947823, 574276376, 156898381, 684203903, 282698156, 208543884, 517452958, 517518957, 918963688, 477086679, 694914619, 190427802, 6752636, 520979680, 403415920, 199983414, 660775635, 637523143, 614934693, 955638676, 517888633, 387039286, 956546203, 280715090, 595725891, 209287741, 7399613, 890695144, 258010653, 731331269, 897673206, 579189173, 648709353, 171228881, 312648732, 809803427, 128366953, 931590290, 955468596, 307051673, 270771789, 27731510, 820665200, 362582424, 155834721, 994326150, 664855806, 687986381, 369288815, 877057655, 833299265, 23756387, 342197524, 732104662, 395944601, 376470716, 518206724, 456553454, 70246180, 978230938, 961009168, 595481470, 276143224, 742038954, 380642977, 395565112, 348995066, 811779118, 833937259, 226479879, 951871461, 440540074, 756508256, 275474542, 155297804, 42295134, 785114406, 428069929, 510829023, 790374767, 967509858, 105359717, 636066938, 70615490, 480825916, 256801455, 137923775, 787205486, 881292511, 801943941, 247283031, 389371255, 435493395, 114796603, 430275858, 882834287, 162726853, 609592512, 980670693, 764605789, 211217430, 231980890, 161771930, 385844728, 508454208, 139712328, 195702859, 68558923, 334773010, 668775380, 606653338, 134369441, 700650107, 379522601, 134216347, 882173668, 893579958, 997849579, 620345163, 638028844, 809285297, 11455094, 884431021, 955678988, 62957580, 444129179, 552400630, 190917375, 241548958, 490619283, 522670904, 480636006, 765168161, 173106477, 109138477, 685249044, 241182092, 214935025, 663383851, 566769321, 946384680, 111420128, 294937425, 139721020, 701693037, 983256054, 579940792, 409321321, 331980858, 984178617, 364332167, 176661285, 272445480, 111855424, 770173490, 859433560, 18281680, 298554680, 193899691, 511866771, 229534700, 890069045, 62053931, 559187307, 388774154, 837013407, 253093864, 359529215, 725281340, 290794468, 588504267, 519718328, 544189087, 586596028, 511742599, 519252415, 212972844, 558340980, 108897243, 556199758, 689797132, 221700915, 901674110, 996689154, 236607918, 653826586, 216529824, 16754531, 749504438, 837071931, 515291775, 127913399, 126623076, 877372738, 838593993, 352146107, 511037567, 343560999, 888566867, 816436202, 509573704, 451530131, 348115469, 425188394, 279039861, 567173892, 501185627, 157987014, 188090098, 905647276, 736503280, 831112201, 746205543, 198039724, 630088256, 90428892, 11359262, 732002530, 955469029, 762884217, 922287373, 871899584, 922626776, 179292872, 98254018, 469001116, 507844739, 811152498, 330253675, 415872579, 958041218, 55518169, 764481251, 863818174, 570891448, 876369664, 281067333, 972500584, 442282236, 674775824, 77582231, 984908916, 643725650, 216591068, 777661171, 689496646, 980249778, 715960761, 724825143, 801230782, 383418234, 769314906, 809711513, 804164844, 642402294, 51028608, 399315188, 989014887, 765253596, 905364260, 208782796, 989668173, 629041839, 465538361, 627572034, 833196434, 235579670, 426762614, 972544306, 864514011, 9317622, 86923734, 470877396, 282363243, 448779152, 686263108, 698595196, 105287830, 335483052, 358882003, 992921858, 230656208, 910404895, 415571783, 333173864, 144233762, 600095150, 692698109, 248135200, 769260612, 551820594, 150113220, 25748981, 395409417, 675541597, 163054720, 399084257, 339476558, 559242608, 338635557, 239238236, 435943882, 548477410, 693810128, 184030421, 56030057, 330046946, 587103369, 10930159, 76707828, 133796781, 581618684, 398972824, 701339279, 185196744, 941759383, 825535786, 181971158, 492605134, 835654686, 454474255, 647097731, 984111858, 669047789, 406182332, 55069516, 191772530, 173873178, 167128663, 320033228, 473286213, 168257325, 500843137, 324528390, 875866240, 453278097, 645835379, 743304690, 983876230, 82583873, 381918945, 5286910, 467805306, 437463410, 32486366, 631874978, 688119112, 7005857, 965342649, 389050130, 512678109, 401411905, 286695699, 532423525, 7175267, 974360813, 374908790, 417593686, 324302858, 579946197, 461478269, 390763820, 470653415, 157165072, 476925089, 990191288, 631137818, 866353244, 241065415, 780509496, 718395754, 405393956, 450427151, 974552821, 30639268, 52893134, 368744258, 306034996, 96602299, 948151343, 938742082, 157517669, 557128567, 300569808, 196053006, 925949830, 403043872, 534899837, 652202724, 397459748, 4455524, 588660470, 897053301, 916847302, 495004453, 388733316, 175151113, 720533183, 436934562, 325101863, 728074502, 426205171, 509715380, 486144242, 398468757, 685831478, 930449846, 100471385, 473732415, 896632781, 184986428, 56316515, 95803688, 917306203, 365230033, 394439464, 280240535, 987377679, 698610823, 557132857, 165186446, 388047551, 773690816, 266735966, 292354063, 37331227, 807764909, 395191766, 628649438, 36790135, 487299985, 743806826, 146436086, 129006546, 564517314, 317474030, 309700467, 449219496, 283705435, 829335226, 411525244, 797807046, 449208688, 380131916, 651057612, 859677077, 968924468, 278435402, 978382333, 561025271, 508008259, 526694032, 497375503, 499541337, 703180815, 552075685, 575250801, 905584824, 292774358, 564842930, 478351765, 941324381, 218574563, 768644751, 66879736, 139572325, 858835606, 531753635, 174656142, 654502797, 812377686, 949238662, 859231337, 844011773, 115908874, 512049320, 791067497, 170076914, 673213735, 434643603, 361249118, 691135478, 526978489, 996933732, 622513405, 586023355, 713349069, 38273639, 349426211, 991131455, 620217367, 691528772, 925562082, 371350207, 569425097, 292005063, 707548497, 724595835, 734284301, 411199747, 483102828, 843832566, 440008358, 59959550, 631696557, 595755697, 73008652, 612916072, 672383890, 471633336, 649607599, 772155365, 686091655, 30913540, 456618538, 848772148, 306457123, 698863702, 395712761, 785591296, 502590350, 467634593, 874937372, 498453744, 55015195, 758443001, 412610835, 71161526, 472632806, 285510339, 523963476, 969115473, 367294710, 59883265, 439566710, 853024106, 8253355, 666965620, 576408604, 372437027, 203247273, 453959002, 602085319, 483329501, 939504690, 902829162, 280077900, 121373256, 405999474, 961590076, 25581321, 104730568, 604080616, 672459111, 968267664, 38069971, 671795777, 4969577, 232333070, 200047277, 769635783, 659051444, 488165212, 232966391, 136580520, 175880154, 391907659, 994035169, 688902720, 260629335, 45910747, 64761249, 247907381, 775205973, 332921659, 756030269, 470468744, 719439051, 674634808, 501346336, 516281515, 848333713, 498192470, 628285174, 102813911, 100994662, 13793672, 224588967, 289628954, 919001194, 526303929, 154222162, 968635480, 907527084, 329173463, 624442382, 295918563, 530845783, 382316759, 714318209, 683457391, 62444367, 669679541, 957598809, 926501899, 23426776, 762930014, 422510451, 150319228, 249005212, 799176799, 594955598, 817339512, 638314201, 19745228, 426969785, 472018255, 412934745, 203764132, 280487699, 935899844, 486240553, 522199568, 424349846, 370371597, 138486285, 26869996, 450357857, 160553661, 403484526, 794920969, 141445272, 494467914, 53706939, 479770692, 546434371, 998066673, 132693914, 498537229, 96319887, 489774071, 150922404, 353451452, 805807658, 780175466, 564158321, 130666776, 250027910, 735435645, 419661521, 681343629, 138684972, 884774174, 977156206, 948100443, 912618160, 667096508, 912268853, 465648878, 87014689, 717856112, 413127171, 557497740, 403198123, 647302819, 229856913, 866654598, 107877409, 783729933, 330402809, 539190201, 222428791, 205905163, 972979668, 746883440, 744150429, 974584948, 287433118, 371951535, 639676737, 355603212, 269023408, 94433931, 345824464, 721232015, 474177390, 652196309, 840893445, 204520809, 852259991, 598876547, 236795881, 455597986, 826476904, 88794692, 352594956, 966256753, 358076159, 723562498, 179944859, 868768821, 973761189, 299882634, 870301442, 608884415, 709818082, 918753054, 657407607, 970298235, 690288604, 538016376, 250840316, 293558523, 253223959, 687361035, 899381179, 756289076, 48836233, 286121968, 554404429, 745756810, 239566729, 381207021, 779528562, 990646301, 40080127, 516583177, 150633227, 88164370, 663225412, 142157063, 235232676, 478590189, 741112724, 518253159, 252084387, 976908016, 195124998, 442141358, 404842094, 131107333, 121410246, 219506546, 834295670, 280155022, 656977614, 694838699, 850609402, 989293280, 333595261, 34517118, 911558289, 793521661, 716589907, 391302426, 303927652, 356037159, 459933919, 641554113, 3152888, 825470911, 821482307, 973102522, 904646430, 176912289, 118241761, 881756052, 848878978, 678365875, 745127944, 351485046, 706673317, 125606823, 693431387, 625816029, 536981779, 825581487, 984021921, 643464804, 792387680, 142977835, 339776584, 483074175, 883706770, 52076049, 198609355, 159796014, 72494085, 126278163, 677716475, 568734280, 23122025, 906234981, 430059642, 893923606, 141515635, 492634548, 864946068, 111622987, 305730055, 260582381, 550034393, 534005801, 132406040, 781625844, 125211286, 103725287, 136531663, 580552267, 447029520, 350104287, 958800083, 463702360, 731483149, 152169464, 98286703, 510037403, 940093671, 42228889, 929550564, 711644907, 514577227, 609441245, 825233261, 825124139, 534833469, 828573332, 643579873, 962663354, 565624821, 58354557, 809307824, 580465343, 991541003, 335185354, 120322377, 498309686, 758732819, 299293487, 114571932, 964963932, 628615317, 986064346, 11569101, 740282013, 323682279, 697896793, 567134290, 995398625, 506660326, 389562832, 609470747, 514988770, 811300195, 684869247, 424513913, 33766325, 51956041, 149060439, 3814437, 883370422, 814548480, 196968359, 531744838, 205927355, 514447382, 14958950, 782740163, 756653303, 401428752, 669028637, 885940243, 824688645, 108634220, 157834333, 216471432, 568047145, 763523285, 642159941, 791493576, 488349401, 112451643, 630800052, 232598786, 564554407, 681154546, 309086755, 314918414, 925390683, 970486096, 794234214, 161285864, 865750191, 291841017, 606924827, 369590117, 715603513, 332195628, 556567951, 93804444, 516173059, 374211514, 259804319, 855899599, 972582540, 639514014, 653968512, 208869504, 344141751, 298206397, 487752259, 12191037, 707939986, 156676641, 920944028, 830200937, 177853056, 458434349, 600351684, 886977885, 666002992, 485346692, 565992890, 244467952, 301883504, 514034289, 342615421, 471208884, 231564881, 940174031, 5818629, 91206322, 599961356, 431677922, 378792841, 475112287, 570472894, 135892461, 848033990, 142671980, 120177794, 163284452, 891514806, 731089142, 25840939, 551769868, 625357199, 380489614, 77702356, 271656407, 888251629, 63886764, 174672900, 998272795, 436059595, 870561317, 554791702, 541104018, 598121847, 570588, 736211954, 403395684, 635813324, 337718253, 813814998, 664627821, 830819813, 990452615, 659501671, 288088301, 317621852, 232951511, 754103327, 782544566, 773353903, 603716606, 593545787, 79681699, 374308539, 430652363, 163886314, 430541643, 535861745, 741978577, 617555406, 794323790, 928223534, 739655528, 239457260, 256163837, 565651357, 674526607, 479512828, 700170943, 411945180, 611966400, 660901397, 653780856, 292227690, 857409231, 232987797, 752830486, 497996267, 124483999, 416828736, 51080561, 616807832, 165120747, 687933037, 929398819, 665689414, 398440392, 52793794, 454403650, 522713641, 683644749, 988200480, 343545390, 64427251, 748892528, 911826253, 413945372, 574074178, 702579899, 38459757, 487445319, 607553205, 843434309, 759893633, 138987316, 991524086, 161939392, 844124821, 552997330, 721905829, 143489651, 43373942, 876955849, 59243057, 961536050, 490606862, 837806042, 931620864, 18342926, 131431386, 490241939, 437841493, 991189006, 441272145, 202306916, 578475887, 715193248, 571032489, 902053337, 899191011, 874783317, 637925873, 434294734, 362475747, 864615965, 879127448, 718390219, 505556812, 780488867, 127969832, 240580056, 701281108, 916807959, 806338939, 725584814, 164578279, 47704420, 45943429, 673942401, 492117557, 469270, 637165395, 663925432, 667995704, 345252704, 533080359, 631953242, 117479587, 47641955, 521548468, 715636778, 790287518, 219675456, 461843552, 182735943, 713733741, 151157537, 809125864, 314437565, 687993621, 911616157, 431428568, 691007686, 541260197, 421649161, 648722836, 274584660, 516147161, 567228435, 223032769, 135576809, 615588001, 859687974, 139910960, 246050527, 870621488, 180644750, 576964089, 908221683, 949937964, 788410349, 293637684, 694872338, 272316679, 184161692, 792411056, 870577610, 852063160, 806317989, 655831648, 702670650, 441174186, 289688534, 669704389, 528793289, 96666487, 343231713, 747837129, 376686908, 138205960, 955280315, 324363410, 470440843, 288350708, 972781065, 315147212, 25509210, 483492003, 307342399, 736835542, 639885112, 58568610, 212355445, 758804526, 640053892, 657312750, 983813699, 373022804, 352842413, 158124799, 358998806, 713122913, 82618294, 907651001, 886616672, 327030725, 509419704, 816906035, 594749902, 28117055, 886451416, 434920058, 322116523, 52906603, 243354981, 931617844, 968204035, 522094339, 945465643, 598830500, 835211598, 846632149, 972297377, 855710768, 340159182, 172091515, 529497232, 981384278, 471087111, 366860780, 734293166, 337151688, 506750743, 825385840, 637909261, 624786591, 18418721, 817531037, 970498716, 150206148, 649023257, 366153404, 13899154, 726623272, 351128841, 962346340, 910549622, 154502770, 151465847, 730125617, 772073361, 123460687, 656970747, 520205920, 896482262, 784394829, 176728898, 541455263, 423471183, 669653201, 697793272, 932405410, 892717038, 745463225, 24101263, 979370755, 337324214, 868768772, 718920764, 625700745, 782631041, 52795752, 838650782, 369721452, 227946452, 729206221, 506553836, 49842186, 2367273, 10838408, 207439465, 347694960, 748004637, 947162543, 761374538, 814924985, 801341970, 811074601, 94241927, 676884745, 809467041, 732683431, 755904578, 836373216, 689427310, 784265480, 951310941, 754275517, 577326263, 26775848, 471288021, 771934869, 105694619, 287543313, 427102299, 316251536, 916967095, 973060932, 454765673, 386570506, 93223865, 810903903, 121001478, 622984991, 846460252, 446580353, 943539160, 405041024, 888598907, 130022062, 968505039, 982155304, 852475469, 953807784, 421644506, 1815352, 937359924, 685523527, 611691358, 110319230, 413244559, 602171899, 195142012, 613199973, 66262387, 814392965, 348544605, 834221725, 374915689, 111262686, 773389383, 673145075, 465232425, 392380671, 620512310, 225518234, 369621198, 304276687, 435579687, 259249129, 211525863, 449661357, 559353934, 285902952, 633738320, 288044877, 666967530, 47029749, 32140629, 919467761, 230039364, 345365523, 424441258, 687460893, 596783850, 560763456, 302986529, 235528147, 503295538, 944016534, 290232726, 428384373, 574941703, 468224383, 827689053, 628972737, 333484750, 478621987, 877985609, 123262586, 679264454, 91523590, 619719934, 862559534, 903012445, 337351231, 154920618, 517785026, 6258692, 181324710, 443073133, 76283311, 538786766, 705994039, 861535774, 150514901, 902929498, 540063986, 260935350, 953411868, 96832424, 291276467, 516525836, 536138362, 466764558, 583360795, 560941553, 21467928, 2567738, 181544333, 865593325, 562831087, 654356036, 225101648, 284295134, 779570671, 774050679, 681483724, 642462911, 745601724, 208094089, 627604952, 458330827, 355034112, 262306864, 947069223, 291726912, 452594822, 20517635, 68157703, 204941324, 170610382, 1990656, 439731794, 14441833, 262413720, 897814774, 837133606, 213623526, 20772660, 915117210, 133862287, 986337712, 931340158, 117874326, 984015596, 350127898, 858145025, 823813148, 79074969, 674492103, 228058088, 936816831, 633996760, 366558375, 702995282, 42505219, 508609884, 765088467, 410023120, 352650013, 990541291, 654412643, 500210597, 185282285, 676682981, 311701718, 159082919, 325405985, 749858967, 664772840, 530165009, 405560936, 595550757, 776087356, 505522780, 24358673, 409823230, 531620092, 870893626, 367636518, 461977659, 914006712, 913060344, 255473953, 629668114, 702055221, 373759491, 525784428, 824741529, 202165178, 757393465, 838815438, 817756805, 98152769, 811643212, 385742542, 540039231, 771455930, 598220147, 564288838, 574003297, 340951608, 729215051, 153242777, 588101816, 869278221, 729103196, 18115873, 503001022, 10187643, 671354916, 456105632, 384310823, 760755348, 486213904, 741132939, 245518800, 175983689, 972115793, 838585459, 278569178, 890423961, 919150401, 15305681, 8734498, 972182951, 540152345, 50725391, 623483257, 797750145, 803253851, 915475362, 434131356, 284707312, 955732322, 882642460, 463205067, 940202344, 250939902, 237061316, 170804023, 53871291, 632598085, 522559986, 384529140, 293212125, 289017885, 355687507, 79235821, 546200752, 296853589, 763122766, 560963784, 781672350, 823225808, 731289956, 160128677, 911400695, 632175792, 792074778, 397776837, 492675859, 128672351, 991953379, 968128825, 548463038, 502134809, 888338825, 921517142, 219801547, 574044275, 475005214, 581149712, 604782993, 691257145, 335182262, 512959830, 530854306, 36307982, 97966784, 711965653, 340274017, 942890515, 101277127, 282965690, 490188785, 897707332, 414123562, 342206506, 15251311, 850848003, 559984505, 473795463, 817332645, 350866030, 263245090, 456762444, 250206171, 914840220, 683417183, 232177606, 303648066, 818339748, 182451650, 485466807, 891932655, 771559685, 98708079, 539997272, 786008910, 266474137, 790183596, 242792663, 706116399, 580992777, 914138401, 284663091, 451189965, 901087477, 745474380, 491058676, 94436875, 755126006, 519598123, 696067612, 934995617, 329083579, 466143185, 130714127, 222224164, 148965970, 2062643, 134605412, 70244474, 214804712, 350369004, 30369976, 434982243, 992027618, 432230963, 444178553, 105994015, 443864102, 32276774, 772404327, 242710188, 656657584, 502759166, 430171704, 136449353, 763741870, 473480578, 130504964, 168200799, 5284386, 778420698, 58757563, 301446135, 143009344, 270109181, 355588495, 412739686, 764018158, 284028767, 357770714, 729881081, 654313506, 965550401, 814081571, 606763601, 928105673, 928359458, 933833929, 354773158, 602719233, 407889632, 133884446, 605714214, 931138626, 587120382, 1075276, 14625617, 736649620, 716143219, 602310262, 41553390, 318843493, 617724255, 621489509, 894120415, 91239731, 841399225, 491771963, 795943229, 78526404, 717878982, 194496562, 176993308, 72953828, 960226091, 871531185, 91516272, 473917165, 372980966, 503375874, 32383173, 118498291, 448615188, 132551758, 957572251, 627834973, 503787210, 523688504, 599447298, 108612959, 699092352, 586281757, 150450809, 11744653, 316639497, 72078327, 567578144, 623647931, 411931488, 215326078, 240218360, 455329372, 17031700, 912419698, 629172081, 634861537, 49753842, 7692377, 339012948, 604627728, 57565678, 363464687, 954896259, 240710447, 789668327, 983369399, 634633860, 149330395, 416653039, 310294902, 935616261, 922763898, 372294771, 295151555, 218611445, 93554754, 226281273, 74957488, 404921312, 189147758, 659426817, 250462747, 882968268, 345472411, 725853383, 704654971, 739689493, 899586272, 38164876, 736015316, 679973149, 321639523, 917663024, 71438872, 611448256, 745124614, 735667892, 374523342, 15684773, 746754260, 341673432, 725597459, 792945517, 195614471, 668031036, 735667423, 104385269, 315315444, 750590563, 635430275, 151787219, 488169578, 770685252, 850283489, 293089813, 390431617, 983797498, 351665243, 231809738, 327140304, 527610451, 307127954, 255506332, 598839060, 274742652, 67278807, 451431317, 500780726, 399492600, 848027451, 696794863, 149361412, 419427373, 468941634, 583516387, 486578569, 363669527, 884341201, 993175888, 937126314, 130136019, 996621843, 956634369, 654900630, 894349397, 971330610, 328291263, 66262571, 212666413, 398613527, 334175902, 254553545, 984302371, 731870309, 322047263, 968251799, 542566546, 350692740, 218319417, 489141548, 816576999, 112783297, 489586746, 147140257, 705659398, 846156731, 89506345, 494027523, 345203258, 6161337, 499198642, 58603421, 894957347, 156348302, 700591724, 854420546, 116373387, 622103793, 302876958, 451780340, 161576675, 42512795, 996579151, 979161235, 661788645, 288388949, 473971252, 465146221, 616960638, 549242519, 798534114, 107653412, 892032201, 225510171, 124113980, 209934994, 361328758, 718694019, 493880180, 915122505, 816143449, 279989143, 965695467, 924658146, 511661284, 514404619, 819004854, 89886653, 905029165, 45161660, 372129279, 807825173, 47764627, 691459304, 941008870, 585865645, 10421012, 30608527, 574258607, 619120286, 351393495, 290374790, 500942424, 679034014, 166033701, 851540479, 245140909, 518404593, 753034228, 280751672, 38405094, 717179267, 645502692, 986826394, 695305303, 557706563, 426928140, 474237780, 32929552, 675230361, 654923869, 263694569, 834011984, 37991541, 388856309, 224077037, 645216545, 407786318, 492164655, 556678447, 207025623, 473937965, 881207494, 583344984, 228404868, 86550034, 207010171, 483139094, 939161244, 985887203, 552071657, 516071385, 122652728, 994559449, 391779718, 967374024, 608356050, 921822107, 126367769, 722902657, 878822959, 939215303, 110031958, 896797899, 86837564, 599695445, 783518158, 347804304, 5890943, 831026274, 435827240, 402334423, 961710374, 694005798, 192025425, 84336699, 769961023, 421573918, 457682895, 237627362, 641035789, 33331836, 400105099, 698096369, 717750392, 445794164, 80943985, 892306894, 985680261, 53810247, 415299257, 793237377, 66485205, 604124845, 573676015, 112913814, 995769456, 165394167, 676889986, 623284815, 485394747, 860552960, 630783225, 306382604, 476076923, 226774087, 88842388, 606120703, 330367449, 904644888, 534404337, 873689375, 765612452, 473911918, 460090475, 625653497, 359845413, 362049129, 803851578, 390660424, 678109242, 259473224, 605468753, 231490127, 862280902, 697814289, 345390666, 482420073, 57694493, 52504622, 513603515, 204313728, 778934964, 981293750, 475758232, 905246315, 210260075, 478703261, 913734261, 273296563, 561095264, 67643082, 509858132, 984054329, 961261127, 466878602, 995334924, 147652475, 126768853, 215762684, 42512162, 201894106, 644425395, 901813147, 5059535, 378542754, 547516804, 817452669, 313512303, 468701639, 443824251, 306321155, 911687587, 390999616, 72307622, 24217639, 916082294, 362825697, 224506262, 541990566, 160380557, 561473778, 295536037, 966486784, 136256277, 837647392, 274703222, 88374353, 960046956, 868590802, 76222881, 37001830, 849237420, 812113733, 275095686, 353830198, 731081767, 659863721, 187753637, 84661166, 280388665, 172535735, 340177007, 34061252, 920442042, 740241743, 217380110, 234197066, 595036946, 363412056, 531781789, 44487084, 13993112, 83904645, 913707511, 642536952, 853814905, 355783042, 204396397, 884681786, 517462996, 452369230, 701822750, 213088608, 859961859, 698624287, 819155248, 268806280, 503613687, 41308182, 186002133, 92191237, 484364782, 586692380, 846143932, 254601506, 700740902, 570919064, 842005661, 782989516, 445139252, 321318506, 28069985, 857614450, 592817243, 87802287, 822337928, 162011103, 521502319, 166802696, 352320769, 366347752, 668789645, 26131591, 385102575, 790987328, 325750719, 181951207, 806843398, 816798547, 496820163, 479307173, 851464109, 792700926, 615510541, 321051817, 386511514, 70617233, 42420993, 267597766, 526371954, 215160077, 958251573, 325917114, 570045622, 843069770, 484930396, 133415528, 380012614, 430354949, 524049635, 751442453, 622072890, 251393083, 691472023, 174394822, 738394750, 868474321, 760545589, 384318430, 901179526, 686864202, 502684958, 402898743, 333428605, 288767536, 86901578, 175786644, 625351913, 947507848, 399720633, 906178081, 166606891, 628623540, 678963290, 355148583, 30941589, 463162039, 562399331, 163140815, 826292757, 303545919, 298057977, 795451371, 791970322, 313239470, 809842518, 832426274, 477705422, 866642000, 121894497, 784667015, 710472637, 799757274, 314336555, 7882080, 727368296, 631553512, 57443928, 95941068, 235129479, 883768736, 718547600, 17034116, 678001034, 583509795, 416529257, 504150366, 926861787, 502601986, 248995135, 661041579, 478524461, 36701569, 635724371, 961249188, 709497935, 354176161, 567128664, 265612496, 786048717, 157198108, 953759493, 343092660, 725093968, 790317556, 998345714, 716068875, 441356622, 755516031, 481335573, 810805627, 80680810, 824763111, 212717300, 787956849, 681161310, 403958429, 687029881, 44158161, 76662614, 245760678, 592860429, 823456666, 765126144, 222528706, 434201263, 573445004, 335387377, 846128713, 469515901, 923444870, 910512692, 386083503, 477254165, 117268967, 416128450, 118997535, 126103632, 160679129, 914659004, 260006783, 316141783, 907896718, 686009521, 320770660, 927520966, 974220172, 743697585, 101595103, 688812573, 193035560, 293795225, 642452892, 86798239, 364071392, 883189146, 61498864, 578459821, 467271461, 931907864, 306757446, 118497817, 696300982, 300863189, 374385535, 556289181, 490501909, 761452070, 749335977, 835231939, 436610665, 585004061, 907184637, 484501400, 729909354, 236691153, 29357867, 519019712, 536352124, 859144718, 898751850, 324384991, 733186526, 222972798, 426146631, 10936664, 35345626, 781267233, 796848646, 802241900, 593572490, 182849951, 603994056, 976133534, 85431459, 695398573, 507362038, 287119192, 634116764, 382810566, 844538348, 894819609, 370110184, 400414097, 838637686, 920870910, 277819315, 292292751, 925700197, 780022339, 748687055, 958290280, 321599487, 59792003, 704438046, 440488524, 86376753, 693277731, 185431878, 59801516, 620556137, 698577712, 269399431, 997993721, 59424326, 687970901, 369558455, 88909002, 620661751, 384253543, 286545173, 296538170, 955929575, 834152541, 861900840, 267747936, 960003795, 93728104, 886333381, 198190447, 519830564, 640243769, 185601902, 778450063, 252097796, 881979552, 830381349, 565134678, 47971272, 564576703, 124947159, 402931902, 730901170, 770344553, 32805546, 631716426, 443515016, 508106725, 110396502, 670463077, 283526781, 393960180, 438474088, 406057763, 568218226, 546211017, 687936367, 44083286, 16927514, 977191767, 109934659, 612754650, 495369952, 782699202, 540740967, 453410701, 962468167, 930155840, 692908255, 740119989, 489961246, 941449786, 529640521, 246714889, 446717036, 392214131, 470162207, 941427542, 28093069, 267504365, 543365847, 979193371, 278440862, 628366371, 309599069, 475451262, 385852260, 453164464, 589735456, 442661789, 102180910, 180485088, 506746661, 105861824, 237733987, 164021193, 856148877, 201141443, 347798318, 73478523, 932186206, 952896666, 649450410, 435054753, 765187424, 891060703, 260194245, 140907381, 412470531, 838066867, 722527984, 323460139, 13427979, 34490165, 332372488, 985408020, 554081594, 230425897, 786298511, 458145761, 362061293, 840727395, 520302727, 289033661, 917527902, 499637136, 131993546, 703185941, 774830766, 484645476, 193495022, 337508798, 688419207, 191460289, 755437392, 966283116, 918388903, 445510728, 174549548, 615280904, 832275173, 475755332, 859163464, 601510929, 910024145, 559701814, 48902815, 612147602, 163820728, 488115121, 231999314, 60028875, 385783155, 162288922, 727352377, 28269922, 899648040, 524346453, 963943247, 593723968, 838720354, 29863430, 483174994, 467511413, 630426960, 43903518, 46210198, 82011322, 987190879, 526202177, 798933718, 756466869, 714842627, 225609798, 681576049, 911487229, 409924642, 209606903, 543675721, 866750437, 535345187, 398530947, 194696455, 259472681, 764354825, 703235218, 711563676, 697044277, 233173739, 700030730, 315723263, 62015640, 788658567, 837394600, 284639010, 364498129, 158610223, 320586047, 276675580, 426571027, 601796180, 130393148, 501168605, 504135570, 368481712, 624202320, 640363594, 279967759, 872271644, 550857906, 192163899, 684602966, 664786105, 452837072, 616076976, 27518239, 138592384, 595566687, 778391829, 551620664, 663542605, 450893859, 158207497, 104108731, 373443497, 476473124, 565858711, 847542350, 172138941, 401920766, 832192835, 788448505, 517829216, 367034004, 7553227, 178924689, 821480397, 825333508, 938052056, 342346240, 475764712, 645290610, 834643556, 990463581, 332278980, 98527175, 445715354, 962581066, 193610182, 205365065, 867377449, 847221521, 509958546, 604529560, 906549795, 663843495, 456534584, 858084191, 602691169, 419155726, 983858882, 265502439, 30905887, 763545848, 476368934, 480713029, 207259128, 193682460, 2938856, 660360176, 201736452, 710444112, 878504092, 849485367, 894553263, 168326432, 784233110, 355968817, 560844796, 627603782, 983056587, 395796352, 405524113, 557406419, 45985559, 652994795, 527846017, 683653696, 26080286, 227873602, 346294979, 862790463, 692755598, 738218689, 323963220, 233136972, 358430598, 759017658, 73982583, 379000829, 340102959, 89031841, 383568021, 498034535, 909099171, 668542109, 639297392, 58603560, 251836454, 956235051, 267207327, 623659741, 439769108, 764903128, 935444659, 443093012, 112451281, 210564134, 127141636, 750487498, 906462956, 167341732, 751150958, 392781083, 464993785, 378331655, 65385403, 356607011, 242671398, 854041620, 191357732, 836077605, 998313571, 90287054, 600167821, 423213538, 348110975, 807624518, 78947036, 724139945, 469132787, 413699372, 766430261, 629932184, 308295016, 123291887, 582516826, 626892948, 930764732, 778051598, 552731586, 948152243, 482781665, 655648896, 150599115, 798613615, 247977370, 187009651, 351718817, 287961617, 565937296, 481363273, 593064809, 205495142, 847612238, 118069865, 368966647, 135050788, 936878811, 777203487, 552106070, 399385712, 872399286, 569523066, 572810313, 868698883, 240077516, 516853872, 596756751, 686477689, 618306455, 827092735, 605567003, 247172478, 471161663, 838489907, 877726013, 999810004, 55507762, 696391118, 259746164, 159274586, 882145861, 871335356, 13460808, 765174111, 201156081, 844433634, 652401239, 716763709, 208108419, 785611171, 218444433, 239487099, 144270713, 423843273, 831427979, 204940121, 174266507, 798963000, 914606370, 507785004, 754179838, 188584209, 199556757, 273275195, 654178954, 753577356, 853665420, 457057586, 135249694, 484673486, 34219115, 459102938, 654469880, 713317532, 195282799, 964866526, 443123136, 477650972, 257236191, 561837223, 533938044, 979240576, 599031090, 574519166, 109763135, 137194798, 202119472, 209946540, 594393477, 162985221, 22778150, 876919655, 552959901, 734766362, 60277630, 611687537, 311075158, 372379981, 425852053, 140651307, 818514306, 46854836, 675066293, 611504609, 527455178, 675671931, 535226067, 791085751, 215576027, 107474715, 555864859, 49803797, 522126036, 720025575, 971589651, 516965993, 982154714, 518590613, 39362700, 549669385, 244781249, 282943358, 592566070, 69410929, 477468057, 297549308, 342018651, 359374335, 493471444, 935494879, 312049040, 279937461, 239132494, 712497262, 652073774, 23323457, 578714819, 708127507, 505914836, 196299146, 884091399, 5397708, 187589308, 47493239, 788804478, 991763681, 567108574, 524087623, 650546507, 45373795, 176488344, 68478423, 923305941, 167910658, 174605916, 940052085, 242235096, 448540310, 147207451, 898220680, 578070096, 223931586, 523797225, 31150305, 533934665, 934666237, 3368097, 460417285, 37281490, 708842013, 358117380, 702151513, 671550871, 360931619, 344139773, 461008008, 912744723, 997754794, 662711489, 786334067, 623493626, 31045503, 707272196, 283624030, 334291826, 181964586, 507975166, 233802038, 992674799, 493099101, 764204879, 823838797, 106527404, 740520231, 579225461, 217816350, 276273834, 778417949, 33849103, 137191906, 667723502, 451391492, 725161587, 590314148, 268021879, 898026162, 584598520, 672113547, 972386547, 887803141, 628404725, 533151428, 628716155, 980173876, 783931215, 866511636, 845719306, 264716222, 959245781, 925794551, 532572946, 640540400, 658992114, 238243569, 19316557, 793344987, 293492869, 575793819, 385142432, 678070732, 350003632, 508802370, 83386583, 347967862, 550987586, 992867262, 233976657, 94898197, 888682812, 683266914, 133352323, 938728833, 610995543, 619086158, 983070780, 823507078, 755175285, 694667592, 635396404, 382953851, 704868321, 337379015, 339674015, 113911245, 49429037, 675752798, 961645735, 299170529, 451860574, 823314124, 460196660, 987649622, 674609168, 336132907, 220969146, 341323394, 418591600, 47630627, 657273626, 606142181, 388103831, 542500538, 972662900, 707768166, 356901595, 694234730, 869346668, 832628086, 310974201, 602937290, 304606913, 446519323, 115117839, 144627034, 827787356, 284550462, 947333790, 761215267, 956647815, 640184110, 721289839, 475961977, 244661443, 565889765, 251504829, 721295575, 571023926, 912215345, 705653338, 666480301, 230675253, 448610678, 930744417, 585173274, 19484408, 462999342, 698171224, 321924621, 596881257, 718968783, 364262349, 280004798, 24354794, 332170311, 769464524, 393611071, 277026304, 800380413, 29925512, 271128735, 724037054, 171864835, 83702131, 521949518, 586704245, 401049819, 780452718, 276370823, 18705619, 297283637, 794379336, 513133494, 89940552, 979286876, 493922400, 86334712, 703393727, 434420505, 977801898, 817438522, 311680170, 302118571, 462980415, 822421123, 561700757, 307387378, 408244712, 318736439, 732339881, 826966587, 157932425, 217343726, 581199950, 138656797, 155116347, 196118696, 902385987, 942162339, 952142399, 343036324, 291191485, 554970157, 166313856, 266032609, 789396410, 561260169, 594604152, 476138850, 178566350, 178218079, 71699556, 596969452, 682963076, 103042181, 467922960, 480940308, 985548598, 573505052, 776423101, 132646387, 890436040, 342996351, 164838952, 166515409, 855209783, 831592500, 184205117, 140969643, 347015127, 882073371, 293186619, 674432978, 946551967, 502059696, 690918722, 652514415, 740849608, 771368248, 196114030, 501309355, 437873793, 600255027, 148958968, 51512733, 502494272, 370929558, 224214005, 453317181, 914669526, 384882184, 401538332, 476744503, 526910824, 865944446, 267190641, 874293576, 52195669, 780317516, 843660973, 518680445, 529167776, 12651346, 255553971, 787458963, 271981923, 986176009, 899722936, 22736604, 431178500, 533951403, 363226900, 576581492, 492917494, 840391888, 418961673, 916050757, 959976801, 124708454, 511154047, 575663375, 396718071, 261563031, 913717198, 487018340, 676934628, 831050016, 732886554, 396107950, 471255379, 733988147, 189755397, 244473965, 336965891, 710880207, 503933920, 370601590, 882523722, 423819973, 608157217, 970284822, 494545669, 552057139, 350675417, 459751068, 146395568, 606685894, 797808272, 325165451, 449455533, 724225374, 297460892, 582713769, 635452845, 970744366, 935835207, 864343095, 719896449, 260927052, 117049238, 386745234, 758957136, 614583337, 246657828, 200248459, 991872661, 183891809, 725561333, 981111812, 868203116, 268718303, 825664424, 743072234, 784756842, 444399373, 477148575, 668870759, 529443686, 39610443, 112404926, 686623618, 737070426, 491732569, 360576642, 907357688, 526753221, 532284615, 305149885, 327151227, 531525937, 198538517, 684207898, 669859464, 30440622, 544782893, 123465341, 171829834, 423574054, 296285364, 482116496, 141010647, 504034249, 266134603, 833898560, 721158645, 691405606, 829675470, 343936737, 364064601};
ll dp2[N+1][N+1];

ll modPow(ll a, ll b) {
	if (b & 1) return a * modPow(a, b-1) % MOD;
	if (b == 0) return 1;
	return modPow(a*a % MOD, b / 2);
}

ll binom(ll a, ll b) {
	if (a < b || b < 0) return 0;
	ll dv = (inv_fact[b] * inv_fact[a-b]) % MOD;
	return (fact[a] * dv) % MOD;
}

// Plan of attack: precalculate "TOTAL" for all n <= 5000

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	fact[0] = 1;
	for (int i = 1; i <= N; ++i) fact[i] = (fact[i-1] * i) % MOD;
	inv_fact[N] = modPow(fact[N], MOD - 2);
	for (int i = N-1; i >= 0; --i) inv_fact[i] = (inv_fact[i+1] * (i+1)) % MOD;

	dp2[0][0] = 1;
	for (int n = 1; n <= N; ++n) {
		for (int k = 1; k <= n; ++k) {
			for (int t = 1; t <= n; ++t) {
				dp2[n][k] = (dp2[n][k] + dp2[n-t][k-1] * (precalc[t] * binom(n-1, t-1) % MOD)) % MOD;
			}
		}
	}

	int n;
	cin >> n;
	for (int k = 1; k <= n; ++k) cout << dp2[n][k] << '\n';
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 2, 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: RUNTIME ERROR

Test 15

Group: 3

Verdict: RUNTIME ERROR

Test 16

Group: 3

Verdict: RUNTIME ERROR

Test 17

Group: 3

Verdict: RUNTIME ERROR

Test 18

Group: 3

Verdict: RUNTIME ERROR

Test 19

Group: 3

Verdict: RUNTIME ERROR

Test 20

Group: 3

Verdict: RUNTIME ERROR

Test 21

Group: 3

Verdict: RUNTIME ERROR

Test 22

Group: 3

Verdict: RUNTIME ERROR

Test 23

Group: 3

Verdict: RUNTIME ERROR

Test 24

Group: 3

Verdict: RUNTIME ERROR

Test 25

Group: 3

Verdict: RUNTIME ERROR