2
999 5
720638741 816215898 1112367314 413714553 1762709256 1502306414 317137876 514566685 1314850780 611204387 692126794 833248122 1703933063 1712029882 930086998 711583979 1821001698 1188955198 121090892 773902131 1323798619 90085166 1661963911 1229153549 392305913 609776928 510066710 291164577 501806372 1080143173 1022004938 1222444114 1896358072 134372251 1636157667 1511582680 1489193019 1953294543 26149364 656559151 417014282 570790511 1489806273 120947345 135335746 272408623 685045677 1956336444 1461362822 658650922 582753928 637676793 601250441 97233191 1866829343 993555355 707009119 229411405 1284718932 1208814491 1309553579 159239222 283773957 1058427003 146125827 1919930625 422525035 1635317846 1725740520 301188752 144392349 142754802 871978264 1634197622 116216500 1007313010 1906605245 653776530 816164806 1220483419 1312426452 1398917734 1858159213 1913675894 1496149925 1577503908 759746601 55674396 1806914313 44465532 1264487888 968983244 56219107 1548260845 27410246 202343934 1320706822 302449634 1837660780 898962695 603637387 1982052129 894231850 1475614651 1468765103 862962703 335443013 1227885701 1516738233 1151606819 300884472 681680037 403039906 11559037 447871283 1899188831 1589061945 1207616884 1954862228 1248491611 1104596769 1071865468 69990207 1160814877 472641665 97399454 1363157811 1793347488 252363441 1053333944 544825535 855999828 887901425 1439056385 184129831 209181881 154534440 519571844 1437066582 1671271673 1671177664 1737950054 205467062 74217569 1749508092 653337346 1825920753 1191085389 1860953230 1633298333 292092352 818065352 557679153 362081560 1978879229 1030319819 311995367 1194552392 676182659 564357808 100401688 1221007194 1420356637 988302114 512578931 1604485468 1197482995 667112371 124057312 487064929 190899396 1647749329 77530335 396365458 1574481251 1827037427 1049701804 1252917356 870638169 763170387 738731042 1162729521 1581234739 1296409195 1524810081 1412629320 179244366 1836804448 459697064 855426025 253677609 560097753 76433218 1674033246 1548398867 441526502 1131034066 598397214 1108637873 1107605731 1085461143 1299536269 607870412 1162990478 1695900728 34867015 842543258 598117884 1287783372 1713180427 1361287271 26514413 728425300 795037362 1175437961 105750734 60182034 1354681328 1942554182 519878099 62622705 48747143 1079974852 139054924 1722779389 480889071 433095779 706328808 1079285285 1541732653 1813933539 17261780 693784274 274319304 1180251258 242200354 309185319 22794515 840317239 1596967691 1588489295 54119862 1475996457 169429948 849156225 503949771 275179682 909337259 1858630099 70249216 1429214358 1921251804 118995360 361704562 1912821081 1841773749 842592633 198432213 400617909 1921876918 1740163866 67066801 1939137698 286463492 341385105 971904309 528662847 650569424 847213177 1368979086 100052468 288217825 1423097948 1576047925 457646773 124769525 79997695 732825455 1034105785 1791142147 803073671 315835495 1564909304 922068031 677539058 1330245737 616357133 1520130691 1528676950 1016974042 1294522962 1121356168 1084039843 1086176012 1407818661 1425423948 58080320 1936480508 75993372 757807851 1157974946 28560193 1046024676 433588246 1604607118 1503670449 558356772 1537119167 89011256 1592461557 1180776666 892083927 1908296052 598201322 1814150959 438350462 1928446060 283023444 1958480154 1309638362 1299996486 1105518468 283509883 236551682 44209832 1691327544 1661974630 102289153 1480323404 1590482355 712611357 490813702 1619041548 1758635033 924400948 1076164019 1114820834 1482756720 465798538 1203831090 927733629 1646574204 95915016 688545034 97290879 1762580328 1126894496 25736938 45603771 937890002 1187889653 1198114611 43408469 1471398536 1434665293 87617302 1015241432 949155275 42420808 348080188 392152983 607546518 838892890 11194530 218696903 1763292839 939872902 1333516737 1098564911 1405670440 389863179 26298540 904759997 338292548 567357927 1002049876 100872876 1694251423 880301167 1998990001 484656778 68190819 1049619964 380579600 1392103709 336800609 320711255 259860493 1285954885 215646416 607939682 1678106868 823191934 1446831572 1541815751 1041887837 1062639763 334204006 227919926 13720027 1739873446 617782105 40017567 497148795 956073654 459889847 1499197671 909460883 6656622 232014190 760966236 491312400 152719363 1810585201 871891001 1544822072 147385809 1192601256 1804681565 1285855047 1408246673 265136599 816477267 83953959 1711967172 210808371 1125840797 627122287 545011377 1353759723 640841314 137400175 1971540829 533373234 634547971 780129835 993262081 133745641 1689589718 999917704 218274185 303071306 1491229104 370992548 113656506 215635457 1915813620 113556669 1408235714 1573010537 1251926069 668997739 1838146137 68403336 752950698 1402628661 131726060 1878790495 29750947 676736437 1085065571 523106615 814135612 909121752 1056478849 1448682583 1689250587 49740930 1434942578 1231355657 902172987 1653215763 1534425963 245917443 24208310 1500596823 461551901 1792536283 1466667845 1869786615 1218062172 571109266 391299706 908723661 492026955 1144249404 163867674 623752015 875555252 46132975 1300487452 1960619823 569238590 114623064 722256927 1625716439 1415820000 264022866 1527971722 703277930 1495377523 282660061 209009045 882318838 528576505 85731708 235431013 990127406 1878266991 1702097858 712429373 948844516 125722477 1103728079 1857567177 617748432 100492835 21434851 1241499448 976047087 67566826 394502252 789182262 489319769 361639669 1511438189 115036207 1777458670 1775460055 1495522283 333251952 1123352930 1778181344 542259998 5671768 159273201 627990706 93617134 1149399607 358773050 1795713993 1861827980 1307616566 1921435470 818071411 1017699095 391699254 918563247 891648299 1633197702 1894609334 811729478 27699954 536306949 1301048247 241853976 47745137 1268598808 19312645 1675719546 616636443 205078951 651587828 247333139 747337949 509773949 406605341 1375327655 603390084 1556003948 1734099705 251619429 1270347281 894231623 25570251 88418691 1911929719 417268505 859496291 656093370 50466207 606620978 1467821849 1930679515 1142926927 621385448 25048843 1043186417 1889983256 44360489 571421315 359135051 101953793 1223008144 606467191 849290742 1732781093 1013071532 77133749 188686529 421590832 1811232455 440304958 1691937113 557979430 465874209 1632870158 322424501 883141715 344881801 978516872 786122275 951501779 298854073 569317142 94428705 920238521 594364985 990129476 662737130 491239827 1561549791 1021871181 593192620 637073287 1628337372 1442482362 222369733 493924256 1519615112 411055262 915514089 1183362919 851359221 459966554 1741341349 1317232430 92836711 63765850 52889497 290232866 894797075 839010772 1241733645 1193650148 1408326914 1188676704 113888668 2691899 31321532 629140151 346446079 1592870323 1651010333 939637700 82458963 1131863057 234635414 304827696 1625786314 1754249526 715881958 393815755 790127797 1567240179 853781309 383984499 736987962 799132374 300264702 789876459 1089364240 1195060777 1628886232 183613237 241226277 889728498 1372288941 207629298 744934750 1403609473 836768450 1091379830 848995149 340294135 31017529 931453112 1472156192 118167296 1236279808 950457858 1872415823 1952160766 1344272613 515058972 1371916298 50569275 899042471 108904259 849700649 1199306173 751295071 1939063889 246882302 232696655 122677125 488107579 1122424154 1347480420 695735878 1867357904 603605245 1532503328 811253086 1452599394 1872796463 694784968 236567858 1197468007 812951265 1472846666 441218 537882440 1277522785 1344712831 1052940412 501954435 1395281106 1951981884 463373047 97497107 1003803409 1214667118 36560995 1250684712 1447362774 11752474 1738791291 422302280 1211747247 287042521 142175536 1815351492 1819544849 953427623 1120466239 1544856664 1648211591 1357033097 594840024 313678208 682395116 595280242 851559648 1959916901 1939992073 1904499061 314386688 1187788532 1708996297 777758735 1285284639 565315058 1992424853 1174359988 1815998770 1292302979 1038626815 1407305414 1714604259 102889414 1694346935 1856778796 1918239906 1366407137 662721771 891221497 763779153 163448714 100769947 1358618177 477125923 783164063 1953897419 1328684571 595596316 1746404845 1085698984 909982004 786708729 647210633 1687739739 71993367 1212524692 1532679944 1098867708 881038814 677498276 137494522 140859580 244617887 92898289 1835205516 101396682 11138195 1054128005 616632806 754874045 1817906158 780080521 855642992 1029039688 1257205444 1638806055 835452459 438405367 86917723 434372656 1524103352 996898727 1221080385 23829337 537153818 1145588106 1236353029 69833762 96971166 117391843 599846391 86980042 110765776 844463278 179877331 1945970292 798374314 43529879 852613649 1415006120 798402925 523035160 47601993 1654044917 1552073848 1304806437 1145366325 240041659 1743210805 1232283048 674413316 1119829509 81697128 1895492701 1143657846 618849946 893596159 232526228 541198061 990566326 202432424 1141043452 1077545368 313197200 1985505731 1257421699 111682845 636395397 1300950579 964295494 51401516 99353503 1487329654 99002510 1605912773 891918854 1256323300 603794450 1131959514 852049457 1836076499 1806371830 1971877966 1917772627 1554379883 968051165 389137925 300491395 1200576393 930334987 1291056721 1403007817 71378438 221117441 1716204017 1909398522 1478538140 1827885862 398309271 632004071 644696709 302225141 583871927 132026362 253742004 42300053 876459570 1510064304 646093503 8419083 214629114 334685354 1667305266 39022432 104973333 1074200501 1007072597 494110259 1374690896 60164342 1424444246 518262969 1463171159 1348337037 739379410 1031890529 1110250912 70432903 712291743 1508559183 702435974 1356987452 1810783324 1286306902 1341528168 64525327 1328605955 70503090 1427103985 1974698458 78921173 1641732099 161899165 1598740792 1680753531 266871498 525456645 540341481 760980757 1900146542 600504823 37940355 270924863 63675982 1386276393 1010303274 948080864 349042657 1080735177 1660371607 1857600840 1783170151 869874412 1520899517 921992405 63917932 1437939197 103113712 134420022 717558534 77812170 65855548 211805985 92225688 1664595340 1892558517 359096186 42567337 285415350 1120075944 1942712879 885919173 1158015299 66153095 802109508 396807044 1076455369 1750189372 745848701 9705898 1263076332 455964894 1792875049 132950743 1976863411 567382807 49383028 1267317960 670495519 183802050 1984875495
