#include <bits/stdc++.h>
int ans[4001] = {
    0,         1,         3,         10,        37,        151,       674,
    3263,      17007,     94828,     562595,    3535027,   23430840,  163254885,
    192059216, 97183539,  384727153, 211932162, 665362848, 415709078, 654959364,
    894067657, 839120000, 627072923, 586774033, 440165789, 840647542, 118441546,
    505992682, 607243387, 93527420,  378847836, 948139661, 770183251, 365355663,
    989344183, 548640276, 317289217, 997901123, 159164073, 843138878, 532150136,
    738186543, 903861313, 682196381, 973969945, 132955760, 252975343, 448800686,
    260473966, 172364334, 974776377, 897990701, 517201033, 576838003, 99444281,
    227668527, 276751933, 925606182, 183971202, 872834804, 675567482, 485151063,
    90425806,  573944639, 319383684, 228218188, 853465612, 413776522, 234312776,
    696953174, 561359388, 614568659, 310760116, 308156021, 643857743, 130527569,
    21545623,  861347933, 160875480, 265384023, 880663120, 642768069, 283279971,
    101569565, 642645431, 549146203, 962813505, 943728849, 409246814, 285130248,
    71857567,  876844125, 639794356, 718486712, 669604188, 215716321, 617971855,
    139675728, 757688910, 320249104, 621227957, 8420956,   210511678, 237853303,
    571777940, 124824068, 554160360, 861653403, 682637480, 231939767, 18101111,
    899784402, 38539461,  459245274, 133368830, 794361288, 845364734, 411437479,
    295388712, 946233522, 770525146, 9117720,   552920178, 575589233, 372629731,
    386010446, 840661218, 620900095, 139503115, 511927381, 578357362, 64025286,
    334338018, 50447285,  600060973, 463521109, 603848757, 124677320, 384555440,
    124916527, 185672381, 489919006, 909579381, 138193225, 265871589, 754007856,
    931017925, 530042754, 776962350, 693701991, 697550026, 65897729,  925178446,
    524529822, 282186556, 906408203, 423821527, 235677618, 198401842, 739841724,
    445468199, 551132246, 282892517, 598818617, 713743768, 323922897, 386628568,
    474046790, 302658513, 783562521, 701916176, 482177632, 681588349, 266655423,
    743351863, 319498248, 426746288, 89678205,  500650748, 546473898, 223152283,
    841147627, 688890488, 901303731, 788610629, 829394955, 750389455, 745439788,
    809252095, 287863106, 297473389, 52881575,  679729868, 61954094,  593572313,
    142142337, 87045414,  702643022, 32976555,  517206126, 380236389, 828797589,
    845005051, 422842060, 260455358, 651230866, 488177154, 982371716, 172307030,
    994127208, 259014259, 84243868,  148694890, 313032650, 79750143,  628177536,
    256112757, 535578122, 7516872,   660259410, 862246837, 942873362, 525515969,
    353458202, 517016061, 146128173, 615658629, 171576507, 313485249, 756862637,
    740107237, 450464972, 698608957, 380461701, 788065795, 235055502, 488339779,
    625468897, 81218153,  752562624, 954468821, 388408427, 220000770, 962611398,
    138488797, 232824743, 623588948, 89320450,  5174417,   444171924, 539838147,
    184946963, 829706030, 250353513, 837334003, 192637869, 954980409, 989726944,
    503629638, 246128748, 144252879, 869972346, 159483785, 38149548,  399002531,
    139867042, 702866700, 566004753, 303913805, 946274118, 352063038, 148918236,
    344908939, 925123896, 175513960, 888310551, 233700316, 237128991, 80142095,
    627539989, 30420961,  108486126, 993957197, 940173780, 407371015, 13694119,
    969064311, 945245210, 515586500, 834646464, 210959252, 766474958, 237866830,
    520123316, 83961446,  97878509,  896040082, 51406202,  612079312, 569120595,
    325712093, 979110226, 72296197,  169538467, 506717757, 990725778, 888153398,
    884672580, 747447278, 989585067, 197205447, 997554253, 162606658, 612854211,
    585638351, 300385030, 648581707, 24645691,  142364491, 87271224,  656248353,
    311752536, 345078260, 862509279, 749617553, 148690167, 255207879, 937517648,
    692740850, 188651194, 442080602, 285711119, 523391595, 806719830, 122802835,
    948147156, 825684063, 120090726, 465071065, 216239633, 955952822, 254936196,
    818273287, 582823720, 838683603, 211078726, 609268949, 539236132, 461048619,
    931162689, 575599737, 702129707, 929755292, 3165024,   932095281, 371965629,
    560082406, 915331279, 404247953, 119029625, 650026279, 33911127,  542568006,
    737311646, 839818392, 121381063, 81776121,  264049814, 428758250, 935258956,
    524814024, 827629225, 159677867, 208903802, 254070037, 334398982, 852112879,
    205126265, 581086872, 289728727, 749733927, 825622969, 203314518, 313219470,
    714203321, 966360246, 415028559, 441541100, 64736522,  135298651, 311340818,
    724308321, 852861846, 567399501, 818780718, 445445536, 185482874, 890679335,
    117928565, 212566203, 217299615, 125999181, 478432188, 642522487, 657976604,
    462229383, 930237021, 202402571, 859794210, 821285303, 193707191, 139635308,
    949631508, 581555701, 493872210, 253862710, 156423352, 756876608, 453019810,
    540238248, 525374182, 395165149, 552059946, 666018027, 218650948, 316154754,
    567824223, 718412883, 959027290, 327709825, 416281152, 860382344, 503677292,
    449112827, 426967024, 595415467, 755716122, 910210918, 495279146, 453103898,
    539903326, 104084806, 171428406, 629857538, 238805628, 522091539, 904850095,
    831383119, 364871289, 59654563,  188523918, 418555114, 248860166, 832365397,
    779188603, 392396445, 763896392, 993974548, 375970645, 176183947, 455296206,
    826990889, 44758036,  495683674, 791719842, 655621264, 658939366, 735144599,
    275667277, 655999018, 965639168, 676574799, 346864447, 379511514, 459854791,
    905913554, 604918364, 6920002,   652092992, 597377405, 920491194, 562313297,
    482675638, 955706031, 63469748,  417878805, 240441437, 990705174, 289937758,
    842452102, 258265727, 995663867, 792673745, 608833565, 729570088, 316539671,
    559104003, 153929272, 607988017, 245598088, 490462484, 935463414, 309255995,
    733478384, 499515550, 689830722, 849692817, 311550442, 635474783, 127169195,
    910162202, 556279594, 843716880, 644338672, 555172441, 515997236, 135709697,
    79038893,  557695690, 600886859, 838036451, 688243460, 80967535,  608159856,
    174858889, 422157947, 441973358, 506853336, 687223249, 123283931, 645920250,
    839276153, 765041805, 409869914, 291531081, 819585362, 902467908, 477747296,
    528122783, 145373134, 454099129, 741569333, 626092036, 479879088, 369907895,
    230044569, 505385342, 714902613, 875040101, 190473063, 872158769, 408884988,
    455015252, 472359859, 31983119,  493209943, 310194407, 220499597, 452995259,
    135106373, 178201213, 847019301, 990806426, 376403818, 58273490,  281675800,
    520754800, 348121405, 425884587, 2386009,   487763288, 337156970, 997180386,
    417075508, 864730872, 42921994,  871322813, 840211325, 364063966, 22525422,
    600235,    193819034, 893790438, 426792415, 487326644, 543061001, 282015176,
    157152541, 994468078, 884492307, 713444307, 579253748, 768509697, 992424572,
    146763641, 846399754, 258078009, 128093022, 747576202, 755784458, 775371259,
    738049893, 408147951, 30228860,  298205559, 841396697, 479705709, 89724340,
    910693466, 917842511, 772248726, 925394143, 423016364, 940794131, 589937656,
    12439416,  817505576, 5766321,   207335208, 205400856, 372008708, 188964921,
    55224741,  517371213, 384078369, 338366732, 664331412, 865275333, 827065831,
    804972385, 178748961, 191743352, 403004296, 927564052, 823868740, 257622825,
    717878335, 446887176, 322169470, 269834524, 843929114, 27272298,  50378784,
    522410690, 596183878, 451906315, 172190807, 733947210, 259460885, 833852491,
    616714123, 951537680, 926805258, 813388867, 443303026, 291977683, 599670158,
    238152294, 445689856, 936327374, 196240693, 364266010, 190436954, 155125524,
    802286442, 86247911,  746915367, 812149761, 386697017, 156862662, 999227446,
    614061595, 430319410, 14310047,  905615597, 730967460, 839536767, 566459999,
    528830445, 488205273, 155119197, 977792541, 733620069, 789944551, 854917887,
    212864273, 919407613, 737497548, 675470363, 478932389, 246699156, 251877523,
    53345644,  261274483, 760124865, 50090062,  854981767, 791955534, 691459974,
    389774782, 465159470, 569088844, 418118310, 342684204, 596536636, 249320348,
    606857878, 713420778, 226131359, 388575274, 21911539,  474258973, 93797243,
    644078757, 453826534, 403801164, 363533678, 992826772, 507750910, 373503532,
    616791236, 264372059, 183581261, 750221171, 878155094, 936703585, 6652074,
    251020568, 992659897, 368462422, 891650074, 750721486, 610629516, 709514492,
    685833760, 579428558, 50900893,  773008170, 385305515, 823673055, 953225968,
    603314440, 728148979, 232809574, 855455002, 295582086, 553846325, 476981256,
    332957653, 63715908,  224273587, 51891906,  346473784, 104448776, 460060855,
    136026344, 661137664, 469259167, 290470382, 86264866,  625481264, 739844065,
    704844076, 372478787, 496577830, 165971165, 39385643,  676697182, 190393622,
    920720064, 150178227, 939373600, 854086304, 830730341, 370885785, 789942972,
    765401747, 766283645, 416945039, 523371177, 322970857, 646425052, 511694855,
    736905288, 953415053, 560704652, 648860447, 428694301, 894447856, 841850834,
    272571430, 678430160, 346541448, 767049503, 36077574,  679246151, 466003799,
    733592729, 207171878, 650255964, 550391662, 53825240,  889883963, 12600784,
    641017311, 291148361, 554976793, 797024191, 85490633,  229960755, 15970020,
    565598371, 192019037, 703223903, 195449229, 64719321,  934602250, 799142123,
    251430165, 887594806, 421911384, 545506631, 493870301, 996132354, 610717221,
    171323729, 912266937, 320567831, 578485179, 307129662, 433491047, 21559367,
    270948717, 441179537, 802388729, 910301331, 384072750, 536953724, 835860980,
    839011086, 312337042, 763106402, 967665058, 924323916, 79578586,  765754762,
    832689130, 913917411, 898560484, 792084326, 348091988, 462841747, 38010959,
    392737993, 3009449,   350831771, 912199630, 425134703, 775020717, 647997584,
    741356698, 166278460, 869663083, 647072939, 745625861, 225232692, 772550810,
    97926046,  158274643, 639954960, 993664685, 948581315, 42923854,  497120441,
    472948622, 671591547, 481449061, 804758853, 579280044, 496884109, 7385548,
    654808800, 859416940, 503726762, 626537115, 408793283, 645016533, 420812424,
    673499997, 373272687, 544266494, 719819823, 952799809, 980437016, 79869262,
    746105457, 555042166, 300365589, 314262330, 775547898, 319195,    862064506,
    247861214, 539457472, 891181651, 739899313, 856325939, 474792389, 646142824,
    425012348, 464504884, 175255790, 645189570, 994342074, 388145377, 758485776,
    644299470, 938620234, 523460486, 696845537, 146251274, 765755555, 211765723,
    406209862, 262334486, 314682323, 238926155, 380293812, 793306827, 695934971,
    41797572,  164125639, 734295601, 957006629, 28334704,  805752965, 247692986,
    455019269, 674818780, 640914235, 498334463, 328997275, 98728370,  94303005,
    330407573, 622176072, 902724011, 502359677, 365755512, 33774623,  314570757,
    644858120, 319084859, 585531096, 555979614, 20241404,  171234266, 134211500,
    178834316, 623478011, 775898740, 847141991, 679004596, 888241786, 304501225,
    547356433, 9982489,   987046099, 186943448, 13253947,  765250104, 958448902,
    814200319, 837071048, 676888072, 296152354, 217946267, 972702366, 775412130,
    658068164, 156404376, 926912470, 443555522, 250919597, 317855456, 915909293,
    284399659, 453799011, 5105713,   790891033, 792297210, 710028002, 618142770,
    364287620, 331045396, 687384881, 424599451, 630174112, 867937200, 769346042,
    484475224, 70419182,  622020019, 256886187, 38456691,  715189368, 370106296,
    264780551, 292186988, 90417925,  143278292, 573568020, 714660817, 287022466,
    572214539, 829167149, 697488315, 72368017,  368199605, 262908146, 163077668,
    455674471, 748843401, 751645251, 884369638, 689084763, 672847687, 163891792,
    461395492, 302226377, 664625974, 577809015, 941674562, 131401399, 309794389,
    316433861, 667752638, 284189888, 968220163, 584810471, 201754740, 563353811,
    500121861, 515294445, 431344283, 551453151, 676839106, 482675182, 27141974,
    225531211, 417545520, 577032155, 777262421, 543846497, 202834963, 870266166,
    757772475, 863416480, 815999208, 987758583, 902266565, 262072884, 489557494,
    35642385,  322610818, 454671220, 846664545, 339165468, 167841816, 41792934,
    816030258, 8374123,   472924553, 590410784, 812622874, 821815806, 686549685,
    586496957, 573983725, 526279493, 937875240, 586272615, 79980609,  817572098,
    49577869,  988672744, 562171392, 646881269, 147215121, 616796113, 644886645,
    597791310, 683978339, 723580327, 317239670, 839871962, 979469695, 451512661,
    52049196,  468819589, 293585610, 841365638, 433463909, 635115970, 697627677,
    875593849, 94609155,  306000460, 324881773, 882169936, 773246242, 483441793,
    582334856, 731323053, 661390729, 859812401, 59690028,  578797844, 969394600,
    24581744,  639171654, 741500461, 703531323, 912447409, 118816459, 817192281,
    450086895, 391818462, 425676138, 40537340,  262670821, 27903141,  51470642,
    850558030, 147747791, 917072134, 344989983, 562182867, 500804337, 902729830,
    141473653, 45035817,  609220152, 538387348, 712397127, 553791286, 292908483,
    188425885, 346444658, 193186312, 824573033, 747471409, 780772400, 757551785,
    172848355, 845254480, 686129156, 785048012, 622014500, 872720038, 102455473,
    867474927, 919250514, 666141143, 588427128, 852369363, 445940559, 209574792,
    886466250, 646346449, 615807900, 796805074, 266036928, 442383386, 387820339,
    804624621, 58065519,  293123937, 197148648, 895594288, 161078475, 187577644,
    91985993,  869252687, 312427344, 749359694, 411989786, 44617848,  685631848,
    875391712, 225073610, 725783885, 684055221, 938696718, 923112084, 96102386,
    713974845, 87920864,  91300316,  298972718, 321470346, 82847310,  821083006,
    109063493, 963694457, 335333188, 419415126, 432269906, 78620389,  256059592,
    507183168, 74360590,  476674075, 950776969, 556452274, 116536558, 410412816,
    80018638,  654087452, 643902773, 997473904, 613296730, 816349021, 763840061,
    279014728, 108603031, 962582510, 583034826, 897098978, 509902642, 91571272,
    855903910, 683065640, 845807965, 627864237, 96631038,  526748163, 39991977,
    300823348, 967751668, 350518688, 51422069,  960456532, 376432318, 568316522,
    145000168, 899364689, 617820153, 421613081, 998545497, 360765423, 24182861,
    25348536,  99470730,  253205483, 487623243, 394440419, 709415547, 383872230,
    89782724,  320034586, 403979873, 36254775,  549581568, 667943168, 758068193,
    841054201, 582451650, 942588073, 769830863, 823609178, 926649294, 727177359,
    555879723, 894378844, 652545994, 298053594, 527144937, 744884670, 12805690,
    667149698, 124493325, 978511736, 514821512, 357286698, 311246498, 210888954,
    965502937, 932798317, 516157069, 598235900, 544198300, 859692452, 27345953,
    619090787, 274825224, 615935803, 705193548, 668826398, 37937406,  450774711,
    127774649, 852917560, 50350371,  665237495, 27432758,  281981773, 801697925,
    591798383, 197023576, 406358042, 794373745, 296697434, 681939405, 761832978,
    460217048, 516575812, 894110038, 12714620,  380931876, 693323854, 687959690,
    218747110, 262307021, 644569801, 695911453, 750070814, 862942697, 92391829,
    576645388, 562020314, 6919284,   946901348, 796844815, 423491488, 564231467,
    904886290, 173404833, 555546106, 322929877, 212033996, 786025744, 131528823,
    555356730, 714333280, 202915220, 809672717, 426216935, 725895468, 81980077,
    199937721, 360816765, 360743125, 75430894,  576563708, 230788709, 553965955,
    434610707, 488343014, 131594574, 699299319, 15360664,  295603119, 965115179,
    835169275, 336188722, 675847471, 123084178, 289371284, 172644148, 851254725,
    954115681, 208852926, 400285368, 272949949, 949307749, 406417372, 637108773,
    311628969, 54347186,  555094378, 760775792, 675727049, 559758729, 410594967,
    413513368, 662013397, 137994376, 587222931, 214336967, 192984205, 454673826,
    653529057, 711347536, 669749496, 542510893, 784865748, 479436555, 702243551,
    474714996, 284344106, 732211466, 695618554, 552387743, 215971257, 26190178,
    431885789, 584120993, 192812458, 629286056, 346268824, 387322399, 95878083,
    725347537, 972804693, 120163634, 683361823, 587682969, 389954764, 960382014,
    251659367, 265701780, 744584852, 420703965, 313783197, 199437853, 103151198,
    860216940, 827873811, 741106764, 892866403, 317880376, 651598950, 62520065,
    601324769, 163877813, 743532086, 475524842, 305649653, 636019709, 520070197,
    214412475, 604267039, 634178293, 767845835, 470370244, 405458485, 890829842,
    606046026, 471095166, 27555972,  67624609,  995492251, 321607727, 393733625,
    558658479, 620823036, 85516904,  347164978, 826672619, 350270030, 297068674,
    561311695, 359062471, 475755187, 863804484, 255614584, 749626475, 340977869,
    469594424, 212703887, 257501249, 162823755, 306023706, 241125417, 142710998,
    776584824, 650831226, 473016565, 89562361,  29352481,  480103617, 412034701,
    613572861, 60642647,  178587486, 567344870, 80944003,  482005028, 222170219,
    142318034, 556699736, 373084842, 752988211, 814839792, 871387412, 620386607,
    602064240, 108189774, 702036287, 278260815, 231701765, 951549235, 626545807,
    445966287, 712350716, 500124640, 188171399, 676125371, 371394647, 837298960,
    939336022, 438031036, 186714880, 216111716, 186044002, 581620230, 340599528,
    101017623, 954534105, 995780074, 618882019, 418147528, 767131494, 301425635,
    413745436, 962385176, 988626008, 137028715, 583626729, 374502874, 129245417,
    783696635, 516244019, 166701302, 395998250, 899091379, 185147981, 888020140,
    214258254, 830884306, 291227991, 600383262, 836705371, 150117498, 22802471,
    69557681,  875092333, 498794258, 369675284, 941672774, 245715055, 351032507,
    745046885, 808550199, 76081612,  247926676, 620593330, 454226637, 124999051,
    997605209, 309479695, 223505774, 30851595,  796149915, 234214672, 698950772,
    634482949, 657440469, 680685934, 622581826, 471407126, 641364582, 439880604,
    828662127, 710328881, 854337730, 218954183, 308890346, 696883741, 704295352,
    23756660,  692821843, 759054630, 223276561, 816528545, 805470409, 321576509,
    507647022, 959763181, 959047512, 71355150,  867173786, 570650020, 763468490,
    454668170, 461222603, 770001770, 552268482, 365360958, 764911700, 677237544,
    440328283, 984549649, 259844284, 75262068,  503143712, 838297266, 105854139,
    202662940, 683355886, 363265848, 555867076, 887916417, 766236164, 129769218,
    260030095, 376298724, 956523327, 899221952, 33538203,  917822505, 692713873,
    268868540, 480130178, 308269358, 37693909,  258466510, 300897318, 587896924,
    278096281, 191534712, 919963415, 565641621, 320019586, 879837320, 908684471,
    23870521,  479525399, 523797789, 364351125, 761922216, 427454498, 272480994,
    531892568, 292110048, 28298126,  163923066, 144435894, 463928498, 878941514,
    432095463, 874023827, 449729638, 637204414, 825970062, 643921799, 835275561,
    752031673, 957571344, 784924485, 289472366, 8843335,   972907389, 328534344,
    957382231, 222481914, 512123613, 255687739, 321672181, 106614581, 149991666,
    483357223, 454175825, 745448720, 274635425, 313232453, 374663650, 677756092,
    632611936, 22070680,  339269657, 132455542, 338802685, 718343286, 603452480,
    699756846, 802026382, 630527452, 896151723, 939566225, 258401424, 853392870,
    880194524, 792827319, 403695464, 109462351, 962558728, 135069793, 549142905,
    983579550, 110815829, 909786301, 182557229, 226845651, 200705606, 497560256,
    193529259, 308570479, 329947007, 189498630, 193994069, 898161342, 260293498,
    537724486, 162722279, 972018154, 150488640, 485488569, 797202722, 828096899,
    629742190, 221961319, 338535225, 581622427, 521477026, 528640359, 597216559,
    922488813, 730878735, 205255505, 474388932, 989429410, 502110503, 673876242,
    185798899, 902302522, 501809075, 233065479, 356452765, 541073672, 847051360,
    538785072, 862803293, 409689476, 625279470, 513414045, 868495308, 330682429,
    586751803, 508454254, 619218542, 533898619, 341736407, 646062216, 89216946,
    19220297,  949573988, 655460326, 308240372, 695484802, 880739242, 573500002,
    231169478, 64651173,  35122460,  131988165, 544955859, 769857172, 185393273,
    886747610, 615162473, 889794879, 337973379, 106604658, 386386085, 191341291,
    878552432, 469859981, 171378318, 2481856,   272586583, 832406872, 960328858,
    336146912, 281053957, 934376162, 646820844, 536944351, 364814113, 117742167,
    247184801, 561613760, 293317830, 469232799, 791091533, 954321146, 805541161,
    709574499, 898284542, 959570285, 682922905, 301875364, 719438718, 279592170,
    46864067,  358224301, 92060233,  672795876, 587715426, 106552713, 88983953,
    597426475, 297706732, 111408834, 78355372,  115919434, 156681874, 739661478,
    624419128, 785595407, 405130433, 6754034,   737909746, 281114344, 773967075,
    286197545, 307581135, 555742349, 810716297, 685375889, 750925961, 421118058,
    767308669, 713093101, 240592908, 443827005, 713587241, 441373998, 342424531,
    425926014, 622764455, 947687630, 790195536, 790596210, 375395089, 932221511,
    25492365,  241669632, 606391370, 846261543, 918436478, 737745508, 820405158,
    703149588, 99985859,  859425550, 554220631, 340069979, 312586014, 985226374,
    527441942, 838574536, 541207768, 284030480, 220471415, 961393295, 871333307,
    663187660, 790456052, 34901253,  535484514, 722947227, 714448394, 109574819,
    19083719,  220125251, 417603431, 976429984, 422222053, 899493832, 100004706,
    553764858, 417966897, 437366073, 189674298, 736512985, 780253223, 113871537,
    156225764, 556827261, 240680090, 501566432, 877565262, 472725289, 107264391,
    808323093, 55779840,  689987671, 328867116, 497001013, 594887013, 333410113,
    631186472, 840294215, 840269203, 191671281, 730328264, 87906040,  579860294,
    706516137, 375706875, 212905817, 636563737, 371574188, 104784815, 659682247,
    721582469, 298892685, 555695643, 389864,    190911396, 529299213, 410894675,
    332730574, 61493176,  735084536, 324332495, 935432983, 572785934, 417828425,
    536668260, 283506957, 181386007, 930770260, 41654507,  397364759, 661712266,
    957704561, 467366674, 981360437, 543341704, 842942688, 66309450,  657579216,
    450738922, 729231551, 364401688, 892809238, 321255591, 981613019, 182078766,
    287581910, 257912053, 212562074, 773918106, 591994316, 862205103, 230201619,
    203483751, 554022956, 789565117, 929049349, 826235646, 656610099, 382055716,
    318638158, 781052879, 921113281, 155317942, 673723416, 867221883, 67089512,
    281422729, 46554513,  59547294,  621947885, 655132643, 582394463, 947220742,
    242129262, 306394898, 102190889, 384049370, 25418591,  961962222, 420193998,
    240418005, 720679455, 944550734, 738288403, 75630516,  542181891, 387422652,
    55350584,  974846223, 28240417,  779310231, 385549603, 323848720, 403791424,
    690839156, 198854843, 817953072, 272671381, 464511161, 462716461, 355374728,
    692776041, 463320052, 157246267, 628326792, 251820723, 234400901, 489608588,
    144560185, 702925828, 784090797, 957419811, 656164198, 960640940, 180203837,
    96415507,  998579916, 462456354, 182396132, 904589630, 730357039, 575175399,
    237891572, 318282504, 974204841, 506217462, 850372570, 449312032, 237173071,
    677473176, 310432426, 517350609, 519164751, 694276927, 448982641, 64685419,
    974975446, 820353901, 120704072, 349187066, 694049966, 811386207, 533414583,
    962820706, 844007880, 665402350, 651284026, 539865261, 789989017, 101356214,
    611202047, 8168715,   489388533, 935941692, 509840506, 582373452, 238216312,
    630014017, 446025706, 891751537, 130209415, 299560121, 976614524, 378434897,
    574178431, 231132738, 992472749, 909426304, 116377349, 162162272, 245648474,
    549686534, 179141462, 692075007, 723182056, 645909658, 14361269,  617087262,
    221974377, 552612255, 188092602, 755557517, 587768898, 490498711, 2518894,
    715336312, 617125067, 409501829, 148222348, 722287756, 508186616, 528470793,
    627551947, 899326934, 634401256, 327358565, 78436810,  826493637, 684726740,
    956508730, 891606217, 24526892,  634647594, 647963390, 214891455, 196610805,
    452841546, 356077803, 4323457,   367511689, 991876200, 633457395, 378659254,
    278694471, 670724606, 433109360, 739295420, 209242515, 386770185, 550529210,
    904322367, 527416662, 814136345, 373111996, 365234797, 151071261, 685657738,
    53651484,  931164748, 93186558,  555823348, 111861661, 776517468, 598181114,
    619236678, 548386249, 600525000, 378050148, 33611038,  905478451, 470705373,
    304656170, 860612697, 82680671,  865826222, 106558866, 254293989, 779341172,
    318337985, 295779765, 407502933, 57702521,  699658590, 660049600, 829841368,
    880536179, 883869765, 432693983, 106831719, 148045131, 53887459,  184474494,
    145351750, 35022472,  141036939, 262960580, 456944085, 115872927, 608860422,
    682610474, 115500378, 482559979, 121898583, 861532144, 765811000, 880101873,
    905483679, 907172730, 333143286, 761140231, 807972606, 138875294, 418648634,
    676227013, 598926412, 375313855, 715298791, 296012865, 655324878, 355854564,
    152052376, 511527571, 417942243, 173805349, 545508711, 344954037, 34947151,
    804917160, 537477802, 751857389, 185026438, 350419106, 834011373, 567123736,
    22361163,  181073787, 543764704, 680150069, 710782765, 955531522, 973001971,
    669741659, 675655237, 511270945, 480581735, 615498095, 170682731, 523408699,
    821654522, 709032736, 252522089, 904554520, 654102893, 131097076, 221302521,
    927279810, 923491368, 86616826,  687201950, 554754405, 878915101, 511529829,
    43413539,  407864622, 116006459, 239702197, 596618750, 916490891, 969731953,
    921601053, 92532785,  398398256, 453697426, 798979828, 574852861, 216671430,
    300870037, 996615050, 258063469, 654525871, 619017586, 145506046, 270193064,
    426684029, 385546407, 777211607, 951807402, 339223774, 621988781, 269055691,
    625486075, 361791045, 448311220, 961238575, 535553496, 666417665, 444784348,
    389373972, 57979066,  475494691, 659372113, 123635917, 889415462, 575193533,
    780578990, 785468049, 771405474, 613682881, 127399906, 40840472,  434189404,
    735173309, 474310924, 981025742, 324247277, 557857531, 368189481, 412319831,
    261993377, 453538551, 242879395, 711877703, 569702475, 818774366, 979498092,
    600728728, 224291451, 926126921, 104464452, 857191057, 91724657,  774437499,
    612971479, 158509683, 370833131, 991090250, 385951656, 919657018, 580717489,
    807463113, 710456090, 172460066, 854955598, 672811723, 63379882,  553030831,
    511444696, 691004658, 959690501, 781368219, 712682648, 360602535, 929177297,
    508814672, 234330508, 744377515, 847436226, 422589793, 950782861, 443011305,
    168735043, 616630620, 28827177,  119244586, 594431974, 771026430, 189931400,
    832335061, 220429978, 302134071, 658579350, 847038139, 583311124, 747025673,
    171830470, 238775552, 207300957, 950749926, 203259769, 697647495, 128172635,
    263602646, 185283993, 883638538, 327150593, 36041829,  517790834, 132288416,
    37902014,  21518231,  610392590, 475220766, 384626212, 191096660, 194550893,
    909644220, 953413272, 971006951, 179787731, 908308219, 396757903, 824774664,
    876150410, 986286831, 308140727, 540781658, 926767129, 533278162, 722573342,
    56026574,  611604893, 109919736, 437683625, 200315749, 770598688, 609721024,
    700604695, 261566604, 166939092, 9959186,   201831074, 595061292, 716505318,
    848609482, 366086462, 46606148,  524463360, 990603495, 112642505, 353389331,
    735898752, 443800922, 441382435, 971945462, 329506788, 411143669, 324276788,
    318585069, 208516192, 200608203, 224584870, 82693343,  784863891, 661703374,
    242587918, 683527198, 442136238, 221100691, 388720469, 828745928, 137123829,
    528521241, 201099308, 269232369, 467440755, 965962321, 193320515, 171891902,
    449277917, 970822335, 365374472, 591997015, 966483437, 628994597, 787763358,
    127630923, 949533138, 216462626, 562230620, 200631051, 362321298, 721627745,
    714766892, 961744988, 901768295, 898563073, 764651347, 141780402, 188914501,
    158235464, 883243234, 176525028, 100365645, 314270174, 228867607, 768389484,
    571272970, 603649195, 579276176, 825191730, 567181599, 748431239, 914375200,
    852618562, 575487237, 593162547, 350346189, 878396876, 760161766, 581974874,
    959210169, 794481973, 840309244, 21974649,  796688439, 733961890, 308266398,
    696203370, 232620986, 229886292, 592712649, 224241626, 184071301, 946358352,
    473972071, 237884640, 746378118, 974017758, 830094222, 658012251, 260535440,
    164193446, 544067513, 408074471, 116687148, 831857844, 872792999, 507482941,
    628269783, 32578063,  232950483, 355650966, 568486961, 113984103, 702455271,
    934743803, 194569320, 179424579, 673308764, 178380019, 900476812, 552570043,
    829917162, 477479926, 681610623, 238757801, 23840226,  726267959, 696057438,
    574677282, 186381880, 35485698,  889222427, 539179043, 821951783, 511698146,
    171449150, 306487594, 927560548, 177983126, 212306916, 494296811, 896705972,
    976896293, 732382445, 621422605, 979355458, 802200321, 571346343, 946088899,
    940072333, 525327115, 582233281, 677737200, 543326340, 286785472, 133019909,
    738261012, 727900737, 310131795, 841315981, 427990858, 462400646, 732466357,
    777501341, 656856278, 836604083, 828195985, 395025599, 102692137, 603174275,
    85844851,  188945295, 857464733, 670624315, 226531488, 416736089, 896956498,
    987691169, 639227198, 147949944, 374797132, 178150646, 48999152,  839075399,
    510992241, 560735414, 864160045, 119678346, 631224380, 750339888, 930673449,
    900385260, 790107707, 743746671, 973743118, 818491268, 389353522, 808802015,
    939386039, 670345979, 729437156, 87208405,  320910710, 882349386, 464047143,
    62705137,  646621257, 116748804, 917896345, 123887811, 988238488, 955533834,
    210758100, 240071640, 382851200, 592070556, 320863411, 960031749, 783694175,
    393071961, 748270549, 964296637, 954789954, 959569135, 610934717, 602197819,
    672310953, 805672385, 242036374, 974231469, 73317689,  707495636, 812385954,
    152586963, 718789308, 816234642, 17031169,  799805135, 68043121,  378715813,
    101997531, 370724951, 379199558, 118109713, 995929225, 431341092, 750709870,
    670219199, 182709465, 892362356, 933232431, 848800901, 511329206, 802284988,
    574599681, 704877501, 86538070,  950231489, 915552654, 332057375, 203789714,
    40465807,  272825608, 327341856, 65871676,  737006797, 564001606, 117271754,
    42366756,  559314887, 72080910,  16332576,  518496681, 178460080, 922835669,
    85853831,  289844495, 114678009, 888735061, 636817795, 994800442, 634170402,
    81387460,  389851236, 385318248, 616434278, 164064665, 58527489,  899289944,
    780921080, 746492224, 321201262, 774927097, 331355371, 323578389, 464788611,
    439530943, 381191621, 307493928, 544419454, 189115951, 888179722, 56027054,
    400162259, 492572749, 570922540, 50044808,  215440608, 939002974, 722116659,
    506389393, 522781470, 577382527, 975750661, 196920209, 110476437, 378088881,
    602038543, 843360858, 248647300, 20368720,  694617749, 70673631,  36350582,
    105955049, 625577110, 626598387, 795310078, 887715330, 349947783, 686546994,
    25161376,  125463051, 652276150, 662037486, 595549690, 718629428, 781857227,
    435085264, 355204932, 469209929, 121108565, 797128380, 955454823, 818408085,
    882286707, 437088869, 418580397, 389415090, 366167084, 344077692, 866730359,
    406913407, 766604223, 751773745, 455849570, 218126777, 673152505, 545689875,
    847077339, 637717539, 701057595, 466037197, 381085766, 57548409,  594551854,
    530621083, 690872937, 920194031, 423902550, 959482076, 921554933, 859646318,
    730912936, 644586671, 440798612, 580905887, 900883897, 627969908, 7224353,
    710662547, 951043097, 178313806, 799487853, 587235700, 362545847, 969286261,
    835552372, 557893781, 713002969, 638126879, 348209223, 611703675, 356160228,
    473805793, 891795539, 626114561, 521722743, 696652030, 743632248, 737132059,
    533440828, 687481424, 130327262, 707480981, 37477429,  738084106, 49372472,
    959286577, 903360150, 76895080,  644809401, 274597234, 173910265, 425631910,
    46188770,  657727345, 176228111, 811963776, 270654659, 19177072,  977422478,
    324751345, 452452633, 712043546, 478047692, 948121659, 875206020, 215136857,
    54756708,  704283961, 569515206, 317180497, 196343809, 80152929,  231235994,
    652206552, 860988182, 339891870, 990648286, 46638763,  509149276, 541939348,
    355904452, 431325298, 357549879, 549943697, 474564051, 162716659, 963090407,
    647842561, 772624310, 369470387, 84034776,  592879970, 951519687, 953129351,
    88447823,  355811270, 262410819, 122874675, 324874139, 427752611, 966515031,
    89544957,  490043087, 514702039, 593866856, 168367087, 644950238, 234858331,
    120499562, 727750147, 300432587, 358531606, 837951330, 555717474, 833618568,
    749833609, 687809699, 594318929, 382324387, 922817996, 752791004, 138103251,
    493853550, 72041429,  300412849, 811511206, 524951630, 444956540, 657742723,
    41964071,  115222465, 18151787,  503137364, 742459967, 290436603, 291850913,
    707084680, 845615216, 544193854, 838816685, 820365504, 64821808,  958641055,
    521245547, 626401031, 826921769, 376015807, 23365585,  127208963, 222201708,
    397679385, 704521093, 398003266, 367632312, 560201311, 959095835, 518490388,
    782459134, 85411514,  363544205, 898645481, 642423170, 356964076, 218770908,
    101398744, 149838090, 847676333, 658844131, 66455878,  967449330, 921735030,
    608517334, 501977444, 370764256, 932365136, 842116001, 2414808,   363210962,
    468920751, 163861001, 885803673, 639058145, 446132418, 402067874, 794603245,
    321367393, 633937175, 752437584, 89831570,  777480614, 1875666,   446948540,
    607778609, 895163736, 654319771, 56282607,  953825487, 322366231, 857703755,
    40904649,  611285125, 973715621, 685339249, 58869526,  750073307, 286265907,
    174980597, 937499408, 885979049, 169542536, 859733362, 993160596, 36179133,
    99723628,  300577098, 119273185, 895361237, 321883362, 666141940, 241183990,
    611545116, 598039345, 942688158, 648305554, 976484452, 909040395, 639505417,
    717880425, 258364578, 177731935, 331433241, 644072879, 835125078, 437946030,
    732730195, 263084996, 227710431, 634360769, 949793998, 673705291, 929116367,
    780620265, 396385982, 636792029, 981415232, 534698667, 605385771, 446440726,
    846286425, 170393385, 865408351, 535702043, 91059914,  396396595, 978353795,
    909026952, 193229763, 332588600, 947659377, 659231379, 21658695,  908909731,
    930701976, 169444090, 242105422, 211346541, 280700862, 419568817, 565028991,
    410179813, 947115493, 162947610, 353283845, 440000302, 555403642, 967699788,
    939284378, 26563328,  808244694, 628818450, 464570707, 613515466, 816227814,
    798592997, 139960087, 611289279, 84099181,  767531938, 309790621, 725213859,
    101876198, 339117512, 560452243, 695943492, 482097635, 696268438, 33261687,
    549042129, 227726089, 324472676, 889008129, 433042127, 121540726, 256202561,
    466427373, 253057484, 582185803, 12967232,  365976221, 1001525,   843332554,
    557829538, 816545092, 17260454,  45247051,  117768503, 97334544,  142496898,
    511333733, 432449646, 539910489, 752822850, 319965495, 857056169, 748503998,
    709859995, 43212619,  215123872, 763386790, 167320288, 584036346, 431950841,
    657125650, 47836908,  931587780, 624620056, 214312432, 650854133, 138350471,
    695691723, 818005740, 800549557, 453278187, 704208506, 161679109, 21228857,
    24799573,  523890408, 644772103, 703815094, 273840418, 255182503, 451051671,
    765402838, 276461433, 817763339, 311617014, 56463857,  173174288, 985489261,
    364879760, 260289777, 866138754, 444165753, 814280531, 665038276, 301803455,
    959789371, 700429559, 566854653, 152240081, 211426797, 960298,    230714841,
    36233184,  269379666, 489824611, 914246569, 385971337, 351582326, 588477371,
    891226054, 658857137, 819038771, 551105910, 907928307, 409262069, 270013431,
    94369267,  383868816, 550427912, 563194105, 462941349, 484982153, 904457766,
    192247167, 381460272, 970265030, 481977727, 31384204,  550046603, 922412185,
    814116989, 722990797, 245899471, 637663524, 160142774, 468353543, 438206607,
    772758812, 544546780, 544896635, 116902729, 711349637, 991251853, 994312234,
    957097261, 412924284, 175915003, 689039777, 818561243, 741321533, 538140579,
    281833152, 679071114, 57304296,  833699278, 707474921, 62014389,  120960628,
    172686671, 848769176, 927259833, 589949390, 807541116, 181697612, 334825796,
    986129478, 59148373,  119891371, 73571388,  74981386,  827459594, 634033443,
    904106237, 805784045, 42592013,  13913474,  335897837, 481916336, 598553686,
    218288615, 420595899, 842333638, 105897102, 275003777, 283689245, 218844471,
    756122698, 252407474, 829890821, 653416861, 368228913, 59776635,  531136583,
    47966437,  827773479, 904112376, 898657123, 115622291, 743558,    8828680,
    860518048, 777455376, 971624304, 635482863, 511862704, 639631999, 438768263,
    901901225, 196727914, 228846332, 683559026, 314126432, 1806760,   214540782,
    658500415, 214746490, 608268120, 158011813, 934741554, 940540029, 155900422,
    939640865, 651516855, 620660513, 386136335, 745327884, 184835166, 788977403,
    243849317, 935550155, 377688755, 32165748,  172100122, 755822381, 999829632,
    354024371, 949379942, 411448871, 895625714, 875439951, 926343731, 221188948,
    544617857, 290381100, 878249839, 843386003, 120327277, 599441531, 626324309,
    222677418, 284201958, 54461302,  576857817, 459925304, 239808803, 254268736,
    112223863, 23598162,  687569821, 898753792, 250518185, 143988237, 47361625,
    861946417, 779538942, 459568395, 136709445, 556023371, 207252924, 283891715,
    777970421, 601703155, 268933499, 562239349, 644182771, 790868861, 383170492,
    819558870, 161660156, 71891404,  868527522, 221592101, 545660152, 741329109,
    492560139, 333418180, 435874670, 747603335, 289108386, 748335689, 149258814,
    947775920, 305799873, 691745662, 859773837, 107234823, 956564497, 619391212,
    703591889, 938772236, 739299002, 85626843,  429657017, 880977489, 480485548,
    262991906, 6951837,   169090857, 52743047,  668398208, 189604863, 792261239,
    245121057, 351830780, 475786287, 298968521, 854649380, 841402304, 705058352,
    643408174, 451190291, 106238922, 905773250, 556348580, 833422618, 660705083,
    321237184, 837596708, 612787020, 472721787, 312244517, 616099679, 518429803,
    244784641, 258499452, 36214998,  60302259,  133990319, 360391216, 503581979,
    672913924, 583093439, 550942660, 250979125, 940247510, 652858459, 675878546,
    797466841, 370674995, 907745476, 588883865, 987383089, 218448226, 449737002,
    955307454, 585163662, 699903733, 105920007, 731369808, 740798623, 732815063,
    955069657, 912907186, 197692808, 955042514, 945946070, 849264882, 370954232,
    838048808, 299015263, 472283529, 79267470,  314511120, 164725792, 389039359,
    173690840, 816568260, 483994943, 820870927, 376726741, 251514316, 51302942,
    615552918, 877972951, 860217092, 843254111, 673189570, 27294194,  673071999,
    795723031, 758712484, 935436811, 338815770, 883286020, 37036329,  817487284,
    363687397, 501326546, 406242075, 412047561, 466907683, 521730345, 887830119,
    645973608, 572743108, 627707705, 639840156, 652240338, 640176912, 825286131,
    371748226, 535745681, 760583377, 383534127, 366576210, 849032156, 398519118,
    755697805, 230126756, 873857996, 596624149, 313413445, 917211514, 268976357,
    940260428, 184998150, 343332488, 895030555, 16762969,  293942000, 61558881,
    102830492, 276975461, 171586002, 255821416, 397765975, 465541436, 942936259,
    901676852, 166714611, 392758236, 685709975, 805075316, 587042608, 808975676,
    446219613, 924221182, 717855804, 15861100,  644071222, 797042841, 247404499,
    716210868, 160723295, 402081695, 469917635, 28585240,  653821167, 10364285,
    208063293, 102556082, 540148245, 666014613, 667552029, 822004563, 166994102,
    334528303, 122406032, 697720617, 316059644, 972708995, 726071977, 462361745,
    224085543, 572856784, 15957789,  963335493, 927695057, 176379245, 383462849,
    865550856, 810104898, 289052741, 20714571,  35324294,  832466091, 743055358,
    790404115, 80236396,  795827061, 395369878, 252255602, 184874192, 23530816,
    506336207, 658529903, 592654716, 556715519, 822615331, 809520025, 787957548,
    139736444, 548229608, 666322128, 72657315,  992131036, 916436220, 768152482,
    120580894, 349515729, 528627236, 449845586, 460148110, 371078849, 605223863,
    752665040, 1624779,   644242679, 985944307, 858571182, 461684752, 810675957,
    993351100, 382520483, 250821716, 977534286, 508168386, 246241034, 609693247,
    743320473, 146607662, 998445214, 431759341, 343673635, 640794075, 262660065,
    878625869, 897437609, 516489488, 23659927,  759999147, 655412155, 503783506,
    667819834, 551718218, 605276486, 57914865,  419059158, 46776049,  804175213,
    960309116, 623584323, 753818347, 91180671,  886695514, 802544874, 178110089,
    143529344, 505623920, 720477855, 80630633,  63261778,  317677628, 454032332,
    240724484, 186782768, 536920726, 899201547, 923187729, 845529381, 295331561,
    895582663, 595645523, 82038737,  267747183, 796913715, 122804438, 49897344,
    362714249, 862665025, 396997686, 604625458, 37112088,  976519680, 446432499,
    748095242, 429003830, 291811017, 677603270, 505978357, 9432426,   387257732,
    739252457, 905769562, 480866202, 114477162, 910290154, 964097748, 975047101,
    558505018, 397606795, 320449623, 674423851, 567300118, 96600383,  149970539,
    81408680,  943126359, 618538215, 902294691, 538833948, 516910200, 175195207,
    164991807, 613271994, 282270752, 195159923, 182691277, 893377616, 350962890,
    378185065, 165520304, 736097983, 104275527, 107760395, 496223166, 392774298,
    339005193, 6415884,   852198248, 869760630, 57337377,  328642311, 313491466,
    473943256, 761334845, 163974456, 805443890, 454791777, 655688589, 217832409,
    48206873,  250729512, 650171495, 668474483, 645785673, 828763867, 638317152,
    787083774, 304210226, 761376754, 998417863, 114437701, 179152011, 856498178,
    895998969, 375283462, 756451234, 63585213,  746100628, 352262217, 685049322,
    41368875,  185621781, 193116004, 704542713, 613788001, 712282785, 133675350,
    36342676,  127889371, 885675751, 150684097, 935926548, 457679454, 908239676,
    46086256,  363721489, 148164239, 493754728, 991370249, 574494584, 10015428,
    949112564, 670563791, 506987577, 373557253, 422937350, 707248469, 738375556,
    170359517, 504522488, 822839646, 971251884, 14295245,  6364559,   829528560,
    31902055,  509183036, 190031100, 209870102, 452967833, 456964275, 743009770,
    951211379, 933702078, 78834235,  324014730, 139963002, 928413345, 526681054,
    322007744, 800710829, 525191165, 830508742, 525334945, 99767615,  190439097,
    150011682, 869931254, 195895108, 642716041, 472372818, 845969378, 891314830,
    756420050, 48906613,  622902626, 55143732,  131611764, 37731551,  299498677,
    640694188, 842798821, 526134613, 706085903, 187560670, 871101937, 458380397,
    376491783, 258403652, 497475041, 92698088,  58099292,  798700283, 160237119,
    420795881, 715071206, 382414136, 647275638, 598995012, 116058943, 342151526,
    611720254, 575486020, 397160465, 573871310, 804763794, 855872322, 662992488,
    811636563, 484712697, 785331707, 394682840, 540399090, 628990032, 459093333,
    905606245, 300709259, 285160187, 107113222, 57562713,  785917963, 944928720,
    215790782, 159729073, 314679186, 484363600, 220810932, 193756864, 176113742,
    653956340, 385162015, 613321758, 655032622, 595475307, 963064968, 575934821,
    565366446, 339412611, 420269925, 853822178, 621890905, 341799536, 730085337,
    669687144, 43038664,  190723760, 520007694, 397191752, 242741101, 295273112,
    911553855, 420256891, 134534726, 229041960, 288039667, 912665239, 952930369,
    420783608, 759505883, 355080139, 13776242,  725047982, 766014613, 348574940,
    279003328, 249479481, 895297500, 190353452, 999650409, 673605968, 308743105,
    923509648, 610816753, 868217020, 502437344, 785101081, 683997286, 190190426,
    14850091,  628445902, 441409418, 361000413, 482358408, 402504037, 416870733,
    249891590, 406197948, 221484197, 989497991, 210224657, 35396951,  560021235,
    76667846,  849870082, 830692370, 990522851, 183760025, 844165424, 799741184,
    751900362, 312616925, 845225615, 371369299, 912379072, 977692978, 464715793,
    272736508, 409713958, 661250225, 355611695, 602025484, 655098052, 791858343,
    935074244, 363351667, 660633695, 830681132, 207979827, 766178018, 314428742,
    291425335, 249769039, 382582132, 176838020, 531553490, 339637176, 171182908,
    867642857, 564528401, 750769745, 600414104, 894717790, 100220991, 558039019,
    986383097, 729964739, 105290652, 584230942, 928474519, 731654431, 704603911,
    359730029, 568522294, 752842834, 632601136, 5043193,   663508854, 927237848,
    469651192, 496701127, 750913782, 564220277, 26335023,  523313806, 906775254,
    972081105, 77997445,  356067959, 448714422, 714021267, 864595306, 865545519,
    612006278, 769170204, 155531347, 410127755, 951372818, 594730385, 248994712,
    771421275, 185158093, 499376011, 662863317, 413001393, 805887756, 473324595,
    921297057, 18735813,  386934464, 146972891, 560627347, 903669593, 967094539,
    386758849, 737091463, 755426664, 220579995, 435711349, 887741198, 883209694,
    478560592, 9832118,   930618930, 163415091, 240446492, 132759678, 134081914,
    702601410, 909768461, 660176441, 680440363, 57179043,  900412868, 646477707,
    534303308, 997628154, 282709724, 402700228, 997064274, 785650024, 436878044,
    977972319, 780587881, 124834909, 341934157};
int main() {
  int n;
  scanf("%d", &n);
  printf("%d\n", ans[n]);
  return 0;
}
