#include <stdio.h>
int A[5000] = {1, 2, 4, 12, 48, 192, 1008, 5760, 36000, 259200, 1987200, 16692480, 152409600, 482306047, 499537905, 220000084, 337152022, 479026514, 565309674, 183971433, 269776135, 563435698, 759766715, 80621070, 834605103, 335410188, 37453021, 26269542, 397658452, 690126198, 285242887, 271669655, 323611585, 41190658, 76296561, 979346324, 659014817, 850620177, 711801405, 147399275, 22341484, 378564651, 790034215, 896060255, 929175466, 122780640, 36190748, 7193135, 981241201, 808922129, 258509838, 725690102, 242339175, 824022838, 895113379, 579799731, 962275700, 859533334, 226333733, 396185497, 33793810, 924238561, 504538741, 873393678, 382392837, 568064638, 165432801, 986507525, 677654390, 687892957, 164875506, 262595734, 376181232, 825070786, 239150241, 434668964, 78805748, 767712341, 52347998, 373347164, 923185160, 16255984, 43891668, 544650266, 363230224, 926972353, 547780732, 733537553, 705601898, 630743289, 569930048, 190629985, 600459142, 568087492, 626086788, 897289327, 697465500, 431309683, 157496323, 61564198, 658796651, 571049265, 995735893, 946271552, 592817143, 940178190, 799991387, 220390518, 83053916, 988296011, 35778996, 122679345, 785736462, 499306579, 338836562, 517084317, 228728691, 576376990, 7213542, 169306723, 40189386, 504646425, 100542257, 507698617, 204490430, 245735569, 169987315, 462789953, 830786308, 340925130, 926159066, 814997181, 808373886, 567068316, 22176831, 888666445, 418079636, 896111358, 564460355, 759198104, 685501649, 812678671, 747085940, 498268024, 914675874, 978473262, 122180122, 536340302, 174173038, 541082638, 478303374, 992909046, 156325954, 781403441, 393380527, 743279475, 391748031, 990876622, 99858830, 595864443, 176721188, 214655652, 314285138, 808962540, 728914760, 360355630, 243704035, 461893954, 66749938, 986643374, 290968025, 397946571, 369223299, 917230003, 521159625, 197638449, 39584804, 689221333, 168689120, 63094111, 800468790, 909447076, 115017067, 363568530, 644250100, 180124433, 265885004, 983531282, 657219257, 717113340, 684247948, 744943091, 931019016, 21890676, 446801410, 5309323, 344625650, 832357085, 602271831, 190465167, 526337918, 98337900, 211320789, 466349975, 867023925, 661693470, 907373403, 669133866, 49917380, 495501779, 84224890, 53009519, 328198274, 55033943, 715866131, 970779932, 360527994, 70446234, 218800946, 361629874, 555039792, 905972668, 447238306, 349835256, 132278901, 45184254, 359555502, 27074153, 191027573, 787348441, 850707600, 897533752, 664321750, 962141259, 440416745, 426959838, 771891380, 435349346, 606774594, 624879961, 227357385, 525204102, 357401, 583005468, 260106401, 413919576, 761010304, 229609938, 239595828, 445241987, 11665396, 301455868, 687726784, 94428357, 148462777, 88081992, 735236500, 985574502, 851686499, 457915614, 840790497, 406975398, 130515029, 549279809, 285145981, 969586249, 258195403, 9569976, 350789128, 944219091, 603980493, 808271222, 431645367, 129644834, 667398307, 724717113, 839121625, 72148204, 352700307, 314332524, 94192350, 393787641, 365934282, 178360003, 635566355, 98186552, 723155490, 408190345, 495797095, 973394441, 401933288, 546213016, 119412507, 190723118, 139959468, 744142758, 268151649, 985662498, 651920807, 181597114, 446019973, 565644311, 122314606, 819924696, 130956459, 330874824, 122473468, 338680658, 612682727, 720671996, 38987423, 574027936, 363777406, 257766093, 413077161, 950789417, 356910884, 514069638, 212866518, 141020166, 724367422, 727440338, 419530372, 819717464, 229727876, 248198617, 903594229, 930965966, 957184268, 651203791, 496864540, 274823882, 885512651, 833917101, 315449639, 815731508, 148826745, 244759959, 762830015, 196383815, 164945682, 784963361, 441306042, 241308946, 921927872, 276960884, 89522024, 519062507, 688011350, 336316475, 258905449, 553446479, 985224818, 248082656, 39687315, 192440670, 393629690, 243766352, 567441126, 491633587, 583667248, 58089225, 667072713, 606019268, 488980527, 529343754, 452956550, 734637560, 671730059, 804436890, 276642084, 974214551, 169728806, 368499175, 187757047, 991860499, 268024709, 421127399, 380616317, 150197628, 417308884, 790169261, 830396098, 194393582, 669754248, 684234523, 376947284, 442884795, 394540442, 607035849, 910982500, 694068087, 926962093, 661399198, 137681575, 805410080, 585220326, 113119731, 635444163, 639756930, 972348689, 240745771, 954939790, 969737126, 371206157, 141606590, 358652911, 954032403, 195547721, 953820391, 556781877, 627570960, 81004610, 874691926, 859633069, 645754825, 158992570, 373998090, 234830278, 19289948, 910725035, 32310714, 480968825, 773909668, 29192107, 815162827, 243204644, 424821022, 337026029, 65272204, 807735972, 19258877, 708702894, 797924753, 777546814, 777258473, 986783793, 149517287, 950214766, 750062746, 418373958, 213397091, 344579708, 742839261, 422947296, 684156045, 884208731, 440956301, 814070295, 271621514, 703428325, 954966594, 652357087, 435994696, 626392558, 523444562, 504257521, 134590574, 824212090, 891552206, 124393760, 886499682, 386506009, 382349939, 509063880, 141756779, 618746213, 596511834, 435209969, 648608232, 298248260, 871924361, 631812970, 389691929, 112354098, 832867567, 318504868, 417556722, 231218671, 542202707, 701583931, 681200123, 768427196, 900596188, 327154578, 26068754, 186096595, 578439131, 975280203, 413797700, 148357863, 371928565, 436746256, 818716364, 988226733, 164214650, 503487942, 637227517, 418045672, 981264644, 391146031, 822792412, 127812180, 735053578, 855882650, 188847870, 64166396, 459347244, 851150635, 560085571, 771352679, 200948111, 476028785, 98089279, 331146919, 964070326, 72123521, 802138999, 376816409, 429946037, 857179010, 928725841, 198337488, 514179303, 524250833, 872075557, 733132794, 879799600, 424523757, 572707950, 691272187, 786036508, 321866389, 548670005, 452777448, 792711611, 306164446, 744334611, 115139580, 617849154, 294722289, 379435796, 94240295, 625585403, 128083923, 648214377, 91946334, 350081170, 570662556, 8739052, 511026830, 993639389, 54316977, 476726727, 606306328, 483214451, 929211443, 961467639, 407657349, 833786688, 395622891, 785376624, 42299680, 199847528, 52603036, 415072418, 156634836, 69247417, 948284970, 168582001, 655505048, 84875116, 811039634, 706517913, 760258200, 601232488, 627976104, 740160278, 119804785, 413789558, 968530764, 423693596, 298595556, 24781185, 686061507, 139060289, 324115859, 197786731, 321012287, 927168363, 368543664, 746226879, 675474362, 318407446, 180654237, 575387968, 122643340, 702548507, 73848318, 478399514, 825944100, 818155288, 361099938, 935705441, 781557338, 168996503, 693443911, 135905833, 742642915, 494472513, 670545643, 963547105, 427462727, 488806466, 456999624, 228871860, 945197268, 448631152, 691575807, 322504183, 214275256, 68862457, 532154997, 262970446, 856694180, 280542637, 605415405, 558089514, 211499165, 720728059, 496424953, 875328165, 644730627, 690678882, 960832796, 283354237, 858075132, 936227490, 284254531, 636058745, 141522097, 971928977, 109630668, 24441242, 670867847, 22217585, 216032112, 302572682, 509839972, 765764031, 282077355, 532406002, 141792922, 14823861, 829167620, 606812774, 33562766, 838751856, 968083461, 427354622, 43810018, 423957455, 735898880, 878979769, 860585841, 415771027, 978549734, 781437032, 760708660, 707052568, 231784762, 804253842, 253596791, 469721971, 386861110, 190018107, 97196006, 239072263, 517485516, 37871994, 147276830, 830057022, 366636567, 288848563, 454861848, 372595721, 58036928, 183590967, 194445883, 205772948, 121901399, 306055306, 366437289, 74425489, 856429979, 732846171, 449644466, 792801967, 518423612, 361128234, 628968377, 839308878, 289694193, 502137328, 834075979, 205851301, 997733955, 985740108, 693074437, 812127209, 725190893, 782269391, 939448462, 39139229, 947498574, 155252476, 155446074, 167214019, 809466012, 399883594, 456759763, 502901113, 549031743, 395519311, 168867189, 958505751, 683236800, 308605584, 67455911, 850739403, 163692478, 385944549, 805263435, 122701634, 752065710, 674089909, 882940176, 755444184, 411478221, 499900390, 95493166, 962199161, 587080822, 124672319, 487729748, 125586933, 70288621, 789684736, 728593733, 726573329, 972766188, 411355327, 917038825, 396551267, 892808176, 218183420, 144448037, 441759788, 94948729, 126631727, 83197809, 172517675, 916481115, 528662521, 287264094, 327239080, 294090476, 359286147, 829942965, 712054120, 310016351, 39896932, 870542736, 685959318, 487255009, 602308763, 414861247, 439573553, 99714450, 345957181, 560208631, 179972499, 156778132, 359670398, 851496278, 568964646, 257697277, 732137730, 118747260, 338962509, 959286793, 563998892, 156840852, 412586617, 889376597, 502440935, 205708525, 176982016, 954062583, 700590579, 776857741, 405775842, 224267583, 993736689, 571891595, 205420258, 509690365, 648574814, 814765646, 126031234, 301775620, 125077714, 375231227, 624773363, 749000075, 984610398, 965621218, 32768817, 530285258, 59337884, 202399348, 48234069, 748330727, 377448276, 203568153, 687749443, 365246687, 572681687, 250003229, 940116411, 876807218, 499609743, 664377120, 623668782, 969148959, 100957417, 972187201, 992790476, 494470852, 614615508, 401879114, 586015846, 289742858, 444684284, 361829650, 6814219, 699525571, 622759373, 23725732, 629534861, 315926442, 773269944, 145706361, 55148133, 811111485, 423908013, 690259681, 555122316, 485238985, 836860838, 23207651, 274217948, 456472781, 416110523, 694016380, 119789846, 530844158, 955008712, 796330315, 462972287, 520455082, 46560551, 354091251, 972499074, 791773091, 925496984, 350825254, 804980460, 975222720, 74511221, 39930171, 162726437, 82925780, 762587198, 127204110, 396045186, 810331316, 534872496, 667654767, 995622897, 468339248, 725865376, 169213401, 712289711, 841492698, 677765739, 627113069, 142282326, 114949469, 248842417, 84408759, 937246405, 812253501, 165232235, 845581103, 83480568, 404098227, 713665709, 579761714, 74164514, 711725360, 137546196, 50085277, 450417534, 810578996, 979194239, 303050670, 722387623, 886861980, 716921230, 564519030, 710303116, 67000769, 913435646, 900221432, 309184830, 78959848, 893145361, 246672635, 699852102, 636304121, 467743134, 273726269, 102132554, 904449602, 399248839, 373569268, 873618119, 313141431, 535437868, 167741651, 343193842, 739438719, 222766293, 357319646, 731722108, 531613065, 654098808, 169541354, 419705152, 449199035, 959122412, 572368153, 67233530, 200806168, 421126006, 590739902, 409758956, 535356122, 299140857, 318759369, 484220620, 721059233, 778846621, 409590675, 389391650, 229193607, 951709188, 959501511, 172497539, 383829887, 139008517, 500907939, 721500711, 16016518, 942701593, 705398346, 648534697, 194886484, 76624437, 250253774, 910282724, 975641928, 108060513, 235321682, 296476638, 562301269, 125758670, 415346948, 555474822, 900188737, 40378299, 964730798, 488935625, 179470708, 600783162, 398905688, 480077061, 980275817, 163171825, 848275984, 490766454, 578650730, 963072247, 76282316, 822705206, 914239788, 278713093, 754001285, 475067127, 766999483, 506883402, 99690593, 811837139, 462053218, 795021514, 222733966, 375649246, 818720764, 492891442, 356999488, 67492857, 474452929, 553554316, 330630693, 14536341, 330430202, 832080425, 713504287, 618128714, 602611226, 650461742, 139410630, 132631524, 771967366, 991350124, 177479438, 401936572, 389143811, 85565715, 308696369, 203357447, 446223707, 941847879, 276106565, 469425418, 121229899, 34554150, 662617015, 681154148, 809528859, 701185883, 997852508, 365923662, 598702770, 745323593, 130149937, 113438869, 329232765, 851901801, 697064454, 660628769, 986791056, 784811833, 174761793, 554777026, 919735158, 644407539, 725210205, 116554137, 76401864, 295348191, 252304397, 24417245, 66639687, 413235911, 534925223, 899269506, 498064545, 568390459, 973602290, 459476573, 565070084, 880250690, 581192946, 325483195, 856528905, 729951144, 928634803, 854281133, 439261529, 270800874, 116949404, 43807034, 282602783, 944686416, 349305648, 298665886, 402159825, 552044173, 464668982, 81025645, 202955577, 182479369, 968173410, 832297240, 265915350, 815524534, 484736838, 237367062, 267071395, 683465787, 217883950, 707081947, 821054649, 215492108, 199494951, 896943701, 600405112, 964373741, 135969221, 695429049, 23539309, 525836449, 907594111, 614583414, 18046793, 652930970, 778895577, 559515854, 399596247, 335968935, 401935451, 545243483, 306943923, 279456692, 92641876, 492199826, 77278414, 712526184, 87600843, 194354841, 695721124, 805958623, 189719564, 33069180, 315447185, 775430437, 284931127, 799870130, 694017514, 44409448, 51787378, 778877091, 888586478, 449395949, 530604777, 308192664, 813191788, 915692728, 871096253, 12080890, 838522297, 730450715, 975818502, 191078906, 986464624, 953143962, 898567151, 939562445, 965372359, 706967478, 836647596, 764219184, 5823805, 34147782, 456876835, 239406472, 103571890, 652220939, 271623508, 115191741, 65371242, 535396534, 553403675, 236825587, 919588196, 295320330, 849499692, 243882012, 831625089, 132297725, 317645162, 526401250, 986487570, 53772171, 975725679, 789742808, 57136250, 484708460, 687943884, 412390017, 372624911, 762036202, 128455452, 908094516, 551688791, 198533121, 653555301, 562272605, 202733818, 382526425, 979498544, 317989738, 527239701, 506624637, 238330075, 15857414, 86265493, 574022295, 225243919, 167919207, 806229595, 983538951, 792784695, 86225363, 82062419, 951677622, 918140312, 866099068, 429739525, 148299741, 773663572, 465919755, 839371008, 273288399, 650948357, 928519479, 186282999, 341701453, 700016271, 253899757, 122956056, 583436795, 904989314, 139732421, 912005384, 997596150, 863021800, 500727561, 433861178, 59573033, 21980492, 63419837, 643171943, 726351370, 282643840, 626746912, 442204282, 464725852, 643660190, 127991452, 473292564, 84607258, 699850740, 692980966, 470652784, 549714856, 915496056, 834149412, 816867261, 624398849, 493815024, 29496368, 417641391, 472398784, 258878609, 318041963, 745239906, 40535841, 655763375, 54080494, 470670687, 319735075, 47872238, 905893204, 542633665, 384050152, 611668215, 647145774, 526430259, 475184211, 793691622, 860912031, 202300937, 814200392, 436831594, 918311750, 424534977, 208542410, 176559684, 211518772, 732493341, 271797051, 882915695, 136897664, 701607983, 465569016, 785745900, 180656542, 830483713, 691696161, 382394143, 483852065, 990243887, 200627558, 306666497, 121485994, 656196795, 837502093, 414042773, 555872439, 893727142, 7080960, 460835853, 342181337, 305400889, 925901604, 148448931, 919990844, 907765375, 605375068, 697037438, 915005635, 719552994, 80128406, 105823887, 510582643, 232464340, 26027409, 748433948, 524413177, 52764596, 207585364, 696378820, 74147539, 722930041, 758132218, 582468595, 921729715, 383946158, 211765963, 745929250, 378776049, 701095159, 877975623, 465954543, 138009136, 646728362, 89361436, 290132356, 175092935, 482403630, 39577810, 183525508, 126630235, 695291120, 702003982, 820286735, 949356586, 641232116, 887015665, 199873104, 543657033, 675987005, 627529420, 668685263, 970854037, 806482826, 52123300, 735663021, 431840719, 777437667, 69824661, 566766181, 281460006, 714610396, 247172623, 607252055, 143838431, 106799739, 348905812, 403221341, 210590231, 355828214, 133247136, 354532373, 77212863, 754554538, 368970673, 740964430, 664272292, 978758286, 364939747, 55055695, 158439761, 595936423, 986608244, 128605328, 807300227, 165486878, 127396693, 969324810, 191811648, 849582256, 799999754, 601644922, 121291920, 98011224, 512898247, 758586494, 356097611, 827578757, 932609631, 365336792, 407158839, 447422264, 729868643, 50971298, 768087106, 961388404, 435219046, 667698878, 992929127, 752881987, 249603184, 286199194, 995271673, 392491246, 193829792, 483634162, 434618395, 966591844, 174564751, 891224743, 660544613, 306539137, 385256950, 493342223, 574565847, 3722813, 251825202, 511981214, 429373908, 515802765, 635130602, 114957130, 98327180, 664731257, 217487884, 80827263, 799396316, 676391167, 724154786, 365369557, 913823787, 144476830, 406694830, 166941774, 947960740, 907048011, 772734296, 738905828, 848527429, 165264208, 126588279, 229269548, 747460471, 59593726, 204499099, 399869079, 78737649, 499498065, 516457733, 838094145, 92850904, 39191451, 929478383, 633088006, 880852676, 600012964, 593441075, 825179446, 559474697, 86730947, 104945985, 441146366, 39542825, 350495227, 469712639, 21953264, 917846056, 315336405, 856765505, 954264815, 326414030, 747042834, 338832578, 373089787, 755424606, 175923746, 535399913, 537709565, 258827176, 486525375, 294486364, 208502053, 910912060, 37583662, 181683718, 306859596, 442528278, 466016080, 720668444, 742864064, 594044177, 562341427, 68159817, 77987295, 46982921, 432264774, 126691670, 568844411, 692119583, 572431889, 96925373, 200603567, 556082692, 596379811, 497444283, 29269180, 934360749, 179101299, 726353078, 309840575, 423908178, 663809535, 826443612, 213902409, 90004332, 852544797, 93457794, 461611726, 565064870, 331984260, 548790928, 743948318, 794151447, 873282232, 93777983, 233109945, 470545193, 76680728, 420235438, 508495609, 437541342, 558610150, 504863375, 734051002, 594674836, 256312350, 551949164, 382185970, 883817127, 261479937, 868359114, 344096623, 299211054, 334899385, 305243998, 197033995, 35170118, 811771791, 558432954, 420314528, 507731414, 505427772, 500948078, 685510146, 845372722, 468437772, 273033878, 500447225, 943066254, 138051638, 838575073, 773448932, 652008616, 65318960, 962864527, 915686084, 370221125, 682388659, 729862816, 318748148, 30096158, 374374623, 796133592, 727164888, 146499214, 80943987, 609978686, 654668374, 888261106, 335513866, 457987694, 204523570, 350022814, 372623834, 91031779, 83155094, 711576319, 243744079, 750134856, 765186827, 983918824, 197108854, 480143003, 728015111, 5195600, 239084272, 711622074, 903328048, 812492723, 601320461, 785092916, 896375400, 135033273, 854996, 414442544, 359121290, 731376131, 953700962, 837097284, 247047584, 601627578, 712130989, 565287031, 100470012, 449376976, 306257335, 723296568, 174973952, 70939103, 982061537, 225504686, 254396401, 685160798, 84514956, 354438648, 702888465, 168996084, 791407453, 33281850, 44399278, 770426380, 384226206, 618226962, 834966627, 741617615, 237417565, 867208669, 795437171, 25552014, 608635029, 99426550, 40665445, 438275321, 455098915, 436331167, 573154314, 76904413, 343997103, 81417432, 664882035, 783378925, 486368370, 828872443, 176404915, 565352938, 437562091, 13033032, 178285768, 658016340, 33630815, 334595342, 425622409, 567990009, 493541910, 934033057, 980192631, 878851826, 648114977, 788781278, 297896887, 57826751, 821928520, 988884076, 310177081, 991748697, 667688249, 429743591, 221000634, 823988424, 700408188, 370163543, 695549326, 175026050, 234282458, 678558708, 352837893, 199711321, 253973953, 127840630, 603811839, 359850125, 719650794, 341512916, 39395978, 81478134, 76005222, 609299894, 332238519, 865024809, 642612531, 898466798, 255450864, 489830276, 823520921, 477862327, 554964756, 278547717, 515893761, 115011725, 856087337, 588208958, 545086134, 461777451, 435195878, 752524803, 530042675, 678804757, 213653046, 275938199, 528784789, 474375207, 144618885, 655776934, 235567250, 353726878, 398257838, 508298957, 529725234, 911341124, 918809239, 556078753, 271193044, 405771449, 997811263, 962949089, 269323980, 435016371, 268430836, 820883038, 698614165, 174275733, 81949671, 438854741, 42921728, 673138888, 883167764, 766455591, 376120688, 376586375, 127062528, 621075218, 55041776, 177076596, 173553151, 43190204, 523076199, 394055512, 791743011, 733858245, 564042611, 325482251, 387387385, 524522414, 668752813, 745893537, 635907371, 822760456, 333400760, 484367573, 854540100, 480949312, 295545567, 487804085, 242001953, 622255543, 35101428, 126308016, 812561273, 374647703, 342435196, 40773634, 544712793, 585172247, 568052111, 474948110, 473629644, 441087460, 271572103, 869002825, 891181744, 104078214, 833000609, 570185546, 894440272, 175540230, 293962428, 31821112, 842056922, 760187752, 974543188, 995996778, 337705430, 205453924, 627274231, 235632859, 754746375, 251297124, 701949726, 528798426, 184929234, 830987309, 193542737, 40715505, 240707262, 150089175, 19752447, 843615309, 276592918, 810328458, 265886930, 835351091, 559788364, 722491911, 259619393, 908169418, 22324189, 904377259, 226664526, 203467547, 656838206, 650040667, 343084115, 458128117, 461498642, 646449173, 942091953, 226514804, 95680248, 18866627, 591882979, 866479533, 568252044, 931956173, 364388613, 577118687, 829903276, 448743297, 684106796, 848662100, 944241333, 209273910, 424164156, 578962044, 991546305, 384440294, 2803927, 853023153, 232937666, 356144606, 402042138, 688267037, 23194279, 1503320, 437411991, 112360700, 445438409, 232698503, 275530305, 153531401, 510997461, 684937165, 823944185, 83557908, 93150361, 712600565, 475745456, 601778514, 153063580, 112090187, 402163470, 614148784, 122670061, 269175926, 710344644, 747666339, 950614191, 773639582, 982926258, 440121728, 692582438, 547422588, 121326494, 690986415, 935420150, 924676482, 72071351, 371086661, 396160654, 416346548, 777920894, 650323855, 782777448, 641191036, 375797850, 598291742, 450396750, 44855717, 829668004, 57193355, 83295194, 633295772, 887526128, 148578694, 193150899, 606821825, 636178775, 664811608, 221028515, 115724015, 594722166, 255720331, 376988512, 319337263, 649151720, 583263908, 504920628, 901477220, 518303182, 237076271, 455029630, 758652089, 481591877, 836858940, 119690714, 547303425, 908547060, 426423115, 942682399, 533699893, 115255851, 740751456, 850944155, 163795838, 15024508, 503652386, 787841656, 949293336, 741568756, 515407951, 111365762, 980589935, 311489299, 85327273, 12684635, 823831113, 184753552, 806359901, 943024012, 149276221, 801144189, 767737697, 362880063, 654690266, 361251541, 9865402, 561086925, 23894073, 318364325, 826280960, 294514721, 533856791, 965930211, 852088676, 645424007, 264514978, 656153179, 609508325, 46300137, 318420014, 100916747, 989982808, 751478390, 671344419, 286451165, 486286074, 687581249, 146038264, 344644268, 636168201, 690616473, 680852415, 863821590, 755184922, 395449691, 433524061, 151707148, 817803626, 28041870, 583051093, 221914898, 448463829, 362266656, 515030717, 539361567, 78865948, 417859428, 535342192, 860499877, 181598557, 143588506, 143376787, 165173155, 838118155, 776906074, 945177919, 889508951, 904389947, 954566174, 901022359, 207096526, 195899511, 196122948, 576659958, 178189273, 763961280, 326708577, 490939040, 969903924, 307803481, 894384219, 356960650, 819718506, 425112772, 473525026, 360958876, 296019058, 133839721, 101651876, 359390834, 760455233, 483728961, 882421214, 757465298, 188517428, 181607737, 327555932, 17507489, 97701812, 785558214, 984867524, 584943738, 31295327, 199948053, 332592823, 220894963, 71130744, 242341656, 489839677, 511050126, 350650646, 637263219, 653525748, 144773681, 422661113, 467508967, 827591027, 861601148, 881676862, 516805242, 517003430, 300923339, 104956444, 464379364, 804681092, 869951580, 570555843, 474865218, 694309979, 739830442, 736796345, 247843244, 418096235, 681274684, 611932557, 488633740, 260676365, 713948051, 504256309, 644084008, 448843256, 554339261, 710069679, 794710407, 374969436, 464278783, 114570550, 784829991, 803829696, 510710736, 333330804, 890499441, 326328748, 768146668, 4752899, 441781052, 703549541, 899762560, 12305879, 553195719, 229228987, 235820497, 12684098, 772730384, 121743518, 936686235, 106135750, 250474096, 83822731, 328677288, 345602475, 985239183, 374285555, 945760077, 993094967, 893277883, 418117356, 516358996, 35620139, 894566361, 415433224, 321573239, 235899112, 35452009, 461551075, 351864648, 410345280, 613985171, 93094370, 718314576, 673358431, 562912678, 414851900, 736333689, 6820479, 94688530, 479120767, 675700067, 759441194, 540064983, 671411613, 760590174, 539557215, 908087469, 822560944, 744461577, 804055010, 565084465, 182126958, 77664423, 617870233, 804498892, 804180756, 138985059, 413472002, 976907264, 345458243, 52214099, 511176539, 507481083, 393545935, 842213394, 329595056, 299208581, 939312115, 181012195, 548022929, 47041649, 965204755, 903512842, 387558178, 336270627, 262265047, 965726311, 415141400, 524279667, 569675757, 279511895, 964476291, 932244004, 146314971, 541939947, 310757486, 99621413, 903089394, 235259873, 549447234, 592326951, 519822672, 38585132, 226587394, 467972771, 819901622, 311975456, 428134833, 193651703, 379699502, 474612801, 487598248, 492615237, 700506525, 852192662, 142453217, 464055221, 583246997, 475234324, 435509016, 160129324, 634723857, 40831198, 48581821, 85222388, 577190509, 288024618, 404851977, 479896585, 601647271, 75225968, 587480986, 260753902, 18391938, 308865931, 913028000, 272699827, 768101142, 4493858, 258230321, 160775940, 738821181, 857483667, 505955671, 424719336, 269788144, 409772868, 683207996, 711256329, 414749166, 101737658, 596306009, 348622628, 872693418, 420758121, 484525033, 922415369, 350278438, 921807369, 191034841, 910394331, 901486722, 48661505, 302079026, 519998875, 258803948, 907021312, 615779520, 420305775, 447373603, 223531996, 28901727, 608634170, 454156141, 703440978, 841288018, 929393109, 334540806, 903804529, 963823373, 904424355, 619910491, 963028720, 542613082, 461017485, 569574711, 978238880, 513594795, 521966672, 411240745, 910302253, 329526718, 463070224, 118887557, 142056280, 304389448, 112508176, 780106587, 399833155, 128363018, 243386202, 690702672, 614201056, 765306180, 322117839, 586090468, 163776920, 468899586, 619668948, 773694517, 929714795, 889558103, 198828676, 386497097, 652890008, 767993970, 543835584, 595040183, 763022772, 778441935, 392194501, 825180595, 326810236, 815414594, 772767078, 501195902, 903716186, 353074653, 347936095, 504969552, 567430618, 226160123, 437505876, 47452890, 593184859, 477164560, 287959899, 457598270, 320283258, 4777425, 794093045, 229585987, 912202172, 966351027, 82165233, 537395682, 722803126, 797173192, 535508282, 88345641, 806318405, 58506395, 371460896, 604252739, 482653125, 145928045, 53068384, 77908914, 541680555, 466540226, 263711119, 644074162, 48558495, 31831631, 13341009, 223152816, 605019260, 799714730, 180345540, 468847754, 353490894, 51975830, 708399563, 814843143, 208107516, 94571753, 6174280, 25254715, 433191093, 292197020, 950988360, 29748914, 273022720, 441571583, 224004517, 87961229, 772702244, 890678290, 856509599, 78637334, 80188296, 258029003, 228193787, 456275748, 426296437, 303601584, 176644225, 42302475, 26088586, 388843605, 243446108, 125430219, 855998762, 688519122, 321941597, 850463817, 13780401, 114805132, 508290808, 829829045, 472795313, 138831384, 635659833, 632697270, 659085313, 199448879, 369245614, 449953626, 682221875, 834672652, 522731319, 288380319, 258318604, 574364300, 178965170, 550606084, 947608823, 25092129, 503727836, 377102607, 586943472, 4419282, 359545718, 299407369, 568421548, 870454349, 129156569, 196125297, 660135967, 172961991, 771701809, 148235335, 742488418, 903806653, 74683019, 673161217, 777438263, 294136368, 143898059, 123616064, 977284388, 190119982, 809652849, 828372355, 287527506, 250925125, 198670648, 956934198, 242818927, 282586827, 786854539, 286440451, 307139033, 586918599, 169259574, 252379988, 901364558, 69819741, 76402739, 789422304, 669158391, 413892551, 254330638, 392053201, 636666052, 52019027, 813473214, 193049063, 429067035, 327611428, 556297208, 473387425, 332504115, 21465818, 268260366, 351474304, 700753819, 218728019, 852851004, 871912317, 228495598, 471681050, 799231230, 79961435, 368943233, 136136209, 347902935, 254773982, 314447422, 493384822, 793293168, 269319785, 226806473, 301588484, 417014072, 402358443, 900700826, 285607197, 754184502, 328059099, 855254381, 586814343, 536159357, 217650373, 167111917, 365941787, 938639105, 861925667, 774776148, 520703393, 39464693, 374290937, 105681522, 169291462, 741040590, 82379396, 138755549, 52017555, 508401403, 695240096, 502742533, 568356540, 668030156, 867089001, 445904124, 472373963, 599865004, 684296206, 580620135, 326609862, 839144786, 693160414, 356864396, 229439596, 225995429, 209407633, 746766912, 422920252, 303576929, 873034520, 91150734, 352448993, 945685136, 726399961, 942241844, 406893942, 266833653, 470862239, 652515443, 164351143, 587557676, 392109888, 354500531, 765934430, 478557688, 484030405, 137520913, 913234485, 972588429, 816000138, 985020607, 388503028, 72171009, 617006772, 235950846, 796815627, 884683197, 334425994, 547191594, 297871284, 633889640, 86598609, 868686317, 973995855, 52177977, 525198260, 238308116, 272731878, 888087641, 369925872, 491971897, 38404925, 804534908, 504157570, 707127167, 428163175, 663853032, 560865670, 722850310, 543906991, 472910086, 348716425, 951473657, 331975923, 175802715, 589348310, 444218307, 959518840, 963588840, 180580915, 633344382, 701132938, 159938138, 394570401, 549999851, 363469980, 578656800, 444434919, 965185553, 671169345, 550532741, 139510319, 183304993, 273608735, 335157876, 56082467, 886991145, 356376144, 802713630, 414825486, 846869816, 741679627, 692909570, 490558147, 538536379, 772944168, 767714852, 995319900, 675639167, 814531620, 17107366, 909362352, 40926086, 377822049, 76934897, 635019720, 199697949, 229078127, 460793371, 472054636, 77557396, 508380116, 678969391, 492631256, 388239106, 928066314, 981054169, 423865803, 672596015, 70180356, 170390640, 448616501, 542199724, 803913080, 484805319, 38396883, 145013345, 169050395, 24191695, 202285031, 949604396, 491781960, 82609439, 467570862, 59716704, 998086345, 340362, 285030493, 541947112, 971109351, 585465504, 905791888, 143599655, 881310144, 433185933, 565532336, 398945279, 884168897, 260212042, 681936225, 343964754, 452120265, 284347581, 568172924, 719770520, 442693322, 284553870, 486795292, 17990468, 36135741, 543721336, 11528306, 897424175, 109772552, 150309725, 708732385, 81583740, 925502134, 553625013, 575323725, 597750177, 438901574, 233944849, 728153332, 781216264, 335244259, 360829472, 33199463, 132082592, 307675076, 341300314, 660867637, 342609351, 369697047, 83074131, 389114721, 947908148, 218215732, 197942028, 70093694, 799221173, 827841950, 661966233, 821630774, 112890664, 34639206, 706282171, 573886983, 535266285, 515799545, 838045995, 748981766, 320616976, 536819702, 564159349, 60512268, 806390238, 69577444, 355853233, 181087641, 507267703, 336865208, 901130790, 853754846, 79500084, 147424379, 213720989, 715543044, 353757012, 273424070, 957364877, 509346603, 86784928, 740982752, 972821611, 392755145, 536901334, 589721017, 981259430, 254988232, 196300628, 38624199, 518421610, 729651195, 328218083, 756652965, 943219188, 628558466, 703786135, 658539574, 492765289, 485103183, 973485645, 857505391, 409540523, 591846253, 48017028, 610212881, 784623153, 635945293, 355435730, 739402537, 402066637, 738832821, 190783013, 445875224, 487909045, 825810316, 517882925, 560692208, 16342265, 888627046, 529310558, 595220632, 142905831, 946558762, 364494758, 228542517, 821651352, 904735222, 111325925, 850777444, 773137358, 924886809, 69472470, 822947637, 816933794, 543141541, 449191612, 128951812, 33655607, 765068202, 430766199, 109808989, 398322028, 924937651, 24006357, 600284081, 334963799, 512433274, 213491101, 959526200, 127693362, 906727430, 928710977, 760972364, 542649546, 288975699, 587374778, 639802805, 659973285, 691675116, 32976106, 133066664, 881991846, 566446165, 659049447, 926738467, 667926468, 974353539, 279020775, 355736927, 729223406, 645409365, 621215986, 71070277, 682587553, 505825980, 561262261, 95708794, 277842104, 189185758, 729867673, 354903785, 262256616, 271159304, 363427572, 924068386, 493542950, 481714011, 433236196, 920351827, 786050958, 605591017, 367069688, 54752071, 433335042, 627981052, 894812913, 159493919, 767709847, 893845571, 49085418, 535982818, 664730138, 257977288, 796043058, 210453279, 801005809, 790293421, 270839688, 360691442, 427217772, 239588310, 397950992, 874932713, 423198514, 622376881, 890628400, 266443907, 910126486, 555633106, 698117776, 949089636, 725020249, 604801532, 231094776, 89204974, 900036206, 425310329, 312167475, 710011038, 630746374, 946364690, 113954374, 444596855, 293993753, 682773779, 918962761, 714199054, 39200306, 610070640, 239628239, 178028074, 6836809, 282307280, 162912023, 598428350, 158004875, 637872, 32522904, 697910548, 463366547, 334583524, 566819918, 397933581, 893697031, 719229632, 370897873, 941649605, 225978111, 754944871, 368635249, 419155091, 257981553, 34780560, 116655954, 404104665, 426123708, 585253122, 158911449, 46626331, 742749954, 660738343, 204644848, 706394075, 878664453, 952395113, 488303248, 76036922, 284492405, 32983592, 370339821, 932379162, 858548598, 403978797, 640646625, 566652996, 288439470, 859216028, 935956411, 354513639, 111069951, 769623075, 124268059, 649836723, 839480501, 721218322, 970116536, 967286770, 888722335, 651746302, 173982537, 732434898, 489718141, 20281886, 882121387, 56243795, 126723441, 211255018, 16348039, 385390304, 608140641, 541124692, 105713299, 463751135, 852459318, 206595851, 759426895, 263167334, 461969846, 7758991, 58647982, 893787344, 359281703, 518337861, 745305826, 353633385, 788850379, 922685929, 848148860, 208185794, 731023079, 106791811, 97694471, 925892643, 599638341, 888478789, 788036804, 81382510, 614144909, 741875724, 594446577, 177138225, 712595207, 505727289, 199021756, 128999060, 35369888, 144644468, 949593973, 449376220, 886304859, 709166986, 922223221, 748927003, 457698501, 397056865, 849800035, 71742894, 768538780, 46632503, 41885636, 606957754, 909351425, 517686364, 6608708, 651875924, 140473007, 414119068, 423318136, 379390577, 867063528, 794490979, 637912860, 444997274, 717793233, 988914228, 900109060, 114417250, 956231134, 892792340, 469054895, 997755770, 71374155, 304226640, 717160441, 207140442, 851013975, 753794664, 69008688, 981297761, 585487001, 520924273, 485103149, 711875504, 721900092, 527004535, 892452746, 652271053, 785063620, 124142027, 471381674, 47892280, 849458704, 57852187, 498858750, 689482426, 961886682, 739263847, 855648001, 789183773, 337079103, 785201822, 78929894, 243253319, 162087579, 624572869, 159717438, 49651298, 271610105, 820541932, 922842301, 780293046, 157408839, 866883732, 469975252, 186280988, 461367378, 778257880, 194351794, 925688448, 913046896, 43379038, 100965924, 135818603, 758861205, 972333348, 481569544, 24382498, 160605676, 299531736, 173778040, 893725093, 439385614, 828653874, 486616080, 739285002, 559453560, 401911556, 405561437, 843131049, 934533984, 386393362, 134314934, 94170006, 465643993, 35740197, 478446310, 862117884, 518658717, 821566946, 123916340, 238265509, 25773123, 842187919, 513116234, 900536614, 789396659, 1388419, 929383494, 395492710, 585858401, 121185057, 673225033, 393893638, 104888800, 377301745, 339920232, 953445224, 633646085, 5464659, 789098268, 32528730, 495651335, 402047945, 10570062, 728183857, 386774281, 590892569, 307398794, 128410962, 474298776, 91037099, 314051517, 154744987, 725188978, 418957513, 735348342, 527255587, 709966257, 419686049, 335295941, 553261840, 351571588, 687339243, 869136414, 701558590, 179114438, 206659107, 380054387, 122377977, 787366903, 733680437, 799049847, 338252974, 452413425, 953378717, 114359397, 807310814, 990084252, 255206933, 459438748, 212029248, 470759596, 773020866, 971158867, 834803572, 201274482, 287750745, 118306122, 366580171, 607230191, 418230177, 563454879, 395371099, 283262794, 633952788, 76314731, 261898327, 893935719, 880652911, 800163721, 842920225, 282393960, 295818278, 327523996, 881431110, 246090626, 154342461, 389365879, 955304821, 980997745, 799235879, 206760279, 202042221, 303867237, 280070165, 220018830, 26241097, 709942196, 748827262, 628802193, 568539709, 440826172, 145144787, 947436562, 144894679, 198309081, 1535146, 587603451, 211128327, 118595531, 59716801, 418075161, 374497004, 377282645, 920811341, 72900480, 962199639, 669735977, 597598108, 828512520, 949376111, 934418654, 553519733, 46445880, 599124889, 310326571, 569400823, 412768797, 116031456, 417212283, 500925862, 836824225, 500829888, 313113653, 126107707, 850727821, 762174873, 351533787, 601349094, 137810466, 794323311, 260900154, 4816069, 314241312, 234568834, 69208692, 264000784, 857679904, 587616460, 403220782, 720240063, 65465390, 638236951, 649881073, 298562798, 38019381, 36718065, 547907078, 378704457, 104827666, 623757353, 909501510, 293331921, 816765188, 598559041, 971947887, 367639960, 729490827, 743751203, 134825604, 333252005, 964862858, 457773173, 436854671, 47073576, 415203620, 208060848, 896474460, 82822489, 658401811, 226189795, 971055005, 434182514, 456189685, 871817103, 875618656, 867237009, 901235319, 830246400, 767477202, 825340459, 433111051, 613631651, 29177784, 598608757, 582424864, 760538177, 211076800, 589107761, 141171174, 833094392, 79381386, 510386146, 106097844, 825743334, 27858428, 793645206, 817068736, 518741959, 466844701, 411098406, 445473675, 904658078, 759790513, 118231348, 879711771, 255168442, 625924046, 596727404, 890664932, 854016470, 693251926, 280708341, 712139894, 521790704, 719615153, 527803715, 109265859, 449989072, 169374771, 98761867, 154127813, 610602892, 219398068, 33771404, 86420531, 845839412, 811015685, 363079809, 480172512, 466981637, 459342250, 495415793, 947776564, 86967301, 187252830, 798872428, 393666503, 360855289, 886141887, 778017791, 555635371, 823913291, 99140859, 557519791, 311364956, 603434056, 93609147, 907010573, 89431951, 938728389, 231541679, 107485727, 463206135, 818451997, 523302883, 103678545, 421570217, 24110609, 825359763, 574416217, 317976728, 909655056, 754360032, 631708614, 816215954, 525345786, 252635263, 984342266, 15622360, 583844605, 932991027, 469866798, 327321444, 650023606, 758825579, 906582273, 271682428, 86475328, 196601965, 348459205, 336648079, 102266083, 295641677, 483747565, 334542904, 757545532, 559846474, 197811824, 370781010, 181220327, 239219663, 293659441, 321086434, 243871442, 120732057, 629339815, 89368644, 746229331, 143981702, 609663320, 74039451, 709166027, 628653187, 774401213, 928782340, 903937924, 790578762, 572380726, 714516476, 197118121, 768444072, 835401126, 6090648, 891546175, 608362906, 303223816, 742492485, 525019598, 165577477, 852262982, 414801370, 695337754, 789494690, 706231006, 414007105, 116246055, 831495576, 936207145, 822494296, 732776651, 319829519, 497022098, 376708448, 428517826, 89460360, 972362919, 121831703, 717281947, 602328922, 301106022, 314807373, 146045422, 758626005, 932907843, 708716082, 922725592, 444813086, 387119552, 877575987, 717401012, 772353162, 817693158, 616611769, 554030763, 782840428, 528084321, 357486650, 426919721, 297959348, 942093598, 587467920, 474315340, 352640273, 21957591, 294737493, 680146658, 583680260, 677624831, 148121069, 428209486, 873391020, 283327909, 585705446, 754303037, 910997722, 510198568, 730632801, 691217932, 355671732, 984030908, 751680153, 694875933, 787055580, 255721681, 938070774, 862782836, 434509027, 130144994, 105561168, 233151951, 256207645, 101095327, 851645542, 91750311, 575252507, 676179280, 392720240, 592535085, 844992469, 543067281, 940731834, 695069248, 658597494, 549309743, 66883324, 558266142, 68219413, 497631445, 854093793, 300828355, 246123465, 733777211, 620096029, 219205492, 438964104, 899157043, 748104173, 390107906, 714125894, 601367910, 809307860, 181713406, 504673560, 501935074, 951629768, 301224900, 604020161, 559132737, 831158733, 44140205, 688926934, 564628931, 526698296, 779262075, 711473740, 896312190, 192751478, 587236077, 666631302, 201262149, 198006437, 55181281, 904910535, 311786275, 249247090, 230808069, 346364892, 536423012, 42309966, 377962031, 497784259, 199261893, 503640199, 710904265, 637974071, 52881385, 161171296, 813644677, 731360637, 78043037, 63399665, 388466807, 20231309, 374822097, 554789722, 13882363, 616232448, 599132872, 822072832, 524955817, 465923364, 33046904, 232063498, 526633256, 992693455, 663727820, 387168709, 985222449, 398089676, 985679194, 76790811, 489720969, 267956940, 240123191, 529924101, 164381175, 493838509, 652613164, 946962788, 199716895, 505244677, 101422851, 116315883, 136583890, 756608636, 200314708, 872973852, 609661398, 240190097, 694981547, 458440554, 568094968, 688556179, 168236605, 175733639, 1220181, 113289722, 647532992, 865130538, 546208938, 791042390, 530625084, 807978488, 309856264, 39706647, 774213666, 700373742, 369148532, 260328077, 45102508, 292978388, 420505469, 968279475, 747615225, 259056661, 960760506, 837793483, 198373074, 234336867, 125365076, 103002760, 934786172, 324118748, 14300635, 201749599, 298231832, 563427203, 865341841, 945553065, 13046047, 662428340, 356422384, 162706242, 460019551, 7282509, 799176423, 957870406, 539487360, 915659472, 445511908, 62929722, 846588862, 377281576, 993527777, 800328447, 194466984, 341932079, 960428647, 711921729, 582423640, 400131535, 122233140, 619259396, 857789007, 926223469, 899044968, 520841421, 442005150, 475688398, 182905705, 713945453, 100092721, 413086578, 241031761, 420425017, 349138821, 551492607, 199013276, 970737250, 155182733, 521748804, 338816046, 14865167, 52258081, 629878760, 181377365, 808468122, 774191666, 758767208, 649178167, 993786604, 214132971, 801239515, 643605894, 824369878, 394582594, 781722816, 977916749, 938440575, 283154416, 725412353, 567654973, 935663855, 424065958, 470040913, 8152209, 692858410, 740503007, 811875055, 204945286, 253249696, 196474113, 779013911, 703223446, 595967374, 430363284, 347385853, 380237620, 478406944, 677592975, 371450969, 35374095, 592856615, 733163702, 881702106, 558499111, 100756413, 268517838, 202356859, 639678133, 470452382, 546755850, 935772202, 571776399, 805592905, 662613516, 164934003, 518644011, 649851148, 854163899, 566541899, 609596722, 662386245, 719221945, 45995372, 585028396, 664444925, 761638871, 677629875, 266883500, 437296882, 834497676, 781390174, 512357567, 133301826, 827756126, 405004049, 417594894, 366893771, 68196367, 79058770, 790203288, 26079495, 201722606, 418000807, 460529106, 662297662, 787454450, 72079092, 135317673, 458780161, 266472564, 695947984, 569484028, 153579183, 753340261, 953646479, 517677859, 291098603, 394259185, 988402481, 498794005, 538801873, 199497166, 918625085, 954078320, 164122148, 627170482, 474921424, 754274552, 583347152, 325537750, 485482690, 275765159, 839825942, 309472035, 937298580, 294503176, 885509501, 780880094, 784995952, 262291263, 213603390, 819173970, 443095810, 158808953, 534633887, 788996628, 938780979, 623278837, 316410813, 847941071, 471857574, 163678549, 717047381, 203697832, 857646074, 796411545, 687665976, 636902204, 496914582, 827325791, 490624131, 347072940, 174910196, 752424769, 680554951, 148719082, 937510044, 38828640, 305834935, 925517368, 107195630, 686733466, 796334311, 705048278, 196489068, 394554068, 235409705, 689904676, 198569202, 128285478, 270700933, 346655284, 541397581, 622283745, 101202953, 148140890, 561640953, 570021092, 7380301, 869192895, 469022506, 750222242, 190604932, 148420813, 364729394, 474426173, 176484207, 819860662, 294016618, 82869975, 325976581, 693413205, 904768354, 942416760, 98610386, 525511141, 559281808, 352965332, 420398497, 977732182, 97802729, 774621807, 913260590, 379541131, 356393105, 806441410, 53606422, 461599015, 310191384, 567657828, 527891225, 133807316, 876970765, 768963442, 110748181, 416959217, 319541524, 562946385, 327716630, 387415128, 923104468, 799074126, 556566703, 461760814, 76375508, 490105418, 496844873, 241881480, 966748368, 698522105, 742119772, 566169784, 859778550, 164901085, 826068742, 442348717, 820841569, 1455491, 791158125, 871406763, 541733574, 621648033, 54608516, 445118255, 513711985, 129406863, 249545845, 702959154, 535821806, 803304159, 805193983, 219046615, 91487259, 220079678, 631929113, 79554634, 117600005, 184770689, 304184209, 460607592, 447793307, 210831187, 748901176, 303382786, 889179937, 335985341, 748509020, 688657521, 321080629, 535876192, 164592882, 800050708, 456391596, 938049994, 319507649, 606647699, 799456697, 970839642, 300277932, 504586587, 100507192, 996079342, 848143751, 563647544, 540217486, 441505005, 21891902, 378010274, 12050489, 832522830, 834217655, 248675069, 486263062, 640526913, 367139941, 258561754, 465798541, 196382512, 581062471, 628133181, 179925274, 219836472, 523427850, 155417256, 849213439, 273414189, 958023916, 13422210, 564540225, 963542038, 901605515, 594114111, 9544982, 304428477, 660363164, 529877761, 290933139, 246278618, 699666390, 108545848, 133513114, 142877953, 696147054, 138915231, 869409473, 132677183, 194932447, 317075464, 846731884, 736338285, 944737701, 793184691, 688691019, 180093369, 49844659, 839552405, 758391557, 311490665, 957158413, 955382760, 553682645, 491717024, 28008518, 592870003, 306713745, 488469032, 724942509, 244880981, 982065017, 934958088, 507028296, 677626364, 373288406, 643418160, 485821211, 332416380, 960671161, 290790300, 662700992, 126017468, 874886340, 265110161, 270362576, 552930203, 552450013, 39994869, 184081046, 897969809, 24103847, 248067816, 481422041, 52215064, 860419583, 612710146, 435587579, 247060594, 554150824, 259152707, 547341990, 451928712, 643722439, 915982742, 615652218, 514296523, 647955578, 496719429, 729985910, 970235598, 327840403, 308218223, 97165965, 218774810, 916102254, 972328093, 493523639, 954687298, 859306294, 819753405, 646863036, 641133005, 338404175, 869907511, 740860296, 35622309, 705417149, 675724081, 509419784, 303279124, 393672293, 596107541, 226030706, 497383949, 465443816, 515532163, 34622101, 352913699, 788785413, 351632719, 379759099, 900323948, 309874018, 540321031, 165207019, 35380740, 973564907, 210389371, 393507297, 281955478, 817063873, 939861666, 414979549, 865324539, 84329130, 538752057, 158897045, 576529053, 176917317, 971698490, 331574616, 506407428, 547602731, 64583988, 232475036, 215211664, 44555951, 733460622, 797553515, 952852911, 798435119, 617509855, 436145564, 727473793, 563936124, 292101868, 108925386, 204947388, 681869659, 881580975, 83121768, 456794909, 47615809, 420940017, 553175566, 382262137, 575397109, 676640889, 389815123, 705276166, 837173134, 71572574, 213741855, 970348556, 720232685, 76734562, 158306968, 433109622, 970016336, 447674689, 432676697, 751547131, 74292964, 810994396, 260839582, 734619259, 300651487, 893849368, 959560232, 431543629, 373353305, 379904948, 338284959, 629721279, 694572334, 675282852, 698272581, 846580094, 423053388, 96760157, 199165092, 759793255, 133587707, 413803600, 552665942, 867160847, 507270380, 129542605, 126372565, 574206319, 704722681, 734746798, 884827260, 550896810, 115094929, 95278204, 420928392, 184445703, 566828532, 823373316, 539093134, 862282952, 784682016, 663570671, 197547628, 200316508, 469603603, 776293127, 291151490, 421524653, 26302952, 706582907, 788990808, 817138605, 574994188, 449032588, 34844254, 880725721, 970070732, 795729285, 11838295, 458171118, 306824451, 396259422, 764121286, 695625765, 849572140, 765366948, 179970772, 743404971, 939201819, 775577224, 196855348, 340654471, 770102794, 536744692, 554355992, 981725815, 411065555, 511965430, 569489942, 2625913, 960148293, 817420459, 986785201, 932052507, 291071433, 83498580, 69192615, 930348256, 603376802, 164227587, 110108194, 298837586, 937592714, 214871269, 341731909, 347666294, 283129772, 398415667, 523011316, 450362028, 841228030, 313309172, 849554118, 357870141, 854703783, 227435612, 312377125, 86136454, 865747445, 990374270, 669159614, 586633352, 487712252, 582213730, 246357210, 998178689, 956664134, 232717550, 114697754, 371182785, 470692013, 269476225, 759446357, 149740861, 761889023, 931581149, 50163958, 17960114, 571873800, 670561514, 403625015, 199448206, 456497226, 406870020, 685131146, 841728607, 125834500, 147128250, 945117469, 946952359, 510548492, 53964921, 532655844, 258011498, 440449949, 689186712, 796892790, 363433315, 920573280, 230665927, 565454594, 543819673, 733007729, 317299509, 549149713, 516212140, 418606298, 546644494, 499632433, 689175446, 181932341, 591504121, 431972342, 46668056, 787880624, 293010073, 890743533, 839992989, 392328936, 274243944, 285845079, 948108457, 84168476, 143694299, 994446062, 347350111, 79872177, 582831071, 307823801, 387644371, 484224821, 527767088, 549479604, 66467530, 841722048, 185298459, 807364772, 983874386, 409017493, 938833309, 53935120, 997861993, 242981688, 608478817, 56862671, 151780254, 974049929, 927589512, 166414267, 85070176, 466606274, 100264965, 321495166, 114575966, 360477148, 743251632, 960729247, 107694745, 548033993, 814210987, 691132738, 917964809, 472975431, 116683662, 251956343, 841930988, 480347966, 753874379, 113101769, 71978583, 356885303, 218356115, 324493242, 638289100, 849535561, 660786293, 698518825, 70802793, 255949319, 612435986, 546756044, 733106441, 558475602, 320472400, 11984696, 22346175, 885592293, 779255864, 460358212, 126231717, 591784661, 941400273, 545429533, 666696599, 789639249, 947812479, 196654624, 65840380, 70406589, 10386268, 59233193, 404546783, 588613530, 2125589, 861959440, 615168117, 210280411, 531288824, 244073400, 422966209, 876920138, 216532740, 631329910, 141897207, 57774843, 138595075, 317099611, 902862955, 136102899, 629638434, 488607976, 178685400, 329277104, 265150829, 994545475, 603909785, 169391679, 867026815, 921646907, 470515677, 325817591, 970305738, 110625679, 897249686, 829313947, 89746488, 979125740, 324207826, 386414098, 250337763, 633238697, 631353420, 211143222, 485869379, 503105683, 538671260, 465485320, 819267075, 911223095, 116372414, 893831281, 696841454, 24815847, 410268965, 158331909, 236391618, 697852618, 822996669, 655988601, 315619548, 546469297, 730900157, 238671761, 988202068, 773523367, 496926478, 325724953, 312448323, 258648401, 652389906, 39784897, 838023150, 423616932, 397614021, 203357321, 592453829, 573332903, 697453869, 789349026, 758951151, 788081726, 936183742, 478595021, 440495975, 665779687, 2665322, 820352328, 248734225, 52769905, 9181872, 291154789, 377296899, 704935380, 379600196, 584847324, 332494770, 91541481, 511132973, 328806125, 672707203, 52505921, 836298620, 507066953, 822262939, 432360855, 288319536, 184449166, 942657096, 615792033, 522376716, 178543107, 100661346, 355959261, 675262594, 35824068, 694407863, 605142635, 507457958, 525448962, 746322361, 293283966, 446095319, 149661758, 58836706, 434594508, 339535429, 155581992, 293636206, 995358821, 747863199, 70008511, 799564389, 501566858, 758616424, 727786696, 244757269, 767074751, 644489693, 493887083, 751793837, 126226218, 858780920, 134333790, 283501986, 770987604, 278766521, 622929853, 765820928, 474490140, 323737838, 440606333, 414460439, 557824421, 224200424, 830698783, 528478555, 361128560, 497015320, 386465070, 459938530, 545096572, 310199675, 599922005, 380993129, 185999997, 904760101, 742171155, 836158821, 65785264, 691030307, 277258701, 601360689, 76686064, 148612613, 506063524, 143850857, 333559059, 691394582, 568837349, 203955989, 515673896, 620019647, 631388663, 139212708, 627812145, 309854552, 528199979, 661816545, 440738455, 774296662, 726926153, 86558676, 195545890, 284043094, 109095216, 847617205, 297803155, 208757654, 539794265, 138700399, 426600774, 17881806, 364451183, 559324361, 979728429, 829351809, 362566758, 464360029, 8400603, 49553546, 922875587, 236427555, 406054921, 235817239, 711401153, 146620624, 649504733, 423522073, 613722193, 353823775, 754526456, 8178223, 61870138, 301694708, 759896695, 310959460, 992185576, 937055956, 156014461, 416824245, 976492566, 233698091, 273587283, 271022317, 826398586, 417475352, 520030350, 552743876, 7188284, 606244063, 858361495, 555948741, 882535599, 493419510, 944075973, 983521296, 755920108, 288927741, 544445549, 592986154, 93023664, 199454058, 1912967, 308156709, 323490643, 229349822, 257495074, 277813862, 966284846, 268792035, 935727432, 502769987, 605956050, 371332590, 423907694, 404709203, 58330295, 478488252, 187976412, 159283532, 494048876, 454684571, 631260509, 88489502, 785190162, 563479062, 554343883, 333048258, 910478685, 828588715, 467462624, 887149377, 311778489, 13959388, 254861847, 996469213, 848639687, 811794649, 675485452, 132542953, 361463919, 587484602, 953897628, 787211017, 760841095, 250759235, 658344733, 415845786, 771789626, 192057294, 46845458, 60668268, 899835836, 990801126, 410432443, 110701315, 831582354, 995567278, 358761351, 121116441, 644562653, 305554762, 105653331, 191425126, 181071171, 583306423, 587126975, 360894748, 7897971, 958061734, 284468235, 310838854, 554543972, 53450653, 937494034, 212164003, 702725479, 827993860, 129157226, 258414415, 608403367, 82518988, 754375338, 632639966, 200097849, 827055372, 441374973, 392518350, 258827968, 51378503, 643571862, 658346953, 299129105, 966086128, 833116072, 621032813, 460388648, 102659002, 458777675, 955389623, 982324502, 490842320, 247530073, 165918302, 867901871, 236780844, 969484538, 263385558, 534354382, 574252171, 4092391, 947095725, 826879583, 91182301, 682460010, 343315583, 921783749, 118980547, 121591130, 34255516, 158310457, 875210223, 322065360, 638756701, 650410301, 339173561, 729903007, 903133016, 314807811, 470820657, 350040188, 444876429, 287122083, 436050979, 345794500, 938915397, 462973462, 512901658, 473802094, 854520838, 864440996, 674009225, 204276539, 862426581, 485032556, 304554269, 758495126, 417715052, 172803828, 809246742, 901050820, 297299287, 819474497, 712365498, 416528376, 84258583, 726633578, 563614181, 689983172, 782303452, 117823714, 881227466, 357018288, 400254369, 268072611, 183602734, 159023411, 803409037, 566181867, 810902154, 484079845, 476494072, 578691632, 587541615, 874760731, 965432075, 173529552, 778085332, 171765099, 60232118, 680196124, 35550373, 641145932, 174152156, 41051607, 432230788, 389943854, 169227430, 419421226, 241948078, 522640060, 633263632, 792874254, 261156648, 100584451, 559183864, 64161086, 751963671, 497308079, 238146807, 405400121, 878154890, 183944353, 927209310, 102545946, 736208937, 124764022, 977669296, 186192887, 975410548, 949138057, 874832246, 61047658, 291645589, 634118022, 912736040, 40527217, 863167120, 799494398, 794983902, 359842924, 188210160, 613417352, 187026649, 373009401, 29266790, 189175301, 778237326, 169184672, 383385666, 953296260, 807526940, 635007526, 957237510, 303664778, 748159364, 637285945, 638501664, 580634970, 47888128, 833389323, 698517883, 349063565, 794910738, 862111028, 526900363, 347180511, 466331961, 868280005, 26686433, 553304053, 98235972, 208726208, 571920178, 941768988, 485558455, 348453755, 294337910, 268931886, 566818374, 848532953, 922935872, 300597012};
int main(void) {
    int N;
    scanf("%d",&N);
    printf("%d",A[N-1]);
}