2
1000
13042 6545248 451 420796541 95466667 18 32 25287 6034872 327436 30 86 27896 720208 3 375295 2 1716895 277141773 554972464 53207 325677210 954817 515760677 980 5889 110415883 19155456 846000 632439 40222 2006433 7401 1 840473322 971275049 5983724 85824 2976 2886202 1062322 50197 15 86 44742419 32029 215379887 6711225 8 7 63972329 830795177 9596 28168341 186 7376229 349286 20423 405881 285636623 58 90 15553 7279 5 758664784 7398154 285134 4 225110247 898 5 257 52137912 77833732 761295 480823 3154306 44566470 97786763 729789422 35495 134 118330 25338 2481 42 865 9564958 581383 2128 37782 23048 9386 48741229 1893 1 70493 712257588 574502604 35558249 18744 716718484 15 5368481 76912435 30457567 9 75396 8825 85410983 60390518 725836804 17105 79065148 372 974619858 861 8 4271 493822 91314943 75 198976247 8050586 899150 184615987 7 5487 9 24 718439363 517 2752385 424475 531653513 6627862 301096 14 3220816 794 3 60547409 182 9579587 5007060 364978 17917352 566466 15 650 1297 25992 30720 98810 79736656 9325 4 501 8 79540906 2976963 25 77544915 190563338 50 2 345792576 48140724 32117 5842 8 2425 75 633027 4616 58908 884432 3 385842308 3920156 266 1209103 452445 3 72954 460332 6401411 71240 2 344 940 94439 47 8590 16634107 22168 739 5995173 728555600 939673083 93736956 26 443154102 976714017 4795 48228095 62 679805 36465221 47748923 6241 3 70114 635213 7 8 51125693 21 723 619806453 712938629 24 591838970 46349 27724 363 453501 96 1099 144 7 3 5845596 8832 42164302 471 61 572 385 63 1431826 25 597074312 35 53475 2 4128687 46 841721 935 115 603 676779508 201 462198 330684 435 33093961 34792 6 66702113 11 6615355 540 879921844 8136 19 225 26455345 34593 53 89483674 61 760 55 95262 729805 5 87 3168 98 406488 52917553 125 420188 4012 6106827 391 892105594 741 36 2535 65943 671592 287253142 1006 636763910 5137794 997969481 228 5 685576 36 56778151 35 36 4991 6387 4444336 16309181 919973 59710654 95052 3926 89590407 17361 2 479 163512 543822612 216377846 557776913 17801 2873 823051943 91 374 9 1240 8116 500650412 549439196 84148339 2728 59419425 512 992726482 5610168 30312905 4318177 73934316 543 7311813 294782 7 77 49 877 25740696 2899 529677055 3 61449451 30658 91 308 420801535 87635915 72421975 770736389 57887252 5200768 716379560 9 2962 8600 117172 94 3547 33811310 18414651 6 641 96 67 59846 53987 81 474112 87 178411 5104 708191 947697 424122 41740 184401406 78584776 15103249 405044795 1363389 20 46 99116 155069 9855 501381274 12528738 32 335489 167404334 9 34352070 4242601 676280335 73978014 565 1 3 1590 60122273 967170430 1279 7 50 385554060 6 1 486648789 28099573 5387 6123 246012 3408 125766 50 13811307 1 76338 3767453 8533 747474802 906 5573 799 223172011 97237 991 27021 1546 4607598 908 15582556 6 54 9349910 234281 38353 8 63004 52 348921419 87406 617 33588 38577655 83858868 1793 90044722 5795558 113115812 717 616164 9691 263983 36 663276456 5274261 11 332591777 60161 76694518 206467289 121219 57 74 24397626 806 932 493407 33939835 5266401 63410256 65060169 873608859 16565311 7 1596975 86 6088 40 9 963 6669 275 4 7 957942943 3239102 236520 6686 772 70 62 13 4842639 772220 640 25646193 701839 7 674215862 149 575121728 83 67 771856 459302611 7 9949712 9996988 62439225 16 56 1954 5 67 548 62755 36562 70046 787343845 661440 36 8 344 4211290 65126564 45713 21784930 781196898 5 78 6885 648184 2 471 14696130 200172991 95 16 4646874 674 21090 322 99328781 89407 938 260 29405 66761243 6806 489846 8 2 435209 4900260 979030 27856 82 5056768 209132162 5993035 923858668 52874 14558 77084 27 24 77580 13990 1261 42379950 6357 164 73155445 579492169 2153 927077 11999497 84 38340618 391730844 3331 83 28576344 115 9611667 21331661 102 868646463 774 418903160 102173130 37064045 492274297 4 87715472 4363866 593 9141745 934207 9528774 3 12 47 8 91904 457 8 8 317642746 8406258 566928 910 1 2404498 63824 18812 2 50 950 377584711 803450 2 69790140 6200 55961038 1059169 735 517306704 7 93768 951 696209696 1432954 579504 1190 975048120 49 94639210 952 750177563 256 4150 67084607 4603849 2552808 5 904688 64 31941762 36777 72760 3448 2859 838 9 605173596 92043116 89 1942254 52393215 971231774 40904 987086624 6 42102907 6307127 355420 10318134 66339 116 5 456 11754678 7946931 760 2326644 403 421 146074746 933 478 2620 96266 3 272840085 218412724 95824154 4814249 9259 78523 6 5 467 48782161 64494 24 30988868 7 69 7682157 62037593 137415151 3644 206101 6 676249 3 745081 5 84313239 820 441 75140 9 48268886 37 9224608 7536336 61 8912432 939 3449198 91233 732690633 38928 45 144603653 3 12677079 45784976 790035 20 32164201 9 3449773 5269208 63974295 105613145 405763 91 6 22717365 39 42449658 80731 56 84 4929 234836 453637253 2525 5923695 84439804 741273 6261104 727 521142 35806 1888884 347 88754098 74 4888220 805 9105 6712 860471 72324788 3156 5067793 7254 81518 92997725 4 240 89 6752843 57597 523117480 6429702 75 773554 409421787 61 1589439 4391134 61095 5190 4677542 444722 83613 899568182 47703 34411405 593262 7262 436675 3 850 2072 37719451 22 2 3061 85714705 7069 74810297 362 8028 84034596 445192046 2616292 7 2 2921667 56 7333002 15292 784 14563 24728158 79918 60415 7637 94692 877 438706857 4086081 14653 8 6 868989590 5243275 2242892 6 8 117 9646 44751 6290610 514150 72706837 93358 183 299302 99860536 81011 44375042 88 7818931 94 836 587 5 4186 3510 50942074 927319534 4791181 2546324 8284161 771922 1531 2229 93759172 47103 222 790041704 3715 2 956472207 71 963778049 185357534 3210230 903 4542 95361 15 11141 627643 512162 4549509 94438022 23386 8707 886 83 1 14 2274 4833 585 9379863 8097 541020 91 74 5893 479843 9402 6901188 58981687 67 42261 9 54 780151252 800863 48540547 91072 651636482 485857 569913963 26 478 753 62827 5403 829 29490 59651 64464 92 3627 637621 174576 65025045 98803088 475969 5 1583 66771514 68 59209 86409452 19986 561436 754112418 85855382 2809 27741 635273339 142000471 67 826794509 39077 1660462 3214297 13516 558257 20573 14 23 966722223 39 99973202 896460 1105 300946439 3564 42735 515 7083 82491 99366 81 60 3 15 5241206 57281 554014204 688977 7 919557 61 86294792 7110435 77076695 19934 4 4 817 283534 262304
1000
6408503 68 9662249 44940 3258 1731505 30 95309782 729 3897 386756 69502380 926 660551045 58886983 324551294 86396210 9 9096 78605 6869902 8009132 618122 247 3347818 604377 2661 56568 859 26391343 710 346358 85384 366617805 4826 72741 34492 8 99943718 3942 6404 86116040 280265207 110938795 54693619 1 338193039 620548 632 159614387 4381 91122243 212404 4628 8 7611336 65385 71385237 56 62039988 665402392 8679597 34097214 17249385 371938 98390 793745395 803 71 5482 4 235831216 6236057 976 796019 604 575496 68434 4567456 1060 24038 54409 1075 663154 65860 7 8 770 8 6152041 4985892 766450457 95458 692 19140 95397 4536773 6 8 741701698 1611 363 42 78 92 46718064 3 2 48 207503830 46 25770140 7310 404 2955 895513 6812572 8455 320996 3 2488884 2 610 283 654389 61 54450802 9 95 31460 2217 9287638 392 2273558 469528013 2770093 44 74 19342726 948479 98 121616482 928654621 8190 2454 5368 49 347962 96046 3036547 229 20 7339423 1868477 7464 346 1 92510 9 52264 2886790 287303241 1 29 94 1 13 293 186806267 6 1 17235107 429088062 24372520 706857 1176 53176 5816417 5 655 6 267 4 26932149 90370 8 150313627 822 4149366 339639841 2 8391 566067716 6679 673076 7346 521 96510 31577257 425263 4740 100744057 404 47638687 384600 510741287 941 35822428 626 745803 8584958 994 44 93105028 79195918 5527 56897071 47515636 50 459007655 8 4 211715 607455 617997931 2949597 798 5705 6313270 77192 5257989 79 75 6254 587194597 928148 492769818 7981023 685046971 748 7750 3 24489 670994 53129 1065754 5 510529 14021 4 9877 6 24739387 4313489 41509574 908 71771 162694237 6946794 7 923795719 31634827 90 18 4663 55 81543 419 95765 8556368 470 737294 5434 618 835592253 975990 25 669993 567704 67 9 65640656 8 8067 206 92211806 63575217 384260170 988895988 81877 6792722 3682 188833 2483894 53 523867228 67279122 8 608387538 761258 80 24965242 77867410 65662780 23720 4343 33146666 8219252 74458893 71793 35869098 99517298 8270107 84410227 7963 28914711 615 8157028 25027430 4093 778 49 932 3684124 7558692 8563 2902 53181 67983423 58627106 715707030 7 7331607 2502685 615 702788 808510 3 404 191778154 3 92963 2597 21 524934844 39631 8043 75960644 1037 78 203 59 5333857 182161 9 84783 135152 35 24638 42 20 75800827 28 4868 70701 79 341 124740 83888862 1 2695 341158394 830312357 241936749 357 917293670 4294 365988 5066428 554 8832 4124508 8 7716038 395772181 334101 871358210 95755 7 231 8 445251787 459314 2 3552120 84230 51 46062 68088 94 1062 5148 21104039 7683 218415 888 69190 63366 12121 75408435 85 952201 4 4255374 681 640 81106 882833 4965391 560 1187 674321439 308513960 5 899148729 137047 9647831 6122945 305413 944 84 6720 718872 29 7586552 9429028 158 92940 837548 2983 111284 3 2620794 604 6 30 97589009 7100715 1 15 275652 98 97562 2862183 435 5148 795914 951 41 332230 5 730926115 539504041 3140 466 320659199 2067730 8737663 60107005 149841 1516 3144 7 181498 7886 4137 819540375 396155 63 33955 631 447509 538147 1 954331 57 795 779514843 831 77496 561136 920707 15297 606446882 9 16 18953590 745866 101 3 414 4250575 494260 97 167 728 270776091 6251803 141462 224 93073309 87897524 747629055 10375773 3 4 933524 8 1 56 9 99646 911754 496892889 228 2167451 6126 3 88882 3315470 629 22771519 14208 442247 19 91407 24798 11542 70 44 67 4321549 8225 298 5235200 17 87122907 4583 52555926 22743 941 17976226 1488 588 204 23 9 102050765 37974 111516212 6 7 56 6 30 557070327 678462591 512348 53357 831135633 1 8306 79038 2141596 7829 6 328906 6 42 53985 853697 2417220 4032 6024139 88341 7420 126358520 2953 95817094 2068472 97 1 3738518 4838913 349 4907 7798 24512 418 8113 686 53 2616561 63 115464 23500067 5989843 81149 697 74121353 22679 61224508 53845 8849642 53 6133 5 545 1566541 5 20 92176348 714425569 842307692 828638 70 764 750492155 487983 854 1007567 439390496 964 936557651 455 65110973 287 959 99 88 517 9 819970 6 7515346 2 57728 3 858536 5334495 4323 5 4591628 7 6 8365 40 904 98572 518827 2 90509 7780 86370408 9 193528233 5149 3339 95 77 28 8040 39774 906554 639 9 143027896 6 4797626 35 85 81186 38 356 832 769161167 8 545726728 7736 94201 7 381 43 208287089 398 364392 88006 431512 86 979 8988 13 760441 75878 88604 587 741 4339763 39303 683794737 448 482 901190480 69 233 13197 914 7 2 54171 109706 108433043 30239463 63791768 4 1910 439593 39785602 835 27841 7 5 42 79316859 692354434 323462 6 423502 32646075 50 703552 48410 1456 492 977256529 9818 5650 9426 74 1388646 96 45000 6813142 1070 91991762 9203 945011883 85029 50325017 8 890649017 172738 79591306 57534 6 143807 79301 7276351 511 235165 3779 77538858 617 2364733 63 78128 9757051 91600 944092 8 3791235 627175 2465 812141 4178154 55057074 8222 88 8121 5 2 437959169 8 660 908 59900409 22176 78 657136 235870385 41811660 2742 21768739 93 473291 7265 67 9976 683854 57223 153383 51960 246981032 17 15 41116 54 431 6339 8189 645503 8 63 95957893 392666847 211 1472 13 66223673 603027 991448693 320 4 9 469 765894661 809381918 8287021 50913 455346265 43131 798694 5515 516088 41 355827 4 8963 2191822 7573 94041 6 3503 864035085 528 81363 7181520 491603228 6 3993945 9383131 47033186 98580098 2040224 2 7540002 923 46153 17932154 60373851 77665 55 4510832 8078415 83 83371233 458599404 2255 19562228 7 501342366 8231084 21792344 62 208248 36167 108468 582 292426 5 601 34063 973926 17619307 513 7253 1356125 41379093 1 48757 39407 56 653130 722630 8982 53012145 552612317 203940 8422091 10244 715 4901 323517782 745659932 2300592 76 3017 1850 4353 209417 2165485 642495 5048132 821822 44058 656 34633592 5 76 726 72250848 105642506 29 5307553 4229067 331043 3 9772 652 9455 52899 5 149852467 32 8050808 987013 65 397798 456 86151 4223 47474 87589528 6 5943 80085926 167 263 569728 9 727968 963303 6480773 710088 75908 353866938 7 436 94 99408 54829764 835 5942853 6258969 8776 728027 736578 9949095 167 58886832 731 68517900 2511 34 25037 30902919 207 63 69 246070746 4 36 30559 2 4 28079 163667077 8938764 655466 244453131