lista = [534, 190, 56114, 578199461, 6530466839493, 502290873, 9428030, 96900, 418498445, 150098033, 75780432370, 55295708080, 23707575833, 12881577657, 1008920, 8031260, 28050851350, 8981322274911, 31290971635, 2220288887570, 75280, 453374644, 66041824930, 29425615437, 3409395, 7188880, 744579671, 4588591, 492259560, 88199403920, 8440738746771, 98836997690, 5829920, 374254540, 4545053280965, 85944961650, 17813, 50958448190, 3865762, 67042572081, 3407044, 90700, 3869250, 876435270, 89137878901, 10914, 795956641, 1236468550325, 413864161, 46510, 6606424080410, 77680, 830475851, 85097967160, 93195801820, 315399442, 336458620, 999736570, 12863911346, 4090367141684, 45823, 8388877579801, 460390075, 18900, 4786821545672, 82660, 81119878311, 82285919420, 679786241, 4237672, 871960631, 39905, 5388930, 96570, 892695080, 23810, 949027560, 5989663, 85007833150, 908880450, 9489200, 961796590, 6819373, 102798678, 426194253, 53019796394, 3929664, 983273920, 77941, 5678113, 11574828651, 7262821, 69141864560, 42655, 8499549208141, 2489603, 26526, 5808640, 7891565134000, 1491147313018, 2466809507847, 706699942, 75940, 16556774561, 18633218643, 31480, 5263261, 5523576070763, 1418134, 38535, 51864, 722493922, 50334920553, 59428827540, 72551591531, 71122857201, 15243870657, 47820, 82411, 6899842, 85821, 17139988178, 90323977870, 16944, 6016995932743, 906998110, 4699140, 409944553, 2122577552537, 85588932651, 692399251, 3339277142020, 75381, 44466820992, 2727216583305, 10753, 33369450082, 496952975, 5584249541642, 9887910, 303990696, 3579445, 304588384, 11705, 4122396918771, 55524, 2248729866513, 453055271, 75580, 35567715821, 73212466280, 84751, 405797085, 15972, 197139702, 6048293857040, 120064647, 389480110, 91380, 6539650, 1644336277992, 7133902, 56347961642, 2447181, 77544359482, 73951, 1378030, 88516163360, 101389996, 6431987737851, 8427950, 8728980, 85810, 23737898565, 7076417473182, 48831957920, 2694051, 1633350, 47112, 5282196543262, 46372701432, 65172642522, 1108995, 7916392, 3089042, 8995881, 69972, 90142833250, 30207923800, 8412583519581, 686697871, 94750, 37614993125, 167282097, 31843, 56642, 53762, 72780, 989173050, 6549951, 7611237191592, 3057819637986, 920693250, 469093001, 6320535361711, 8449217393970, 15863, 551145014, 33540948174, 720979301, 1912928770330, 572010770, 523851271, 5918086977643, 714589561, 69227891901, 88597708551, 58971, 4516694, 650680713, 3289199810340, 90840352270, 9766709381920, 6998919637193, 94950, 101691677, 357680956, 139592944, 46048537811, 59805560504, 2749204, 52195697112, 4977974, 8882558997901, 857495251, 9889280, 66942, 32844, 696579473, 8959171, 9300109200220, 75720989291, 2638477, 974496420, 45910, 94214484620, 791099481, 4868674, 66743887971, 8727570, 6616778075913, 4509790, 7287694540152, 795598811, 7685538117640, 656978851, 80339730431, 1917949546466, 3124247117223, 38656, 33072997454, 24589788490, 4532902, 301861114, 7477092, 12993, 8114600, 6268152, 7778871, 6788191, 6407491, 7237562, 18601938770, 5811251, 7596891, 971082240, 5418519022481, 618361461, 539578734, 7409350, 76822720002, 12708940940, 150917025, 8086711, 4684049501334, 65113807830, 95650, 2529774, 35646, 8549590, 22229832962, 14364451518, 13083952315, 511564333, 78842, 9332149796060, 586593643, 8265098696981, 14820965848, 51990, 64501, 3663867671116, 4342009431202, 779369890, 437074775, 39982, 4825153, 81182795781, 43972, 1766277, 48677891034, 68851, 943476620, 5283809072211, 352069723, 457060333, 32701774142, 72602564722, 47047926421, 6455732, 8407288918120, 97538873260, 82102917230, 7666668844112, 16998, 63717950652, 9067208139200, 565490230, 412752513, 8257457911091, 41059946104, 92800, 9119140, 1669961, 2480912373361, 70311, 24235866012, 82864415741, 443996264, 992384210, 46942, 30601, 5797494683161, 15223659212, 7960083405040, 83144703050, 4088043, 88701, 9950799257520, 7446639029620, 431678650, 97400, 894593271, 843290850, 61492813751, 2272087213266, 7698072, 337699455, 71861, 1529448417463, 49852484153, 2117354, 438867750, 267745552, 32739468133, 8566360, 41865, 1669904, 75580, 20774, 215861425, 2378197786483, 7943375723180, 4927462, 8882786883680, 743885680, 2787672, 6394890, 58641, 805062210, 16525800728, 2619946, 4768004, 84811, 41952, 54992672831, 41645, 90552949340, 241394881, 76253308282, 3879435, 663482063, 439893402, 8106341, 9281479176540, 51961, 419363341, 2763135887800, 9812032237030, 374893033, 33665, 5418384, 6289032, 83810, 37910897542, 7912965523361, 4525588134565, 20926, 915880080, 9319360, 5609071, 910861100, 486293425, 860694461, 90182938880, 75961, 78505875272, 4249823, 2465117976442, 794441982, 785497320, 2047160, 34211, 92420, 31960, 71905307132, 46580976812, 49200647672, 289361492, 31266498385, 3808566, 8821999170110, 730889212, 3357939208792, 4157165014241, 20691507372, 90490, 744196670, 51732, 5127592, 3517446, 303998044, 10707, 8342758587761, 80931, 32270966342, 5901985268374, 6119110, 88620, 16316824250, 48941174940, 1303964852581, 84338270861, 383393033, 1356737, 5898534, 55923, 2178734, 72681, 85881, 8549451, 3647789246521, 5594710, 2839195659756, 30533868681, 79410, 374577341, 3872324289971, 3314075, 5051488535803, 763889590, 94018782440, 220494103, 70030530450, 4687275, 187194074, 38521, 681547281, 78465799000, 875971230, 7908491, 332980506, 235297653, 43958596782, 9821496603840, 507196163, 2528511, 6818933562782, 252184273, 6465561, 4927953, 996978490, 1039903, 498648141, 29575, 5877253, 2866728161481, 337436241, 97400, 31021966005, 46884, 9484268038670, 34299938300, 9223970, 2078369853900, 63908279662, 1268245, 51232650683, 5135538290844, 926099760, 39925, 2038055, 7077262, 6199723, 9640459784270, 58018965633, 8998831, 464991764, 3547268386141, 9605154234770, 52901, 9846010, 68235977572, 13847, 9732498982750, 4219652, 2354466433524, 3061216597474, 5429487513082, 650277600, 16016688347, 1985238601393, 38822477740, 1112033843998, 134998420, 2526331648396, 81880, 1797608979584, 13551, 7372190, 2586097067573, 3216865302971, 807545091, 1672389974767, 44881, 13732548735, 1242676248224, 77592, 710790930, 23656707407, 911498770, 8107539819680, 86939872410, 73820, 925971870, 29007979737, 52361972863, 78458809641, 9198640, 1909168, 233798837, 2609464, 53540602023, 305885714, 19714734275, 88630, 83891, 7009701, 377787945, 1942718261668, 73972, 19791987236, 6858577622782, 68821, 93339790250, 1949733, 41452, 5296523, 54345891760, 89531, 1539745, 6497986478443, 234595207, 4081209693114, 4613128051083, 500379830, 34574, 20784, 2414946386943, 440657533, 91710, 567491831, 2115946027913, 98918500010, 722696870, 1147565, 66569628452, 56833, 115987981, 29273, 948255200, 196995260, 5493651516731, 661566132, 4296748731143, 29744796915, 348673702, 4315865912230, 5366004588124, 91272918070, 55130973494, 754598100, 60790, 54630, 239451555, 53752, 4904107778330, 53866412521, 50551629333, 63813, 359494094, 76234701571, 14280889895, 719569120, 1986267460007, 761180251, 8778071, 5438359955654, 1099683, 9664270, 80940, 1608958, 1912539365328, 99772954980, 9379130, 8089641, 1589388, 9209240, 58535930104, 49775966340, 14434, 46515, 95940, 48943, 40775, 787299652, 2183729301371, 550130490, 3957085569265, 95870, 28967977320, 35222, 35524, 2757874, 418062670, 2764367, 75072910421, 7148992, 1037619808715, 87691, 58305953542, 42772, 80798642800, 111286703, 810846000, 30846, 81951, 5033549496090, 86501, 566290304, 74691952681, 9748240, 18878925813, 5370344192481, 5375366177760, 99106515950, 4789911, 75560, 92978703510, 3901159789911, 1223714107797, 2164308501227, 964696970, 72213946522, 38015901321, 97430, 307192844, 72755794411, 950189640, 2570999412625, 2682387817080, 8835012540411, 25271922461, 9365953196220, 90281994960, 90920, 5746609042630, 7895681, 4774748283155, 2783019009221, 8065243314051, 89030974890, 7288490, 33785, 412184070, 77606458031, 347583014, 2247007887447, 778592270, 4257525, 7896539618750, 5287773, 7128991, 89850, 2788725, 24251717537, 5519890, 9665910, 95990, 22942, 59039424630, 2865422, 9474940, 57096911633, 44890, 874844891, 61963, 7196129032652, 326698913, 7867196503272, 32920, 97380, 25189969714, 11825623604, 57504, 205996313, 71116561170, 687176133, 5719931, 548568754, 6026189791212, 58872841142, 785476151, 58218861260, 6245381, 755971480, 137472861, 37243, 1125896141578, 132998855, 5976201, 48436610821, 10587, 1568118, 3165969643561, 28412, 25494, 61641, 37742, 6575771, 998873220, 7819011, 28923827735, 39713, 76612, 678590851, 2100247824936, 9078920, 4043829005211, 158251428, 5944939896440, 24099562182, 1124016, 660171733, 786897562, 66675996342, 54812, 6965257794712, 3758560, 64922350442, 44885, 64925970903, 6432379062470, 14542660476, 612679193, 3520159100144, 3607791, 60309424923, 3669614, 496073670, 367649851, 89084450090, 8142408702161, 22933, 73551, 5436048418924, 82941, 3469021, 13933427537, 99890, 44905, 1549589536200, 2785031315521, 4515633893761, 47505, 68991, 98780, 3943739605512, 26545, 9637340, 7209901, 34810, 91033377910, 383193963, 977765280, 41216916023, 25728721311, 77088345380, 67792, 4298965, 71483965341, 28966803792, 5178024740540, 708350321, 4888164, 4182668659544, 1347808849225, 482167442, 166869456, 59742, 2997295, 4279437791581, 89277519970, 1008016, 319770101, 12471, 6832042744013, 301691586, 57466946751, 6062056863322, 86759872781, 137197980, 15443131787, 46832, 6827396655463, 70961989202, 1484759583380, 927214640, 591998634, 854299401, 22962964840, 127128212, 24395, 37069742786, 1314379390718, 6079003, 9949070, 21930, 22221, 2007743582624, 8636940, 9798760, 446091154, 55823, 333487271, 18325481724, 93510, 590495961, 4511346659464, 32806, 69326978583, 6539860, 9248906043430, 54292994574, 1400959164433, 52451, 8435556256201, 17438946506, 2577167, 829192180, 3828660, 98086361170, 12967, 8582548473690, 1918468, 6429372, 3975588557682, 8944425856301, 1107829437793, 13011420857, 878682601, 23975, 629278000, 849069991, 71932, 933391850, 31960, 8423810, 95873886460, 8409370, 819286990, 1587498515940, 5531930, 8485131, 638598790, 41683, 6146307994501, 44471735532, 27625, 46705, 67923, 934991670, 9319150, 2728289325206, 2209908996103, 9775715081790, 106796825, 92408657820, 16930, 2061590, 4009742270664, 449589894, 6384608172452, 66811, 32085771024, 6150957845213, 57948936152, 3647026, 1999812, 7289243952420, 1897857, 66317839421, 235878395, 207671657, 97920, 6052139874853, 33418970450, 47352, 151963130, 42183, 4505467854342, 3856196910023, 4816100, 90132465710, 7475049787521, 8692338767380, 368388655, 84446868460, 155182035, 60620, 2656606, 5428863, 66863, 7819300, 6697447978141, 91710, 44551902495, 67678947132, 2488057, 3219071, 41007403050, 51410, 4835120, 32322458943, 7856506296841, 3118684, 11762, 64373, 7179860, 3897111, 85480, 956989700, 8329681, 178393631, 40233, 884771590, 9769278564110, 85990, 7956688343790, 628173660, 17614, 9036705261060, 2868599062874, 559963721, 44903647512, 7068166939752, 175290344, 5651245573803, 4328213, 7927561, 8118731, 27951, 21917384665, 698573042, 30854, 7337552, 48474925804, 25807, 86920, 7994138419910, 72358761791, 24894, 2951276842587, 9029900, 5984729166922, 9881557769920, 80931, 590896991, 505065301, 8547276649470, 7688198483632, 79531969662, 6729803, 4253829232570, 1384194, 132354266, 4177137182764, 9638050, 365291572, 958356090, 46994, 71891, 21847, 66971, 38764, 56150781663, 9568958062630, 6109879015090, 3210576663381, 1284430, 65079178311, 22109777283, 529758170, 42535, 485396462, 22932650891, 23762380397, 8509201, 1609391, 31560287523, 6390916531381, 8682417911490, 3178088695956, 48272967082, 6751306933852, 56800, 31593, 5205856274222, 57918788890, 2355373, 177051085, 94620, 750792570, 2738357179161, 6793412, 95800, 36077951031, 61412, 30736890846, 25983, 18937520060, 2121457, 58444994000, 58438518633, 68800, 44139639960, 8194530, 1808548856320, 5301950, 5510215545160, 2201705185875, 8728177074670, 721489190, 4287933, 46773, 8857351, 96198923010, 3409983, 3855906724396, 222294666, 783784271, 5741088931370, 3805635, 37875, 35617837076, 915192970, 32885940455, 9912208764520, 51940, 6501025352221, 4608567121360, 6964223, 15965, 9726840, 6459553, 7820659068450, 28711, 6268493343240, 9136400, 4079342, 55406635824, 13937, 407785325, 699894440, 7446972, 166292148, 82576933130, 66870, 50680, 5527275039411, 6196931, 15684780383, 23471, 79344306861, 79394847901, 7812458181630, 4467081, 9215740, 625398380, 597161620, 92497519980, 329698432, 3235000, 79954373800, 58730, 72512, 630697140, 78600, 45770, 457046301, 6244735511882, 283686246, 930787810, 361596362, 716658720, 67163764513, 34018999735, 77039886791, 3964058638106, 93900, 89526964020, 2178230, 6288372445021, 78741, 3078104, 81281758091, 5817029595703, 30826, 7399130, 138470318, 63952, 4679778759391, 84083573630, 361587856, 74415969490, 21553767946, 4431498209832, 936567270, 88454956940, 64152844053, 28990, 9982010, 8499099316321, 96900, 989491750, 389198166, 7779830, 7576367500731, 12961808452, 84046337040, 19865, 4061646484982, 2736333, 634758933, 9209890, 36208946666, 226591761, 5685663897951, 4756806863784, 7596988902980, 72732, 43964, 8228390, 58862, 74792, 127996794, 33338572784, 79220712971, 69210815982, 94890, 17790987298, 91920, 29777991400, 3562391, 8527224880751, 51971, 512260020, 21527, 9394889958770, 60970, 85621, 9889570, 9025749204120, 249191457, 25781962195, 831072651, 8269759934641, 6437969291320, 95680, 96970, 4690049972085, 60913, 94990, 622297772, 96636833360, 14432944133, 8074840, 732381301, 3836468155641, 4934040, 9840154571330, 80525929090, 8354958793090, 13754829175, 66633, 1985539490641, 48241, 841453800, 22884, 55604, 646098520, 70090654310, 1027001, 346423933, 24654, 39710686372, 45552585395, 4861509913480, 7402944344812, 6161349860791, 95651709290, 75240937592, 9109250, 25983, 1885497, 522984442, 16489710478, 45187922913, 22790736836, 6459818000502, 6268193, 54954, 74950, 4857733, 2820637542114, 205863545, 61378792432, 2147768289455, 2339387729011, 7107863161010, 3967634, 27866769492, 8724514833651, 57942, 36743, 24674, 4566973, 56774746644, 73259983072, 14708904848, 949495270, 97532944400, 699492261, 8767357644220, 5928264, 237094715, 351277852, 62531, 23773, 370859415, 867588310, 994088090, 3073289220315, 14804, 48530505711, 4018135991720, 38624471574, 21052769065, 81855762250, 63862, 26863, 9325235443680, 46911, 5920285934121, 2748446825974, 635961651, 7687091, 1948293, 378441260, 564536512, 620470112, 6562088987001, 90780, 193790898, 14658994392, 12365, 41613, 41743, 988577530, 6673359751890, 50325616001, 744661252, 536392294, 5579722, 40110754495, 7068349169461, 516981561, 2856844, 96548627610, 66973, 54950, 786651152, 88970, 12830, 2341962, 373842106, 45905932874, 71018840902, 3999054, 48712761554, 418584450, 88077403591, 8389681, 9219020, 894798251, 55950, 6573015983930, 14651, 6722752466232, 193488155, 1986052, 55322, 16728, 7838019046651, 85555810960, 8113128594051, 71960, 83711, 96900, 855895970, 690487822, 21872, 7584051, 6458663, 12972, 43330, 93460, 1213779751086, 6317852, 3468776, 40910, 2104603, 4507405074154, 721882742, 11916, 45765, 421693681, 53504, 46981, 68542598110, 9536440, 4489273, 80598702960, 2368705, 9972237065740, 138794033, 26403, 277655742, 52482, 8407397882710, 361989906, 5879911, 7437196519991, 38501885506, 4742689566973, 92700, 8129000, 1483388773101, 5282082, 95544749790, 93500992090, 57309914324, 7309861, 288184521, 53331, 46632676303, 4178857826630, 14487, 30855, 39891, 10660432984, 5165134, 49995964151, 58928589502, 444079974, 5278204, 3814699805563, 25621, 2303375, 8007841, 848994550, 571480403, 8021788969460, 74491834912, 9099420, 78902, 13159974540, 2201076, 535088064, 752193191, 9786338038110, 7440719687301, 8928040, 88709856070, 1088948473992, 938039000, 93990, 2499435, 6172157066413, 61903, 9469200, 7990799847270, 16734, 7851625628321, 83667808730, 45890, 455642871, 37814563190, 9993790, 97261996810, 51590957824, 5479633, 4028872, 908868770, 481296715, 8179520, 9438690, 9544329642440, 56952, 434778895, 78921, 50884, 98940, 28974, 4351866693102, 34403645725, 7088431, 7418801, 1678231, 762620151, 44100825642, 22648601375, 3247334, 65284775262, 70871, 4476548146354, 2051798785907, 9199970, 9495979624970, 65913, 946596090, 3059022, 82283501621, 6769373, 2165309443617, 8669430, 4152518468390, 19916441906, 1687587, 40329847083, 811477371, 79005988341, 2558731, 946830840, 10253992871, 2821482105714, 6736970, 93709653100, 5579420, 89472559440, 83554883521, 5009462, 60723, 290490586, 33032854442, 4138145263935, 5179403, 16812, 2093393400831, 9163850, 6459730, 56662, 52783, 48276861342, 33355642871, 5239954467291, 77642, 4862019498614, 13448865778, 12373903662, 8873130, 24748809524, 9930796541470, 12300943668, 27122915292, 5153664614254, 3589115, 60179826651, 1859637603350, 641314450, 6693326793100, 1786687, 5597948085280, 7402665816162, 4120899168504, 9336888546310, 271793597, 28018959831, 1909253782293, 7342394203041, 29363886037, 78911, 532487332, 1167286, 26424762035, 1007687465425, 9765006788800, 25986, 3226508339970, 91284376820, 30975, 96840, 72323980692, 95920, 1028299181002, 850830701, 55933, 727782680, 492770451, 47541, 911159460, 20571980186, 9088740, 77950, 171675688, 372498204, 70956716811, 51893, 60212887292, 4690208328623, 5447563, 33318877451, 324246303, 39285617496, 133992890, 656616021, 847079571, 12358994395, 75621, 1898606, 6002377456923, 6559880, 34600, 7397373506502, 3355909106183, 76906609961, 4603028957992, 16197633636, 8743717298061, 13197955611, 26283, 604954353, 13990, 1891253, 7920174228240, 75085716301, 56572840423, 2975588653841, 5753360, 5837745147802, 12768, 6861289073523, 5492829992961, 68673, 2166849955631, 46304, 13538882443, 76649439751, 28100846593, 851353651, 7429769922420, 24723, 314656710, 697834073, 10924, 2729495917686, 3908741, 6404390, 48664, 4288024, 8464978727610, 820184000, 3618981, 166847001, 53595244602, 16130723328, 3439925, 72832, 1129994, 34573, 2876656, 21230890485, 192270513, 4421034870021, 72638529001, 865785631, 554395191, 3050276726314, 9647860, 2609779217051, 2713447, 828692500, 6428973, 69931, 2197071, 351938370, 3868493331603, 7198546772790, 43764, 79079854612, 7669669158851, 9070088190270, 98930, 27627912963, 74571, 37854, 9577310, 6160119466110, 5316296831972, 8738907505791, 223998237, 3029282, 75530, 39766, 10912, 6883703709201, 61722, 7598452, 58342960012, 87790, 679981523, 76941, 46655882924, 991482990, 474193513, 834177891, 62916908720, 8562356274841, 334098595, 1488901, 2894462700752, 9954830, 47111928741, 5357145730003, 4718944, 99890, 914099860, 4901649815801, 3069555732686, 399693726, 203399141, 101435523, 932249340, 5899842, 3319507493084, 8517491, 73276951412, 8556629595971, 53954, 3640909772402, 5468635035234, 68942, 972383850, 87547990891, 19995, 5931446533472, 372178522, 60551, 652974603, 808792711, 3229866, 348695044, 18048723747, 800782551, 4499674, 4844138025443, 4387543, 95537777350, 5759073, 72801, 81829847301, 1539096, 71188760570, 40781705211, 49531, 8135831, 49903, 5547954, 60991, 7167111, 28824, 663965431, 6927861, 34024775801, 8394191, 8538799271820, 4113098186693, 34620706244, 224275847, 49901, 365851662, 93143530120, 2629737, 52688959224, 7999699351151, 4038413, 813679871, 5249064, 10948, 21900, 92280, 74932, 43933, 25737, 4219592, 26672, 6114004740233, 7449979748822, 7529932, 4220669615014, 1255108431080, 150715494, 5725490, 8065000, 94441833350, 8969640, 89058877870, 61944879631, 96934737310, 54993, 2291578891305, 8877951, 3498459360122, 34482592516, 75333903550, 76780, 16734, 18923583923, 9174860, 82281960000, 46288881853, 65558704543, 618097833, 71728991462, 3229822, 51564, 61871956961, 913278190, 570498894, 7129401, 9198850, 575890114, 38992, 713557772, 6725119742403, 9059530, 8029660, 3788134, 8297731, 8020789228590, 41409833231, 90510, 919593850, 73870923040, 35763, 60105604240, 6516000, 76640, 841870271, 5607899902693, 60024887800, 92690, 3050059886130, 96176388790, 70844906732, 826397671, 486492764, 4368192, 1486315, 620468732, 447988742, 29617, 855397521, 128596998, 5749404, 61983, 9139870, 93950, 6729742, 492687524, 43805, 4279394, 6688501, 65437796340, 769065502, 5239000, 5426315280302, 414079600, 20883414275, 8253767567130, 3548178092980, 74279373870, 93760, 2152169997811, 5075083500653, 2028787, 12982, 5093392, 833171541, 89910, 40865, 72148962891, 85800, 52863, 77717872911, 9108060, 342190681, 37126456463, 802160360, 5046528873480, 7725971, 56054870300, 1512625753108, 788695371, 583689280, 311952135, 2955788223676, 71569869441, 42834, 1905288228088, 634595401, 54891763890, 407554513, 1794437888273, 573842070, 9795590, 137295902, 3233653606326, 6609542, 569985232, 579376142, 288479517, 9759580, 41691941381, 8845851, 9950389820490, 98900, 51335986364, 23996, 9558610, 36843989024, 484272661, 2265017, 3651769147882, 148153095, 59744661704, 8709880, 731185212, 3469983, 16633, 209742337, 77940, 9682887139930, 6239830, 7696991, 18828, 62523905442, 80308859221, 31014931951, 8414294632210, 5318440, 9205590, 21947, 28889966222, 6714451, 3667674, 1604027896253, 6531474472840, 874366620, 55870, 4034585663450, 5150434392813, 2989408077825, 426173260, 3630644888243, 5746183, 965285600, 119293712, 9435073966030, 37151957586, 9473399815040, 5165569313023, 42852, 6506283, 4289772, 70621, 22856, 41890, 21474, 734360572, 9166999483010, 515893883, 537085432, 23171792304, 94258643020, 207792201, 4293671, 645558463, 369199126, 11195985338, 8689800, 946489580, 533297292, 61623715391, 56349776034, 1609188, 79901, 9018500, 515593871, 7077836329860, 75119752410, 550577240, 39514, 29752, 9614910, 8482299912520, 5153778763554, 12921, 52638211464, 6549062, 78578850832, 25986, 6756248648803, 91970, 3905899782404, 86294773540, 8628238448371, 49309930532, 89037688721, 280398067, 72942, 11015990857, 42883, 3724357619051, 9890584961410, 9199889446100, 454093020, 5647654137530, 89689536231, 3239879793243, 5276044, 76903998372, 6564989989260, 969764230, 275692581, 7282373735001, 27805, 545376692, 607076942, 84881, 4239062, 403160665, 5919640, 20534, 35661, 46812487724, 88840, 9911638962720, 6569573, 1159145, 5014766176583, 70832, 921191960, 9579730, 488692241, 82511, 3740119063496, 7859162, 5668799881330, 957157270, 63676958190, 948661100, 264995096, 765484562, 11976, 50713, 648880302, 2978385, 28793, 8585170, 8592418740291, 427898164, 59840, 879656511, 81991, 7279100, 5727571, 92506601980, 26037982634, 65012633172, 7038720, 30736, 2729734, 25221692226, 83354894530, 125783456, 55721, 2176414, 4205646876061, 4187965395240, 473946163, 838279111, 368392393, 62633, 190291354, 73621502461, 32846, 285695747, 9509410, 56983, 33893, 7661696200950, 13914766624, 90315559200, 25184953677, 9959069850230, 11902, 264034091, 79302, 656491361, 1127933, 800740680, 178287563, 59464, 414794764, 70811, 9568300, 36316980470, 629231471, 30051775314, 9727760, 6299691, 4057852, 9406096678510, 28918948876, 9328780, 3969801, 55145471350, 70511, 923487460, 1977099998691, 9732790, 258699363, 56544, 41911, 51753504230, 32571, 3174510, 785537291, 55383861724, 3410769376842, 9505580, 32934, 109273228, 82729952161, 70509966102, 6179441, 3043647088751, 156546808, 80981, 6359751, 95526738630, 78972, 6615599391951, 88577715131, 10414993303, 6244131, 78752, 73942, 282994295, 5330607605154, 562694814, 5549463, 487288523, 56744, 17953, 831640791, 32077902316, 9719370, 6399193, 94840911750, 22917, 90910, 40515971163, 6257122, 4878455, 51760970544, 73902, 8819279093111, 60046916491, 2591687290912, 32404458345, 85019888610, 3575068263780, 6833081, 53926753092, 97770, 6149573, 59721972131, 1729016682995, 972360320, 521091511, 6326033, 8590169950300, 8442568239171, 48823929074, 274283744, 8006191, 43913998940, 80882481471, 5445329042480, 60522, 4160798849472, 29795663851, 412032490, 5574843, 1388962, 233330035, 95770, 645995900, 340261450, 5556463112991, 70315661410, 47770, 71254423980, 45487778304, 3138990, 40372, 196762227, 12824, 9439865660950, 525993924, 5733229754324, 959290300, 11991, 57200, 333350074, 8517060, 586787090, 72078550421, 10527884140, 6071710, 40260693565, 748796951, 34692823720, 1523063908565, 423065005, 74941, 662581760, 7576672, 3859983, 3623256548102, 40580, 1968884615598, 3459399482750, 9993833785480, 46751956844, 30853, 1033606171738, 71120924371, 676684540, 224360605, 4387171, 167551568, 905892400, 1689385, 9165646495780, 27227983156, 831184661, 4379139007452, 65630, 95252626360, 840895800, 64852, 1428334, 4875545, 9099310, 7980559387720, 7129197572712, 6959789743751, 6927802, 8424368075930, 658989853, 17906, 14672761577, 4108243, 43161731902, 427062624, 18002843780, 438610511, 543658510, 8075731, 440691801, 5452265118442, 31142702526, 66920, 291568692, 61440, 592567582, 876870080, 28690826133, 297050433, 427057582, 1951786897843, 1822984545277, 61079882330, 103064101, 2222011, 49835373330, 6434290, 916964250, 5022959519463, 18884, 37512, 734050960, 850072021, 83970, 3435188651161, 56878400782, 6697732, 18870, 3396281458750, 6283482, 12834, 1460815341425, 32648691054, 86730793401, 161893977, 30522883442, 1345252, 788836142, 12931, 5446912707891, 7466892, 839797450, 5355418140261, 82210674951, 644996090, 46465689833, 5247253, 54860810592, 95265709850, 541090804, 56967905633, 14805, 92680, 58667975141, 11183621051, 1687462995284, 301354116, 201997845, 8362377073960, 5775888871681, 5943686192751, 22642, 46453, 314175106, 8136009715281, 10985, 6366591, 62009702332, 6264048191830, 901663650, 12074998575, 56623, 141888728, 15671934243, 22882437140, 95704243130, 30925, 4417348937821, 51125582814, 59455937812, 8087680, 82800, 82305899871, 56450950692, 6656717836591, 1206377400241, 93280, 97960, 8699160, 3918196, 8579021, 30973, 29631, 6553523, 5629100, 4255865517811, 91590, 72921, 36856, 342697251, 3644362, 8616955464880, 24791869967, 1249428, 58422938392, 5897843, 67800, 89621, 4848349740713, 72761, 3498900, 15342, 8774683099420, 14842892232, 9343360, 6607909265433, 8439330, 38823, 76449669580, 87951717760, 511884681, 23673, 21524, 93610, 98472926940, 5161079911452, 35705, 909089820, 85991, 54912, 76439734190, 2743967215284, 23122637361, 47321, 8498665301971, 6759941, 3024477748414, 82771783250, 499288051, 88868573561, 472692440, 2944720, 43215, 233191874, 441564111, 53513, 22375895875, 3362897200633, 3756911, 41451, 777158101, 64853, 3309911, 5430164578290, 4935031, 3865170, 96410369320, 77902, 534594502, 12332793877, 70851, 59880, 82560, 8378970, 78860, 4288477723922, 3266303, 67660, 4356542, 84753631610, 92904882400, 47468979854, 750081330, 393671411, 6944110, 91449616020, 22904, 9376610, 8265529084570, 2469868104954, 341067723, 7326182, 49416962171, 73531, 771289102, 9632839755900, 3254419734706, 667490733, 6899143, 5868799754614, 48923, 90710, 81970, 39221812666, 4723299587302, 5475186052710, 1775854, 71580, 1977475, 3606046062205, 1318741, 557522482, 278275923, 97550, 44799981462, 674766470, 3921256743092, 8775810, 28134897652, 468349742, 36640, 9002013698830, 3399055, 91890, 1579394, 92838525170, 57963, 98850, 65457900802, 3947738567572, 666757620, 10612, 6809583155223, 8199580, 1201018557993, 625749413, 90564986100, 52934, 955595320, 63911, 8907931, 63980, 83641, 8692469493481, 3549706, 58961, 1248176871068, 443992044, 135389106, 9386387866320, 6199503, 8284949361870, 2688386, 8001978816310, 5578911, 2646061, 83320, 63797810252, 584785672, 41712, 71768675552, 959693500, 467491543, 1009177229714, 11502, 4902793276031, 5875851, 4066544, 49024853302, 39621, 6543314906463, 2776769062937, 74579999640, 58415718961, 22473608051, 46491300381, 51591, 74652, 28972, 772941892, 39946, 34418947853, 65922610043, 377397271, 7944562, 811996140, 1481648691406, 55794, 314793031, 988145480, 1109549898804, 48376530913, 9317680, 3069491, 11799463432, 2500123257431, 6287003069842, 3058324, 54417731244, 76843921481, 712589841, 4178910, 932545770, 6229171, 2807037319664, 56257680774, 69901, 42782, 61849659752, 34163889423, 608663112, 1990698356120, 48561129082, 3946962, 39526, 1299921, 7582891, 4898042, 417669155, 99182943530, 6629073, 6276079441352, 703686492, 417791220, 6745574918981, 71720, 34534723433, 2956550, 8868542697060, 51892, 7869457767460, 71423740602, 965491390, 8475799949000, 750085411, 74729859962, 205792723, 5290385437110, 49502, 25636, 48689849265, 66982, 670182242, 2297428564954, 4205276487241, 720855921, 92850, 8449419391521, 34031949785, 86834848850, 594586392, 443179421, 7035892, 7389791, 31846, 93978918880, 14568913822, 79342, 60990, 6046932, 291487935, 492471490, 748243722, 9225779004650, 2294229871637, 2739351, 17333, 903846330, 617698990, 383966963, 88670, 4988125, 15993, 6726454319301, 662675550, 87690, 88043878550, 355687855, 6108710, 3062866210654, 61528768532, 97313898350, 98980, 3202779873022, 245353235, 76199719940, 57710, 8745730, 673788802, 2800958668451, 724338520, 39763, 4596402, 5796443, 64822, 866482371, 39912, 55590, 13550, 8987011199051, 59613919642, 8198277452020, 62653850570, 5766840, 7775450, 12202773501, 109124335, 7940446291090, 49640723503, 9167070, 352691170, 49882391455, 65941, 945272730, 25300942266, 77209834560, 78411780960, 754772410, 606870520, 45624, 928380070, 21918946083, 184754141, 18218, 675194751, 64815708962, 8668960, 5718400, 94450538510, 42952, 57917665591, 73326612162, 15853936961, 776320970, 74839718670, 438270004, 5728762, 808873081, 915198040, 60982, 455383973, 389871052, 332351581, 64450, 764760052, 6709293, 63931907640, 22613, 772859802, 94716922800, 262598747, 1649531, 183926065, 16677, 7688840, 96527727760, 35991, 1603584288787, 9568470, 2704019071054, 2796696799977, 3099690, 887933970, 2396528638770, 16442290306, 766777251, 494685333, 99663746820, 994898370, 2419821, 940830980, 43923, 76814728520, 8108467423571, 746994942, 67931, 3187600, 17020395427, 580881561, 31632, 50326537644, 50529914832, 18287734970, 604710191, 29224768397, 34985, 84881, 6445129249933, 33031921312, 1112755306665, 404268193, 213475551, 66342, 357585966, 6195619367650, 90630, 23993, 2225421, 566238374, 6479539507732, 23816869646, 636080372, 57609823323, 65178817262, 59821, 8446381, 4849365, 48550938212, 91610, 97950, 5389874, 32954, 65732, 52485847593, 290081205, 729679940, 4626377079845, 781393370, 17721, 8352071, 677194292, 79699878691, 411682905, 91910, 1914359060998, 88316986180, 35351886571, 1135984421343, 713949011, 34842, 93169587810, 5019140, 8723365898930, 872884761, 43981, 3915075139936, 44588928515, 1978239105944, 131750933, 1453334006982, 13384, 28766558061, 34376, 9230009340830, 3372729475721, 8974931, 92405980060, 4259172, 141563347, 4628410, 5904343, 9450528424170, 774194162, 43913, 6074957897432, 85443899170, 45592874610, 786443212, 59930, 25364521405, 95095755520, 8089619709161, 98706960630, 7814279474841, 5528024, 23785906870, 75242, 580396562, 20364746760, 252724716, 339189565, 30821, 765848442, 6939769485971, 220274883, 200252324, 77670, 27733, 66500, 708060132, 848992900, 32035800685, 51890, 6795873, 405698455, 30528955951, 46403, 77721, 63184880773, 733192512, 9126849352720, 356999442, 734854271, 921284950, 8319561, 21757927847, 80410968810, 5888143, 3056768431805, 255389426, 9108820, 2525929400130, 767628960, 809470901, 677293713, 26941, 5817263654824, 51982, 47792, 13637, 24821, 5795953843472, 9948247331180, 724999180, 9980587606310, 18963, 78632462130, 45784, 2993778254991, 99851355590, 9061499715410, 638591173, 7809699249252, 3517069591814, 9579277185880, 65245976022, 3333518329163, 1606040, 727815160, 183074404, 6495233, 7319640, 4677253, 56450798362, 35784, 189177463, 623046642, 90880, 45904, 420387582, 46685, 63963, 9749090, 8329130, 1468906, 92760, 83951, 17107936395, 25615, 95655779210, 94720932880, 58740962212, 7477960, 70762, 76960, 51001794564, 3116369066162, 46813580585, 4853769243453, 4387882, 704863381, 1284718861685, 3146083, 3936792, 136957065, 76748679600, 216078203, 4385025, 152099053, 28413, 36904517904, 8117831, 91041978620, 3526869712501, 8634270, 75801, 628888242, 67196805052, 2508258785535, 60254797592, 1938916, 2697347393601, 8193501, 55914, 8471669385950, 911382620, 8479891, 93331903730, 74960, 898476190, 60840, 19900687083, 47260470971, 6970245195651, 34704, 6077570, 33715621971, 9354480, 9741519310970, 9874879613370, 4000879894981, 8217505714151, 38982, 91570, 34971, 268842100, 88250, 15491809035, 93621691610, 64810909070, 826565340, 38797866095, 11092812274, 5337375648403, 657985740, 84393635261, 4929353, 609173530, 1356626, 58660786721, 34630, 13360, 877616280, 58803, 24058889134, 3034876697310, 8063670, 3318591, 1383884925905, 29614, 298761120, 162622494, 3312925853421, 4279794279670, 1120564349214, 48564, 12871, 737728560, 203375570, 73292, 8029891, 9049550, 7111179421181, 53801, 207062727, 306695230, 302133374, 6870777076782, 8878150, 4338052, 70561690931, 54814, 5349512, 43775, 7041489451682, 61796913780, 5169446642594, 8124229300021, 4755849448233, 9907107627510, 4846639837903, 9158597604690, 155292278, 8399691, 352992420, 197231665, 97600, 435296815, 8310179722431, 98112976200, 228696764, 329868841, 18481, 13263, 8632634486150, 776589830, 7726467308550, 350972316, 9132019786290, 400398835, 65930, 355163506, 2581579349384, 746165692, 38022964460, 145830126, 1577252, 61110325931, 4057100, 48872415570, 12472, 95337364780, 343398014, 4343587788842, 4506803, 78683706972, 8273539096121, 9022209062460, 38900, 4836703617803, 86720, 3823608653312, 13502, 887636540, 8690758086260, 6098760, 2326101, 41850339671, 419057105, 4353889816805, 8790969836121, 1179804, 6075190, 56664608444, 34979961922, 33592, 178357274, 9393095483230, 243494144, 361065261, 826944361, 67902, 3148973, 86691, 863797780, 9368948247140, 4659844, 32970845063, 59684, 95930, 7453479104432, 399590006, 2462669336572, 8508914257001, 55971, 8513296308151, 9059110, 483791810, 221742257, 7319789653322, 724290452, 188197103, 451641862, 51673, 53871, 14674, 85511, 262296324, 6116136876323, 842590931, 454793433, 4787414, 68803, 8409181, 746499850, 9818987905150, 640899340, 2496276, 440186171, 1600275613727, 86881, 209295906, 401580150, 77796477811, 623080743, 5528439434593, 5646038910974, 6941599194042, 8178740, 767885020, 915272620, 649090962, 22803, 64561, 1497388, 93079903550, 2399644, 7146652, 325291502, 91530, 326694283, 49613, 584471721, 418161220, 5440534206791, 77120694850, 4867252, 9944616138080, 12495919327, 130188565, 813867870, 28801, 8182413229190, 4348583, 3804877806533, 273466560, 877022170, 90830, 405292735, 607594601, 971671900, 33986, 85921, 74725995160, 818473080, 595080314, 2649491, 2983532, 88738493891, 50932, 5305727487463, 68839842030, 8763916322110, 6004608757952, 827786760, 6498783, 5497469519633, 9946448208780, 140890471, 8692280, 4558941, 1665940, 434017305, 99313959850, 81930, 993381650, 18933, 94649402400, 2969614, 63531646440, 3258486769671, 660845163, 516299472, 63700, 6376993, 73941, 80860, 14818, 546591143, 98820, 917999850, 993295410, 4115429059422, 14094623450, 1095771281795, 373961690, 50334, 71980, 3527601, 4638334971992, 16686, 7307380, 730071411, 3868654, 4427461, 86570, 43824880525, 792391001, 853683561, 59671980843, 38093880336, 3649574, 6900367734811, 36792, 45554, 53820, 6901225329960, 2126546, 59155849412, 6165667609541, 557471443, 223483001, 68310, 101668468, 9043509145080, 82921, 2264819724490, 27608211045, 37637773434, 23791731006, 361485021, 73185454262, 3522069395266, 211091103, 285457333, 28648547137, 79970, 271471261, 55331, 6146790, 5281416511860, 39108503284, 21703, 115852325, 1796613, 80796433231, 344399811, 523243203, 4178732, 395864945, 7088908925411, 82870, 8232838721331, 8452949245061, 1446399321678, 4575709339862, 753764952, 320990431, 264647713, 5935994, 56964, 27551928315, 67732, 733488562, 8279351, 971992200, 18985, 4873926663982, 44712635684, 20887, 842397621, 69992, 436780203, 5934007496960, 8043505658541, 74981, 1900178318012, 53322, 9148527493850, 1449113, 218745647, 279090501, 4381753563634, 2778238513683, 1166705795071, 2712692, 4584581, 1694595127874, 229855782, 29233421133, 70590, 726071761, 34820, 61311, 5647174, 4473829433200, 31482, 70439571992, 1429574, 91783599020, 2669784, 6100556226923, 9139130, 44914, 7258612, 38994, 9727930, 9513139275020, 975990070, 377392994, 15211717927, 8452488412271, 57246969502, 109277011, 6820392364470, 99021689250, 91990, 896396520, 79842, 21971, 23241321605, 15733, 70010472682, 62536998701, 550670714, 32463985991, 63410, 696567591, 399775284, 89465707150, 64841, 2422337874006, 364081052, 82501, 3888309307230, 95118356740, 1858859995008, 1489302, 46015318151, 59574, 42903, 2297757, 8119430, 63810, 492262991, 511250554, 727693132, 8029490, 634382900, 40146636164, 9383298055560, 5377669903843, 7126828490072, 6269372, 13145804245, 40630, 1008974538422, 3743115, 5279848819993, 745084771, 235585007, 8089019976930, 9246988231870, 6399319413620, 320861311, 29442469026, 79094844210, 269177790, 44280, 6251514056090, 6426121, 13711, 23987288755, 41546721044, 1798398, 224191927, 86921, 18915, 28052648746, 5359968761400, 954957220, 51901, 108269461, 4348842179991, 4205621, 9195410, 37161951891, 4544422, 7231506073622, 40944, 6892408602711, 26629716911, 4098183617062, 77203683380, 54752, 503773841, 24813675672, 5124850, 3736065414830, 72459340220, 9175617480710, 827099570, 666186070, 2576994, 2016511, 5643702, 29423741414, 4856491, 81550, 34853, 95610, 97824929210, 57557998084, 8079660, 4778223, 33749743151, 158243054, 6135962, 3288282, 87607592170, 55842, 6296387378860, 19677, 3746458671860, 7693121, 708888680, 8808127595820, 1654738001824, 996059570, 78444994941, 7108760, 43552714530, 245547102, 8464640, 3718711, 66988447701, 12742, 801438041, 11844976950, 7334251602260, 32970776364, 8173607467780, 5485468070383, 11868, 664791621, 438374543, 35786759214, 4097387092535, 84981, 5679869964750, 259059043, 14545, 6876870, 9516830, 3429084, 139077650, 6350921779100, 36161625693, 5336721, 92700636000, 36894948156, 22465921542, 58902467951, 2676495, 193676231, 894222031, 2185149858464, 18806630485, 199869226, 357370081, 500247440, 750556482, 62287905253, 622395722, 4878581, 707257811, 4609488039681, 5035041, 50660, 502657244, 7670139489892, 4967059981745, 4689253, 305975200, 7235253203461, 7854218698701, 56761843770, 94550, 5189030, 37311583814, 9510217355790, 3189639994246, 53578902440, 947352120, 967097130, 4781549208502, 5366482, 88710, 770683462, 3399632, 13360534414, 5605991, 64557693791, 655277570, 548362082, 48724779892, 696466082, 61810, 6540926501782, 8513608126611, 79633909482, 40698940624, 215081507, 5805479193174, 17968, 795591691, 115481505, 534264632, 13579761685, 71941621201, 22894, 803262220, 9098250, 7334019164970, 762877561, 3868282, 10564, 28686517835, 42697766323, 4059867253173, 8913297801111, 6227229043623, 16964, 47253509304, 5298931, 84629646371, 1553469506294, 629453141, 8922097269270, 9332418208760, 8659310, 56967890383, 4246038302933, 416970180, 42434, 866680140, 40883, 7665637170390, 89751, 1750049074622, 1608323134127, 989586680, 82413924401, 58934, 3028449802814, 48781768581, 74580, 69940794442, 90330888120, 34034950920, 42390, 2168054768542, 825544491, 322496552, 195457067, 20865, 5147060, 66532, 75821, 23841, 3081253602976, 8469110, 631085310, 4863206983440, 9276544916170, 125895586, 93750, 634192963, 225294606, 35516828821, 6005612, 136987366, 4608137440455, 78257959471, 88357847961, 249497054, 91690, 51931, 3490846424790, 9295713895880, 6079372, 33750885075, 3390048532546, 7787199546811, 534186114, 5895429762260, 2765181, 1119663227976, 5150667623053, 4926568263572, 3376556, 628098751, 12343790695, 55694, 2435059245071, 477133684, 65620804430, 84968689210, 91840, 74065932641, 20386832440, 58106270991, 49799643242, 8646740, 9968350, 40942, 66653, 5648879956891, 85970674620, 26378840644, 729765940, 8977280, 4749678965975, 212992837, 70951, 324582372, 81550, 18810, 11256118677, 6958332, 301588301, 473346111, 11538, 505997642, 184475094, 48971565012, 4813566855811, 8715380, 74870, 89720, 700687312, 49210955405, 591198452, 84174789551, 51168907923, 62386820402, 27177813677, 81961, 63971, 67523729751, 8447170, 1948686, 42794, 70885883682, 319097173, 27783613951, 613732300, 5800906368794, 6482739530151, 48117790200, 59474406703, 507986684, 35942, 812254741, 34530943555, 887087961, 23945, 5287500, 38504, 63750, 7946280, 82333741510, 466781041, 74140539181, 501981270, 42231521904, 7882998495271, 5612538891083, 67842, 2322638766052, 28169489422, 91856451980, 5311939618911, 4720186569252, 6274926398102, 8003168751010, 2315458704900, 8192140, 60833, 3364779875254, 331576591, 1738614157837, 34975822370, 45304, 53406817100, 87962531250, 22841, 83370, 31611855190, 35376, 66017944183, 997692710, 3819301, 21211457552, 1173684529837, 22846, 68833, 195293192, 593531543, 15249821954, 5322545630763, 38034883324, 7817647349032, 42923946295, 797391101, 13431858226, 95062746680, 7953459717711, 845884100, 240983487, 196594192, 9259453574560, 28786916592, 544443780, 557958894, 30936, 6978179569590, 8966891, 5489701, 1296854, 8245121, 8496339680000, 90784807670, 321592010, 65912363023, 8586609906031, 505095023, 5908198433512, 83700, 59472880824, 85990, 8427518874051, 26154989923, 8843795729761, 5206549932503, 6650698064740, 2626796890293, 6861595911640, 41193675230, 52241410843, 1558276, 130576728, 23163959713, 4708255415363, 847975741, 47972, 5156253, 4008408450642, 3476044, 9476497894780, 9889770, 68920, 90855614270, 9977599974230, 91980, 1023169312710, 63181, 45702, 849964591, 4903719238375, 394694464, 16401777878, 45311943273, 847071151, 1540169024907, 9653958222630, 98920, 71971911042, 9417029172990, 58942, 1047358, 42983, 4096527707380, 849842280, 99512887820, 5469952, 7617040, 456974414, 6438130, 26790628282, 4604650, 1107664443977, 8678240, 6042268068221, 53774, 98376909950, 436696353, 760478202, 35905, 23896, 99800, 26213970974, 4013126337573, 83836703521, 4729251, 4755875, 1929593, 4904934842701, 46552, 796363232, 513292520, 1475467, 92880, 62458962392, 651189662, 208686844, 387162394, 641876893, 3991629146982, 32576, 5820039107254, 58924, 7325299363780, 3637005, 1098260, 1631176, 649879320, 7446031, 2558240, 474820034, 1488472, 91628369700, 7269001, 4488600, 5174270, 19586, 969578360, 30245968912, 21484594321, 8443381, 4869390, 10513452867, 3708860, 14363, 11486, 5301467328634, 27987991142, 37494, 2037497795251, 98592305220, 234393745, 937670740, 86980, 31577839026, 6179070, 973169600, 9280259686280, 160796993, 2605784335181, 98278379940, 900298170, 58982, 90915746800, 8579681, 47970945243, 243276804, 84671, 65433975771, 57723, 6888610, 59107652893, 17886, 7552017589981, 73468865450, 402773330, 10480, 4075061455795, 3479843, 63369678660, 77004671702, 24912, 1234822, 2608373074352, 56338494754, 5515659583143, 98840, 79961, 524181370, 2007815222374, 45682, 9398686581280, 83941, 88990, 3128885, 48815, 6539653, 65424938213, 433596110, 96490, 1189234, 4651935754104, 1698914, 6734095588360, 1496336, 93720, 854793200, 936882950, 844092280, 46854, 16884, 46513, 9217270, 985493530, 359391412, 6016325675343, 27983962256, 218184207, 61972, 4959828708332, 6583216717902, 54831, 92650, 58967995452, 84741, 900897390, 5042679374983, 485788582, 15967634681, 642624201, 22704, 307363260, 881936961, 8969811, 124893335, 936862700, 295993697, 21950, 115622531, 41273, 962774260, 85961, 65277927882, 62733832272, 4022588985703, 372874954, 59136707441, 4556720, 673448280, 18634, 688751162, 161880492, 3987623411932, 15541, 2742570, 6028972954661, 90740, 53931, 9994996535600, 82991, 61914977601, 9157930, 491692403, 7483137642220, 1305367124677, 74411801131, 345486701, 5095954868290, 98550, 5619603, 8189608670911, 601896601, 6897553, 30895917391, 9623274626710, 7749831, 218486860, 3415032645271, 2975454845037, 58254945511, 81670, 1863728152700, 685310381, 16511762030, 388611971, 580149103, 9538710, 8139991, 18467956755, 7146386311492, 17942, 4523002, 52644, 32924900214, 1710387454925, 6999596933040, 624860532, 233182196, 92955899390, 11084985362, 5860233997920, 20198511260, 7822980, 1375097570028, 20914, 53548612802, 37487790713, 678866893, 40943, 1097094, 684652040, 97680, 9474439277030, 40922, 3586383, 7061526338071, 1598626, 873076080, 7308752, 4458179144621, 6390915650850, 67647606192, 12851, 2545172199246, 499381750, 76851459111, 3492078075715, 59852, 686274393, 318792880, 517736971, 18223615592, 9063960, 1199180, 28197, 3715999742025, 9188060, 6729713, 8477109309241, 703290062, 3998069132444, 390079313, 6865876846160, 990463230, 2047139544593, 93479530910, 33965, 13861, 48251, 735957262, 18824948422, 822336511, 9119980, 5717049553960, 3729725047896, 1328929321467, 5913678995080, 3295302, 1685190, 5369141538140, 44853515345, 288398320, 28416240517, 6249500, 89898679270, 44503828992, 9146950, 341192564, 50724, 12954, 3425224, 26744, 76605614621, 154381448, 2017659206384, 84661, 77728902652, 628091343, 6890919710830, 9151506186730, 47808911644, 9112638215620, 5557139540640, 233359326, 33871, 884849361, 5159240, 46564530510, 98163446440, 4379212, 9566930, 2259000, 50665224373, 4886998394765, 87902908900, 74830, 93720, 257596991, 32700312670, 227033164, 336767243, 1686400, 4831982, 1025256066105, 66683, 64953, 3586769344503, 915665590, 65115962753, 5109664, 341692410, 25337, 59194968474, 30500933312, 33532, 37541, 27425, 98029756350, 58911, 909862330, 5119292, 93740, 18483979364, 7641675062460, 7327312, 59712921830, 528254111, 3694186985151, 8251084074860, 809782141, 9759720, 28903, 707157231, 20826, 82870, 54810, 863559191, 43953, 1367947, 356684486, 16421967567, 91860, 5339480, 8115701, 874497561, 7629702, 9369450, 1909957, 393184530, 9583540, 5962999912802, 37724, 88701, 36961970496, 3399112, 551456294, 808293361, 9569920, 12371962606, 93764755020, 70982, 1029809618725, 8046616152610, 2644388891575, 404673825, 47089950862, 77640, 5217480, 4735030, 7452684504400, 3160617032306, 3459562, 7356965030851, 506688132, 3917447883766]