150000 300 1 111173 894261552 66 69046 151308237 154 31011 449181620 162 7273 648224176 198 5757 117749397 231 53594 227264254 234 42860 49650801 291 139676 313416635 359 133678 673844233 425 65145 397817824 471 57655 131995361 570 19967 823358405 662 112955 845952901 695 72236 750627591 768 98177 120162332 845 142689 518089155 923 94364 449639365 961 44660 731708198 976 80493 875696469 984 47021 186245034 998 96253 962832727 1055 138372 128435130 1153 142761 468732506 1242 133802 59379878 1263 11678 923600051 1335 142669 390511016 1430 92698 300168562 1528 45264 361733531 1577 50502 157747172 1654 81462 948117305 1730 95095 551878272 1802 20840 687250032 1878 60460 661181874 1889 56764 55713744 1959 22982 888811514 1971 3635 187258816 2003 147485 76787833 2048 69590 265445517 2141 4924 835245428 2174 136810 906564632 2216 33651 320202711 2271 107193 945310922 2277 55786 610622301 2337 18094 635347472 2371 717 390885451 2395 52588 9959143 2467 124311 770650133 2548 141904 640580653 2565 144252 390793293 2613 62609 38187719 2704 61043 622944199 2738 71510 850230598 2808 51951 162046853 2845 39010 664602725 2930 4429 972781168 2985 80132 975524699 3010 128151 737672037 3085 86247 747580049 3135 14608 396122085 3208 77208 431329310 3243 51061 393051514 3259 109698 621931497 3296 46573 756628945 3363 84772 53847061 3408 57128 895565393 3455 119834 407768468 3528 118624 255597610 3563 53444 989829503 3566 59434 576935848 3589 47440 855865622 3630 12683 667603969 3694 137240 788905863 3729 18187 902374347 3739 861 758540132 3834 97585 259040433 3872 83170 962534204 3881 2343 230537515 3901 81222 799648921 3917 181 714696796 3926 9896 2189169 3989 52822 335830246 3995 22517 327813034 4044 91826 972300189 4142 138609 108007692 4198 51160 341732959 4296 13646 735151407 4380 57914 524941109 4445 149354 503566619 4455 24861 940013575 4537 16201 270395836 4614 122029 419966435 4666 93560 679890338 4685 75488 967397277 4770 62572 92171077 4786 81679 148839862 4800 14001 152612545 4831 144486 111210644 4836 82220 32188210 4913 43028 179448062 4983 129798 464734703 5051 114730 477562127 5129 46887 716255864 5139 107457 479349235 5180 140005 72793265 5255 47530 767887389 5332 61002 126428427 5354 149045 454004526 5377 108177 919022726 5383 130493 734670947 5390 125964 731304055 5488 17302 882440812 5567 104017 235831338 5642 37070 306858575 5688 37009 102613048 5718 119049 885807203 5809 139192 934309135 5905 27030 587670834 5951 111585 830348208 6026 74738 665899377 6075 102941 121087551 6144 101842 661490752 6173 63771 7212139 6200 123939 831729378 6250 86051 972595337 6271 28936 100677027 6347 141185 553178301 6418 134196 802357052 6500 13993 806018446 6513 29166 49380035 6543 86350 986143894 6620 116531 278737854 6647 96763 990274010 6690 92714 250054134 6724 75674 919858601 6762 30351 276641776 6783 137616 586866261 6852 32536 307063692 6924 49275 178038902 6938 8285 124829860 7024 109506 504917494 7090 68561 720233371 7110 102182 449326448 7204 100571 950930551 7245 20392 224659781 7326 32018 512863892 7350 12526 813196614 7423 58366 372655580 7487 10478 219483202 7513 7677 841942398 7591 47989 383091281 7612 117834 179005972 7632 140288 187215 7709 65060 853015900 7731 131482 474474600 7748 34121 691333181 7775 4426 765405006 7854 38134 71373408 7937 79252 499032059 7941 96668 515511940 8025 3263 130546658 8045 51517 845213220 8136 116097 564184010 8179 25610 967467237 8181 75776 607321241 8279 51912 325409330 8357 69705 359884220 8360 82541 826670949 8455 21459 920943913 8538 139508 479266665 8593 5638 416507680 8616 4321 910374157 8715 89257 462064511 8766 15477 584127602 8793 110473 467387945 8891 104648 742432520 8982 145560 201331194 8987 50060 183815448 9086 87231 246427304 9140 48111 3577975 9179 54737 989036041 9197 75765 910596300 9250 134435 385259156 9263 43371 923111561 9277 122942 566416601 9281 6366 3720566 9345 61678 162635190 9386 9334 152217108 9447 26660 939333181 9488 82390 859610413 9531 138382 777050398 9618 61261 392197048 9702 11609 597841922 9769 99390 830410385 9786 78481 394348837 9827 43419 176206857 9877 52446 406117177 9908 143135 504332129 9954 129233 69580149 9990 81244 375434007 10007 53035 786703696 10043 126121 603837419 10085 18939 151024106 10172 54928 553558995 10181 142817 889368163 10214 131991 449922844 10239 149878 690680055 10291 16111 772605110 10351 45086 969998865 10396 70746 869940546 10407 57556 316030141 10455 35464 116033665 10532 23452 647653525 10615 113499 963472359 10634 147790 187346166 10699 59454 33203251 10718 94780 73509769 10746 58414 819798409 10777 132734 817798091 10833 77866 4518213 10888 129161 497961462 10910 74340 300902030 11001 77193 201540283 11063 57954 560760944 11121 73229 527839005 11177 38062 707057714 11253 88799 370627380 11307 41298 630191890 11372 76150 252970705 11460 148921 613696016 11556 67808 364540406 11637 57187 168376226 11667 48417 352824222 11679 118206 780373515 11681 19938 764629585 11696 84433 911113302 11782 108992 363381938 11860 77695 985668934 11863 126481 971070099 11911 24908 157423497 11987 73598 854782603 11997 110832 17319515 12036 10318 587680720 12057 1959 544940517 12088 74241 929839085 12108 131950 441856570 12112 40799 989882040 12182 69005 617688744 12271 59798 67709161 12365 64067 919482850 12393 121795 280303697 12428 52241 749215421 12515 133956 320399936 12596 77924 343687972 12671 85372 692834874 12704 14907 477945309 12710 142442 812523613 12804 2647 791602202 12882 52769 476750768 12933 18863 321333288 12966 135098 612558668 12988 14329 384185196 13047 64684 506422065 13066 91528 984380539 13142 26578 154384710 13195 31161 550271396 13249 140960 121454479 13257 107577 839139793 13321 101758 157166277 13322 127013 766099815 13390 22316 848432154 13465 44188 506097336 13555 140485 826107480 13595 69443 688614655 13624 145411 500464015 13633 36226 853302378 13671 138797 745221932 13749 115085 127224744 13816 29089 664251872 13828 50806 685380301 13875 107724 406137714 13968 25637 510142550 14034 113720 444408738 14079 37522 995232679 14161 60706 452124049 14166 135757 822589651 14260 147252 481064382 14350 126310 635986793 14435 125426 663003273 14527 67554 815115063 14601 14290 676470401 14669 132842 284564716 14713 90371 231952850 14753 105098 867551506 14772 78334 762237604 14809 118512 312618255 14867 15515 177108432 14885 9030 380818790 14982 23487 472744935 15008 17249 841837002 15016 25022 812130000 15099