lista = [89967103, 50969368, 81585319, 86576334, 47323494, 87500877, 13854775, 22434731, 99942372, 459745, 34396383, 71006516, 95010337, 11490201, 89040204, 60774564, 89058760, 97976808, 37153699, 59169954, 33227970, 24882077, 31296990, 13852294, 74170790, 3473860, 31445548, 4734051, 59600508, 29857152, 12995968, 63292176, 45445138, 6550058, 1206817, 97250653, 188425, 23317695, 47314009, 77285573, 43402625, 55074116, 30435161, 90395214, 92870007, 36519082, 91937179, 71963436, 53435214, 52013588, 40414228, 56294041, 46070719, 43638971, 96510937, 79892887, 92069687, 63575809, 48070523, 83690893, 76615264, 50219284, 66181163, 60558756, 50667101, 94411995, 35247720, 7296421, 2212220, 84710291, 39779329, 38613049, 29772374, 74501913, 21366627, 43604101, 3926322, 12909635, 24708225, 10986952, 90375194, 88571727, 64355901, 11237829, 85966118, 39056107, 92533518, 97454070, 94292469, 29606596, 55003085, 38564954, 7211659, 96902378, 71793879, 7464304, 17034288, 39408777, 33037894, 59415425, 1588675, 57925711, 83866650, 33667681, 37677102, 92138947, 17526663, 39435080, 42585559, 75626499, 26348245, 80650944, 21298327, 54571983, 89966765, 16035863, 78038017, 13619061, 40878560, 64949878, 65147165, 23545950, 19929965, 98706756, 78187878, 85683055, 84096056, 22385586, 28498248, 50697434, 5350910, 36799225, 83969427, 40152579, 63076505, 57313519, 55347653, 92952794, 28646374, 51562685, 91069129, 91025501, 82002735, 67039479, 24435601, 92480048, 68535879, 35609892, 85525487, 59348426, 4936299, 47966134, 47263240, 68816572, 76454791, 75039608, 81125079, 62828369, 65875231, 42391173, 28436031, 61472549, 15009892, 91112344, 96840956, 73035054, 50307820, 22790306, 7624039, 50111356, 18537122, 91700463, 87910970, 55379248, 75854685, 11407166, 29684960, 95625633, 25385805, 24808745, 86089906, 32875645, 10679004, 67320410, 35473945, 20027133, 51249856, 44700343, 15671551, 45788256, 47093122, 31769177, 3229436, 10344390, 3024218, 57822472, 83911696, 7092010, 96950994, 532189, 98560618, 5189124, 60873040, 84133664, 39635873, 27074259, 84791705, 81593000, 93492793, 52912347, 84185369, 86215649, 29988180, 83623124, 45162906, 85788139, 26657731, 66652838, 78647583, 48943767, 62380396, 21294692, 35127040, 75874631, 79802983, 17958373, 92273398, 22340793, 33654885, 14425874, 67901274, 3689890, 46083815, 73105961, 94321223, 59231352, 13404183, 9308448, 46502862, 21561994, 98451113, 28954702, 59277730, 39611410, 65852573, 45607957, 87580433, 87196952, 57660097, 28317796, 70152658, 8653243, 56434427, 26672634, 21154373, 79122637, 21718976, 65202218, 24955830, 84645416, 11783493, 83203939, 15958675, 17882308, 22428443, 24797017, 49408941, 44630338, 16388475, 96230047, 28978017, 1071562, 72516835, 62500038, 40722477, 14544299, 47418919, 54436843, 87393277, 48048244, 14001405, 30017034, 69593515, 38001786, 60732603, 86522583, 47937976, 8705792, 23467622, 65206346, 32416658, 70172154, 15046841, 68701572, 40523400, 51340710, 5918803, 29332854, 95791277, 47876099, 1350837, 21785205, 42091268, 8954852, 41510631, 87068667, 12522635, 59214472, 68527969, 93495978, 23562308, 98342266, 92793682, 82357713, 7451272, 20009333, 63536959, 53411228, 80659269, 97571546, 15965807, 72963947, 16536850, 92456223, 32160621, 60702247, 23030714, 76742327, 36368639, 64905362, 4184344, 2174760, 64152494, 88437759, 41486852, 30357083, 90694886, 16851267, 94214440, 37513504, 59105574, 4865582, 77109928, 92963906, 86820413, 13829936, 60498789, 85458901, 91136603, 91538744, 39512957, 81006825, 18669608, 29649399, 26564944, 80264744, 44330022, 22778789, 21362069, 16001232, 22634463, 58672214, 36530048, 33318567, 16751147, 27852310, 80152932, 36681080, 82444364, 29585871, 72403962, 40189812, 20413904, 38750339, 791387, 23262873, 92897311, 55059420, 2469805, 25464325, 26873479, 48118202, 6692762, 24463836, 14147357, 5860338, 85142671, 86642153, 41602490, 28172157, 94894857, 99619630, 83454419, 7104132, 51416598, 68905803, 35538473, 9390786, 58732449, 41422095, 863422, 3493658, 28307660, 3814262, 17411918, 44774021, 26766318, 57313041, 61575302, 3401308, 21013419, 9072219, 65244478, 25686423, 87854605, 53600165, 21387845, 24772498, 64384046, 55422907, 66280925, 78668110, 8222440, 8931441, 9341105, 80254548, 67942931, 25366600, 68382041, 71561980, 55410635, 80939016, 92093960, 10887434, 22014330, 35955127, 61476094, 10052174, 62703123, 98423414, 53853034, 19205811, 22300679, 94978774, 70802691, 15599625, 16456752, 49093817, 77248438, 48765800, 58286189, 58542829, 77342269, 9930986, 25223550, 41103007, 37951610, 50814323, 53934236, 45895388, 74808806, 32551136, 77792086, 39909575, 39979352, 99112088, 53513876, 47469219, 21112104, 37062614, 79180248, 31000915, 31796780, 10229850, 30240828, 33288798, 62606551, 11958560, 83320834, 38523342, 50122890, 85343514, 43222661, 26081409, 63470120, 86336255, 51621512, 94136105, 60081986, 82739253, 52533679, 40689717, 47364490, 45263181, 74254225, 94390926, 94500976, 62700913, 69297911, 54093128, 76979853, 10001811, 99038911, 61923238, 78128287, 59355102, 67408740, 21982900, 92368555, 68051543, 44168494, 53875657, 90965141, 4768316, 65038871, 61462081, 7472836, 67059444, 96356683, 67889352, 52052024, 86152289, 50754731, 46038433, 56226951, 64122622, 60960539, 39111484, 6832762, 69444684, 50231806, 24548768, 29126752, 19528114, 54838721, 78634881, 46606925, 55753446, 87576498, 87652547, 62117612, 65779734, 43773490, 42678340, 73054583, 55376000, 97146965, 41503668, 55214448, 353988, 41394644, 26149110, 95978899, 23177367, 32766795, 44176513, 58083091, 47259063, 38541483, 70240572, 73706801, 77901266, 6736070, 48909817, 49350050, 27781291, 19865816, 65433793, 78229294, 1464967, 50477857, 94207208, 3157013, 19061173, 68039471, 58582151, 33355218, 95404464, 54008990, 70043660, 57640223, 56019700, 79469587, 44763078, 4172107, 33354220, 7723770, 37901462, 1813350, 60505535, 15591970, 8189052, 55484464, 24560368, 81032182, 41266496, 49704919, 83719950, 4023391, 73486530, 3642548, 33371494, 24128294, 17388696, 37857137, 46626493, 11014252, 25526414, 30553616, 4185334, 78087959, 65934217, 15355578, 76816108, 94943709, 83243681, 39433889, 88371678, 38281295, 21774258, 47621867, 17737659, 37961001, 95705175, 94098108, 63539175, 71096970, 62028142, 21813585, 24994212, 83126031, 48385372, 11860359, 71274245, 46207462, 21515960, 86921769, 12251177, 55629074, 1866127, 85878664, 17780071, 85911234, 56002413, 1920336, 80183792, 66757145, 28125023, 62929412, 33346390, 85155349, 37577006, 3834842, 22402006, 88856582, 22768650, 22656794, 86680158, 88496503, 49772957, 64207653, 54618904, 47821819, 2104633, 59629776, 81928779, 36024542, 6083051, 86116635, 7192591, 21195765, 96564920, 84198026, 22091995, 24061803, 97876131, 87355765, 76875482, 59487738, 96576735, 53787519, 72182343, 87735492, 34533670, 15674959, 61794880, 53591291, 748131, 15179643, 90776946, 12721932, 61333252, 73598435, 55224793, 20921080, 70809554, 7519742, 56528610, 34526969, 75083802, 8532138, 4916363, 31482293, 73735216, 99781619, 5497073, 76655720, 27571047, 7015642, 14934590, 38758297, 37665935, 31988313, 64180703, 48637401, 45235605, 87500359, 69288443, 34322042, 43037093, 39157644, 12927850, 19556651, 37807036, 5725969, 91234772, 10029932, 2669803, 66190006, 84181266, 18089029, 5468062, 31597499, 26111534, 41362902, 53584146, 30328540, 87399771, 92613823, 97135415, 12446317, 81615081, 97122538, 8475605, 7629684, 38544710, 97664088, 54159152, 90541536, 66916834, 8644649, 13439076, 83011224, 26900938, 51177024, 37907469, 24772101, 47960161, 28924584, 1431113, 71003935, 72232365, 97726788, 42155150, 66472294, 54472862, 42915079, 3429477, 36398796, 57394969, 75897715, 63282573, 67608376, 94574383, 32569119, 36113313, 35668454, 96574500, 2955950, 2297453, 15060587, 29331227, 74262686, 54195210, 88448803, 31752497, 42748059, 86253336, 80187064, 22489012, 78929569, 22282771, 83779339, 47516956, 88384602, 9356224, 16371482, 53636387, 88002300, 69088658, 41683788, 68283481, 58646834, 2738726, 36729978, 83574820, 99971216, 1199845, 30918226, 92098655, 54530984, 17281363, 71185494, 85480423, 95137304, 20560506, 17312490, 23233394, 48903914, 81170758, 36346646, 41503636, 48621187, 81873706, 80269952, 31368496, 65287796, 53465750, 14193384, 81557982, 60424900, 92459608, 46251790, 81580159, 22720734, 12967635, 11980594, 18319207, 86901747, 31108220, 39073314, 38831934, 34219034, 63242914, 18577877, 88428053, 74511530, 87457069, 32860912, 34753819, 74791430, 82496467, 24534566, 55701116, 97731668, 87391362, 8837172, 23295363, 88547620, 516119, 78497756, 67059947, 84353536, 31484870, 6345004, 10419335, 31109843, 9293292, 46309365, 32025626, 43314985, 15451713, 20546304, 45928244, 83628507, 88386808, 93505965, 3489615, 59723335, 56649660, 98390158, 37882139, 58266565, 47911456, 29903757, 13134852, 74176579, 63693776, 36978384, 88331250, 85840286, 35504200, 29286451, 48450653, 17980121, 70813621, 43963704, 52672050, 13078557, 29224440, 80979236, 56015653, 80320120, 40642888, 62847999, 61075146, 29018948, 49731882, 52373580, 6376861, 15574251, 15149099, 76561325, 50634218, 9184050, 8348967, 21010976, 48103398, 41558087, 43664046, 33659043, 53974979, 58434539, 50710782, 56719142, 28834582, 40673046, 53719892, 80135180, 7383739, 64241319, 81802602, 29702191, 94282262, 21245592, 83867238, 73446813, 45799789, 94583471, 50061779, 28279757, 56857963, 2284941, 95831006, 55918859, 59712560, 48785704, 11257450, 16198286, 87182553, 18701090, 54556615, 51986021, 69906543, 23923888, 44516994, 49236821, 10032409, 835866, 43450031, 90652856, 19167092, 70495799, 3389881, 40447712, 96335429, 71066178, 89850066, 84118832, 31518079, 85208444, 72052080, 65813051, 39954041, 7255788, 53500481, 42658999, 78647712, 92986181, 98512839, 9441198, 83505157, 72078032, 99239382, 86668489, 62885343, 96656826, 50320268, 1440964, 71938752, 75369351, 16325421, 10261182, 17876855, 71065273, 32156040, 20660828, 73446758, 97867748, 85332300]