1000 456943203
998545246 998416909 997845671 996968500 996893980 994923345 990846361 990690188 990475550 990032989 990028868 989926065 989699985 988930478 986776751 985658750 984838231 983840444 982572130 981602863 981567343 979934682 979776105 978419644 976628464 975623227 975408149 974005895 972581990 972454070 972274185 969760349 966808558 966294512 966233858 966051781 964611541 963830400 963280282 961182517 958150175 957753855 957416546 957030429 956262873 953989475 953485664 951313394 949415579 948775077 947322411 944549932 942661202 942377472 941444748 940973376 940950837 940104387 940049074 938407463 937395453 935225553 934974350 934704667 934075546 932459689 932363148 932306068 932301166 931219913 930368396 930026584 929736088 928701998 926509505 925782223 924589930 923773526 921145764 919964520 919818256 919366237 916874290 916864923 916279554 915737658 915582591 914747835 914163543 914150387 913332742 913062026 913003862 908200766 908187195 907814684 906696255 904972087 904723398 903419516 901314503 900504014 898755268 898376166 897002392 895632588 894909327 894708488 893309152 891133078 890763092 890695947 890469466 890366836 889639610 889507330 888698560 887658037 887589521 887222135 885509989 883385644 882857813 880383112 878390264 877967086 876517639 875873071 874501750 873902736 873680121 873040443 869703818 868782188 867978860 867412659 866422728 865423984 865284306 864966916 863668176 863601318 863347346 863234258 862452764 861785305 861715793 861688140 860296809 857282286 855149788 854797187 854585431 854577509 847397403 846726640 846033528 845759707 845667473 845511850 845494532 844799516 844517617 843931522 842687004 842174209 841654344 840709505 840408197 839809535 839776200 838585466 838215368 837771086 836115670 835454695 835453823 834843777 834277533 834068801 832942507 832033980 831273760 830562982 830533141 829637453 826938558 826182316 825089617 824011803 822445256 821852527 820901583 819724466 819556186 819532488 818357251 817546067 816503015 816496406 816456668 816215626 815069528 814753558 814261236 809426145 808701397 807549851 807206977 806354319 805741370 804635509 804241772 804232909 803487313 802812818 801112604 800040737 799997938 798016015 797987996 797932159 796607848 788893036 788555089 788052636 787879758 787596731 786914280 786703847 786636619 785343183 785266267 784978461 783194397 783024086 780376544 778758275 777638919 777635736 776403329 771166649 770793637 770735349 768688727 768597940 767559930 767067858 764854694 763672900 762847899 762835119 762794663 761115952 761037779 758350127 756559760 755923606 755407558 754553663 754327250 753247317 752204703 749542779 748764771 748593136 748574450 746082479 745740775 745722898 745184128 744669297 744456916 744163784 743961358 742134626 741129853 740958910 739428055 737857729 737592144 737532491 736112316 734211757 734149955 731666294 730777479 729945215 729537022 729468485 728121951 727816240 726677143 726186696 724578058 724449803 722316899 721821372 719317424 718980549 718798372 716866162 715073397 714072959 713741170 709416000 708543036 708175487 707441732 706417536 705482252 705226153 704629204 703819322 703323954 703278924 702957058 702822044 702283986 700786025 697798686 697295700 696141084 691905306 691807551 690561150 689474862 689075407 687273067 686083851 686019753 685544933 683819721 683587076 682632661 682137233 681397758 680583343 679798203 679308793 676037098 675798772 673605565 673344472 672303197 672068635 671846728 669282860 669079927 667542618 667080558 666998381 664136817 663596789 663380057 660957151 657443075 656606391 656567378 656391150 656358935 655502277 655056373 651397719 650531955 649985642 648979009 648603643 648360090 647908803 647827388 647318476 647197908 647059513 645977788 644617970 644166087 643789039 643004436 642584451 641695942 640179435 640176070 639859042 639589918 638145361 637607995 637045281 636378569 635874107 635427485 634047435 633860876 633456187 633310856 632087927 631063385 628178170 627953067 626855518 625744091 625560038 625083865 622214227 622078983 621401773 621086243 619906066 616191631 615601061 615313183 614475050 613469415 612544704 612015550 610415832 609683578 609343392 608850397 606015826 604980991 604114233 603163471 603016479 602459064 599766439 597506807 593477934 589739657 587407497 586950762 585638453 585226100 583971895 583451682 580889873 580760645 580656200 580316146 580225284 579961462 579332145 578158791 577732674 576105404 575980099 575083435 574310238 570637342 569575546 568983461 568959965 568955785 568211886 566059307 561427967 561345016 559090810 558648741 557335294 555425907 554062967 553127334 552199406 549887473 548924977 547161047 546830591 542730590 539808503 537335160 534877175 534697304 534562184 533652962 532631558 532567973 532209709 531282036 531197312 530524688 530053282 528563868 526547102 524486676 523580326 521560023 520188002 519870990 519827588 515827668 514412513 514302907 511322654 509592247 506558980 505297304 504897756 504147632 502943836 502922343 499684191 498525336 498226066 497547558 495504827 495430454 494406662 493728472 492249751 491543994 490590225 487850873 486272518 486091552 485725695 484661334 483549404 483276228 483222277 483095665 481728901 481194021 479073111 478125780 474855610 474281625 472732259 471132954 470489355 466578319 465441448 465232583 463886556 463159853 456536034 456235175 455349313 455087865 454223310 453008195 450725223 450292119 450096301 449477244 447503343 446872504 445869254 445683729 444732890 443709022 441825374 441720232 440761639 439071152 438523897 434075721 432926263 432619403 431775578 431773974 430994937 429643517 429526483 429297080 428266919 428080540 427815115 427759528 424418854 424126136 422441442 419805064 419356331 418033453 415293109 411334033 410001380 409964180 408591557 407252724 407230371 406797223 406472838 405906320 405425544 403951609 402744167 402617896 401473611 398295288 398095885 397403491 397305737 395564501 394735337 394353979 393675506 393190246 388315601 387911245 387731809 387561202 386992083 386978449 386453563 384842059 384650776 381617489 377280228 376620363 376402911 375783921 375521141 375049583 371707796 371698787 371670534 367363896 367273105 366092371 364765544 364400280 363612717 362079955 361515950 361469352 360757500 360444231 359657493 359515195 358440999 357782720 357536712 355999181 355675174 354130961 353499612 352900959 352427054 351069234 350145021 349262209 349134024 347026901 345630885 345246071 344859091 342201542 341927306 339721159 337753549 337540865 335818080 335681454 335152351 333097646 332390779 332182648 332121036 329507738 329443399 328560928 328288361 327277665 327048948 326487843 323325036 320981293 320174720 319387454 318748461 318066877 317973335 317058923 314048660 308232013 307661893 307413971 306959619 305848855 304599063 304455352 304220588 304093693 303883493 303868519 302725422 302718619 302154608 300513169 300298662 300166689 299678547 298333308 295265979 294113508 290871453 290288471 285621930 285200693 285167102 284434183 284043072 284018683 283166964 282937356 282694647 282467182 281470954 280854527 278188365 278017392 277414585 277097140 277005262 274895464 274199224 273820995 272839106 270328024 269437923 269316275 268952429 265902760 265437375 265306401 264867547 263363996 262925326 262824376 260575773 258353782 258120365 257703796 256541642 256052934 253091053 251598913 251519951 251230073 250572093 249391083 247909952 246174678 239930082 238032260 236351185 236258096 235053381 231804338 231800358 231765760 231172437 227948287 227301480 226739835 223766057 223665224 220999428 220173716 219998150 218435621 217556432 217417905 214324846 214323925 214172184 213600890 212993387 211595684 211211055 209648570 209080815 207868407 207609810 205659474 203387769 201583679 201334583 200469812 200105919 199856868 199129962 198407179 197639193 196940278 196578030 195343886 192987667 192020903 190548059 190529752 189465125 187832161 186238054 186068759 184646861 183768129 181745418 180285491 179849786 177940652 175979647 173586811 172795728 172662495 171537003 169986594 167462357 166803291 166741284 166447595 166014089 165080227 164883842 164448159 163931345 160687670 160134493 158713466 158142821 156062156 155144377 154976804 154849703 154114991 153398132 152963823 152869065 151409301 151350052 151301409 150824178 148921152 148080823 146794979 146345212 145571588 145552141 145525099 145322521 144201713 143817061 143563594 142625687 141303348 141187785 140933625 140828968 139925031 139869615 138834808 138069243 137300563 136818400 135657018 134798864 133639249 133027842 132686249 131726121 130453787 130325116 128656407 128349629 123473803 123080981 122315690 117494459 117359127 116794002 116520752 115693331 114823802 114249269 112638508 111973959 110063760 110057221 106160311 105873428 101772868 101752483 101332171 100576675 99727849 97218287 97132594 96426928 95919567 95895615 95772124 95671046 93723751 92049610 90862326 90278214 90014778 87979744 85031355 83994185 82369951 82047711 81518066 81156658 80737273 79713267 79705933 79287754 78147871 77342660 73868022 73179470 72119009 70242988 69211524 68076429 67731861 66873203 66660134 66413673 64755266 64312512 63607649 62289280 61783328 59059885 58970683 58838620 58010012 57751031 57325228 55726958 55273766 54961935 54891952 54870684 54398851 54242290 53684800 53446407 53277704 49670600 47904189 45467837 45457430 43226147 42865402 42859271 42637943 42197363 41349258 40809219 39513819 38125555 37174293 36291490 36235529 35965230 34501484 33580586 33368124 33041166 32435240 32332545 31556725 30850601 29559967 28478040 28366591 27582992 26943631 26860422 26324265 24863367 22279787 22034592 18741149 18335902 17098835 16119465 15683332 14838641 14717263 13833771 13642440 11142575 11069902 10263166 8101767 7153620 6602952 5427637 5279394 4767915 4043623 3962282 1897769 1387589