lista = [454453668, 132580275, 864568025, 309911398, 300631870, 662029768, 746464499, 866869813, 131635341, 694525748, 418688819, 391646495, 389061975, 797557860, 259816804, 965335459, 404720478, 729220782, 936877221, 888453007, 263344417, 980929708, 882489554, 643671194, 382351933, 127597486, 415093329, 323120107, 311763074, 891598180, 335242924, 194523761, 650106080, 699136880, 498227465, 825462415, 105229812, 162073705, 174790376, 933284279, 899419903, 508816744, 112397063, 935518613, 148934837, 110518952, 526939701, 902377906, 963248875, 983328066, 542094124, 313694812, 161866643, 874279073, 415558480, 546734742, 254283821, 393186835, 893315138, 242752610, 546627113, 713740284, 128957122, 452445653, 772079358, 166827863, 531276892, 421667666, 479241877, 496688533, 917922092, 946733848, 655360889, 511478220, 263071008, 741137458, 400258881, 941718334, 219956169, 839822964, 910774379, 138627864, 445768179, 555561755, 465126252, 251917658, 307227589, 599521631, 484403893, 776373475, 735755319, 402491942, 694636059, 658652983, 670154005, 520234478, 643447936, 927787137, 636535867, 895319725, 177884985, 946885896, 623124300, 314569869, 501412473, 330593477, 394238633, 332057120, 478068230, 124721401, 185669682, 512555873, 313127749, 644914046, 483517480, 745177457, 581601102, 615128389, 150758798, 706581977, 167755278, 930160096, 265593440, 462641919, 149299918, 451308156, 770568163, 157493170, 129854208, 638884383, 832415058, 346186111, 373719380, 709591098, 419058580, 256291474, 996999089, 601248544, 126279496, 994216856, 610065306, 518380837, 114024072, 341741140, 152627989, 733812769, 815656676, 678800943, 727461484, 774030775, 338607795, 641934100, 738253817, 533248297, 854670919, 243066373, 240937662, 723589410, 702576256, 487823287, 270807580, 500188523, 465963883, 477617069, 429937727, 790199560, 429319761, 564479930, 223230997, 356289057, 104823064, 978509822, 935049136, 115530410, 823222968, 148560470, 982115343, 182281059, 109882788, 229321780, 994911720, 892216919, 955305817, 817293499, 128553704, 499729906, 446889279, 644090520, 313404841, 860379760, 837541458, 740103339, 126022068, 329865060, 408363275, 526344590, 914138242, 966535950, 557512707, 381739839, 765192903, 246713063, 776929277, 932479619, 833975218, 837106018, 672024802, 609871230, 106263342, 442556552, 897602913, 305358011, 824065694, 417065143, 226296517, 676740206, 687973491, 793180920, 688005228, 277315153, 993031505, 937063388, 170016662, 257197484, 166375390, 801325490, 896074757, 243367500, 743460316, 857234155, 151512641, 965247873, 398113300, 111296322, 639297452, 742227217, 316783229, 619370704, 411926716, 549473976, 944656216, 780571324, 343920800, 107087665, 779039563, 815948045, 338604060, 964154750, 708285569, 570769645, 236482771, 937348929, 707449017, 454046479, 133555841, 348680696, 919922772, 515732817, 588419393, 129429140, 354421886, 938927551, 491801511, 396730002, 926792281, 672611963, 874344523, 133775727, 899871561, 312331271, 961416608, 650156589, 399706599, 403246378, 214999002, 518381656, 891159416, 851198978, 252682440, 961421979, 651613932, 580121019, 794368869, 299702738, 204447139, 516676018, 943458095, 813805169, 324828654, 220932010, 634610595, 108989095, 533610076, 693628385, 588902697, 741550323, 910994171, 788950111, 917816360, 514309847]