1000 24
32589 1017479 2330669 3920562 4943844 5498241 6429837 7117537 8088390 9720195 10243826 11286361 12897528 13905503 14463810 15832079 16956863 17009900 18663330 19432632 20044449 21022910 22459446 23749065 24258785 25481323 26845348 27365175 28868166 29957831 30548113 31341622 32209428 33041319 34706017 35442557 36282896 37940833 38717754 39755391 40487487 41178761 42690433 43113906 44764582 45588020 46870618 47005068 48333323 49767992 50674347 51861120 52768945 53253418 54503448 55261380 56999967 57257437 58709959 59805964 60444505 61160169 62510877 63309903 64465956 65448288 66763710 67939137 68468741 69687449 70193233 71797462 72943873 73010792 74527544 75989380 76367901 77280163 78953946 79469185 80953759 81902302 82542236 83620032 84360970 85924527 86020259 87259127 88479141 89785449 90524883 91035867 92843380 93443172 94148306 95068705 96581628 97191858 98172485 99023613 100477378 101625962 102492240 103758758 104753420 105005921 106874713 107526159 108232669 109869803 110480772 111870575 112212348 113784413 114320951 115191609 116378541 117440588 118325975 119421219 120123253 121404110 122991560 123700962 124909849 125891384 126547248 127813227 128179934 129610781 130215732 131309363 132899593 133062421 134480056 135449263 136056032 137470130 138564514 139239315 140334950 141662987 142152599 143306198 144248930 145720308 146974139 147869419 148215768 149140355 150154868 151164361 152457485 153034124 154942566 155447395 156751046 157712549 158474679 159222383 160687816 161174882 162176844 163442466 164162265 165884760 166792649 167867633 168344124 169938781 170298388 171291280 172134456 173064005 174318354 175905782 176908561 177728997 178006695 179102998 180365132 181395347 182241209 183716647 184007022 185465123 186079341 187241052 188277437 189278123 190795943 191262059 192146876 193091903 194724557 195036297 196274226 197980852 198295364 199176363 200528226 201070496 202327024 203393798 204672723 205960791 206646775 207249935 208814729 209600047 210283965 211636731 212384585 213126268 214253736 215691390 216747993 217585043 218587037 219408271 220079804 221541642 222597824 223676705 224049529 225798901 226625911 227638698 228662419 229173097 230656871 231374111 232199121 233433340 234966580 235512693 236409463 237724867 238904836 239984737 240394314 241188689 242154812 243567576 244282960 245639101 246541312 247283855 248656396 249314524 250814582 251980474 252003141 253358210 254680130 255014096 256888190 257765700 258647883 259477636 260433918 261382200 262545907 263754444 264718153 265202290 266852962 267875997 268320740 269145863 270343227 271174380 272074260 273382797 274124196 275894254 276905247 277403736 278772737 279459928 280642760 281959614 282947064 283054623 284703702 285517459 286875373 287953143 288606221 289167276 290975623 291551831 292048434 293430559 294827817 295832434 296126922 297429120 298236856 299097086 300448154 301660837 302663386 303530544 304478056 305972002 306672052 307426621 308907703 309595084 310747755 311414874 312396174 313891833 314653219 315793212 316510129 317972861 318270402 319008856 320827108 321440685 322925228 323638434 324449263 325722463 326654919 327672209 328532564 329837864 330918008 331207384 332767705 333092187 334566819 335117421 336548996 337458895 338336110 339614278 340684504 341232153 342651453 343762070 344761628 345031885 346863863 347744082 348078676 349030400 350697727 351925681 352330309 353022983 354198266 355703335 356096052 357080312 358343374 359051049 360747303 361898408 362114336 363369387 364255521 365360619 366918869 367581091 368681257 369116758 370498001 371168839 372310019 373202815 374283641 375147594 376780659 377685753 378665844 379520546 380254337 381028892 382858853 383669508 384772079 385318459 386045297 387392677 388612355 389875627 390078271 391967545 392361859 393367617 394043633 395778359 396436786 397255763 398388207 399502163 400531095 401898998 402826460 403187265 404211126 405198461 406829406 407184823 408945748 409774143 410793370 411834282 412627894 413987281 414586356 415533903 416095713 417985735 418684241 419836187 420425051 421512758 422143064 423100611 424450599 425264436 426538540 427400188 428738444 429796565 430774643 431494011 432427086 433078894 434055761 435733748 436363890 437852693 438154092 439905182 440716605 441119454 442111785 443749484 444142580 445629663 446516140 447001108 448793693 449043756 450914843 451679947 452477436 453846810 454722778 455965254 456309397 457280191 458234959 459946554 460718383 461157999 462230495 463719068 464509198 465995200 466534831 467519968 468777143 469758598 470828067 471471165 472134768 473093206 474773408 475363110 476323644 477811206 478415245 479750098 480325666 481413226 482922253 483988212 484778341 485765720 486166405 487789570 488627276 489950308 490383516 491063537 492836379 493809891 494490037 495241590 496237015 497634155 498383221 499028166 500074374 501935120 502651203 503045269 504143531 505583335 506512513 507354010 508630732 509518150 510116247 511361352 512765999 513301825 514407912 515923414 516402136 517091886 518142682 519670455 520732812 521998817 522784017 523782561 524101200 525607407 526934963 527740425 528972009 529301742 530433509 531551908 532035101 533270194 534390411 535757223 536202607 537961361 538612491 539753670 540621862 541056479 542222282 543997432 544025222 545695793 546204396 547131696 548775700 549229597 550836631 551704933 552667669 553411959 554654320 555815306 556521678 557922069 558201243 559279765 560403140 561885899 562838014 563639035 564766397 565520686 566780029 567638449 568935485 569082452 570840382 571273708 572142024 573732177 574016806 575206112 576726821 577384763 578045977 579160900 580391513 581517669 582630013 583440779 584022567 585012135 586761463 587160428 588524757 589609043 590055851 591505754 592408233 593659840 594945663 595288203 596727974 597189187 598554264 599335092 600219923 601801776 602864858 603880010 604396596 605015132 606332331 607699074 608650318 609838557 610666864 611624337 612709222 613843975 614093261 615622443 616675202 617556207 618290536 619013191 620635621 621589035 622233061 623515352 624414166 625158991 626392426 627760212 628477784 629516209 630480156 631460465 632613938 633974501 634420191 635866146 636165096 637694912 638804825 639991325 640451904 641814040 642317679 643717270 644319613 645547329 646640773 647830468 648118117 649128657 650008513 651536091 652412222 653135259 654499912 655405519 656593612 657140151 658527230 659086487 660926356 661455159 662775561 663177062 664060763 665521267 666338957 667779954 668620134 669208637 670234032 671245424 672042170 673199148 674183575 675053077 676649565 677548372 678875814 679063510 680974738 681355339 682649731 683244136 684732384 685168421 686975955 687855103 688242379 689491255 690920506 691978642 692566168 693795671 694723870 695131028 696085644 697297241 698355364 699718396 700155884 701895059 702354288 703656573 704979070 705012825 706547944 707663181 708675141 709153153 710180017 711615201 712057352 713837086 714948399 715267118 716670411 717027271 718075656 719444712 720049555 721583889 722503072 723500934 724438757 725458448 726993821 727321020 728180999 729608473 730556260 731327550 732715644 733543810 734383385 735707074 736656779 737880927 738628642 739193662 740888759 741700422 742189412 743516901 744989447 745265291 746253443 747349421 748653247 749632515 750500517 751787723 752860132 753207620 754460079 755684787 756102139 757847778 758385221 759909532 760806538 761408370 762872461 763704441 764922900 765657482 766539243 767141377 768182368 769789630 770709061 771290663 772848434 773143652 774638144 775414753 776681551 777142480 778684417 779940581 780271612 781773784 782919212 783013798 784199294 785381455 786460198 787823705 788884891 789753293 790115862 791059061 792421910 793519332 794489119 795880430 796139062 797025707 798687142 799441721 800982783 801110455 802490706 803051146 804497462 805854363 806842502 807340183 808658848 809643695 810492007 811719446 812919682 813888133 814647963 815219962 816108641 817411380 818336007 819367289 820345027 821128464 822952848 823899336 824134252 825280175 826558490 827665499 828987616 829470885 830913930 831836137 832648742 833764168 834256967 835604838 836361026 837654956 838471092 839521222 840479354 841886118 842443191 843881280 844638993 845896268 846806324 847568711 848564238 849087090 850272593 851092625 852007732 853697389 854597618 855429011 856337738 857578771 858462334 859058306 860829908 861462840 862535704 863872467 864508887 865991154 866225701 867532346 868800536 869433365 870356555 871505710 872504413 873528374 874272239 875424802 876405673 877005867 878325109 879607821 880443843 881812808 882102531 883482082 884398254 885413475 886817214 887876119 888106673 889335824 890352971 891704993 892773136 893340324 894352334 895262325 896153937 897228533 898131180 899996104 900988599 901528343 902134795 903423311 904259272 905073056 906262544 907512446 908228490 909170404 910323936 911532556 912920129 913542008 914912607 915148972 916877938 917713842 918927795 919821269 920868002 921340966 922481024 923218874 924211414 925409385 926483309 927455249 928043603 929397009 930707676 931125903 932835807 933827826 934638389 935920233 936367421 937277026 938664731 939823123 940567156 941277813 942086196 943407172 944354440 945580737 946018980 947870448 948037502 949388057 950565265 951361419 952146907 953064021 954646303 955696907 956735460 957107079 958212085 959777573 960186655 961286150 962238518 963985935 964383695 965703335 966503239 967093372 968673851 969610110 970631182 971355489 972430503 973117728 974829744 975361333 976337560 977267746 978254226 979546924 980336659 981324122 982463960 983208186 984403101 985261853 986033895 987752470 988706684 989804926 990338406 991129651 992559219 993718420 994458040 995287815 996960905 997010036 998111106 999556103 
87855 24803 45705 83224 35560 97013 58007 91793 25579 15207 79505 93362 53961 10334 34865 21815 16854 67947 10747 88406 65147 53921 91521 58311 33177 86984 80520 23591 93587 68473 55325 24425 99422 61887 18178 45278 27103 72849 62322 57837 31058 95483 12835 56086 97331 57046 81495 25018 92258 90042 58247 44433 55864 31767 11801 11670 29910 87474 97499 26911 54263 13538 91097 96546 51099 74449 42159 89751 92358 48532 62950 51228 93083 98135 66943 88409 18449 62784 45151 85048 67544 76618 74628 26927 91020 33883 80352 45686 73172 84234 40720 52181 51717 95034 10741 93053 26269 37940 75163 44954 93635 81211 55926 69228 95871 17967 54669 37803 64092 90443 96120 90005 86519 28227 31458 85274 76550 65931 12346 43153 49737 79731 32178 61342 60170 86496 17310 60775 53828 51214 34719 31555 43671 89739 43029 35897 87483 18733 73542 10886 99764 25471 29160 67364 93190 18622 75197 29069 11777 73785 60850 45154 64897 80266 86623 43989 37680 39962 49605 29744 91835 89722 91115 87445 99241 11048 77527 35945 44692 46306 27038 84063 17986 53532 42218 72258 75828 12394 18683 90254 64336 71411 68915 41286 68407 88309 58602 87386 56771 97915 16851 16575 65580 58265 39108 96057 79474 72513 95663 28755 18752 35066 33961 75232 14050 60711 19415 82788 35672 26701 46892 15443 45051 80631 54484 26257 48538 55480 72665 17291 61450 12174 37851 10867 80356 60811 16218 95279 13266 63832 69007 30944 13456 34938 57574 60798 64733 19904 52533 66641 29086 61457 60107 99559 72821 80088 60409 43702 72066 14462 26542 71392 15524 33941 43100 91578 80168 10465 29975 88761 38678 20880 83591 67431 49845 67746 93912 24610 43839 89116 96533 15969 63057 26575 33091 28791 18258 77999 44207 34289 97049 58364 39033 31627 40445 46107 40128 68305 20520 32464 70662 79067 18020 61229 48642 10156 69370 24686 60502 26911 72821 61877 44480 94623 84785 83892 48684 92950 16866 53006 62337 39100 70687 45612 19364 94616 12574 87104 21775 47664 94151 43109 55808 69209 21259 21399 25727 20414 71159 93976 98055 24529 44203 91083 91125 84540 60631 28855 46324 16741 42867 32682 61902 55398 10826 39102 31659 15274 55920 34713 17481 32667 75922 75080 65700 51338 63688 84498 92578 95467 78364 63400 27714 36638 96043 97505 96763 73621 81835 98613 54812 86784 24105 82475 36380 97243 44668 44497 34073 47455 57895 22477 52852 31626 44106 52343 91259 66535 89312 40862 70975 12141 32879 36923 83383 20066 30864 81695 43375 99755 73689 37766 39968 79268 96085 66562 63502 34019 10057 95115 25194 95863 14435 18178 67327 72018 87389 53953 24911 82489 97262 78712 19930 89826 50412 38924 50882 62076 38210 22295 28493 97861 75948 28786 58251 85287 85793 39535 65906 73203 36750 78960 45319 87115 52743 68550 56939 18114 16596 66857 62047 50280 89414 48172 85267 23012 67747 53793 24547 89284 13795 69008 50704 96052 49863 11797 81228 88052 35540 70037 67283 16088 47482 53818 43662 13364 57036 42436 20276 41432 84251 61393 59767 62918 20634 80865 55995 68744 53358 24211 91049 25751 26952 23667 43697 69236 91785 58636 12378 46947 23598 13304 25150 72704 57544 36207 87540 22297 83677 79761 13798 71779 68411 45777 38571 95951 20680 62241 86879 66191 57857 10517 63228 21721 33183 95763 38830 48081 64660 51558 60503 14551 26742 31171 39591 46899 76479 86468 53410 59249 71563 24904 66304 73651 90531 82906 90239 92600 18033 22426 72453 10062 42497 59446 63077 96366 77991 54361 27025 81972 98247 21328 22917 72377 66011 58017 14085 15716 27023 87495 32417 91905 76418 44810 26594 93876 75899 58864 28248 93946 82026 54528 74926 64207 92769 70052 21095 23957 75172 52357 47941 73060 95925 44254 28836 84699 82857 15251 91898 36206 74254 17928 45695 19862 15867 98324 98361 91840 72575 14638 39492 37465 69856 25277 35651 73544 55460 89068 37366 33245 12996 97968 84197 32214 62127 22584 58769 48779 92571 82789 37576 32428 77927 33219 94388 44850 46688 88136 75727 32035 63083 94819 24891 21470 32138 22035 38109 27669 21809 92581 99619 62341 53987 41319 52685 76910 39164 60284 15554 68680 88534 67575 27154 62071 83546 13706 60701 11785 12471 68840 33866 48739 54409 67836 94945 76631 71610 80676 84079 73635 48180 74757 89423 10203 90669 71267 42631 79724 97004 42802 18633 49108 39855 81432 21342 76216 73634 87821 51940 16428 91904 73116 15631 40908 59290 89777 82292 47227 78237 18556 82150 64856 10488 85521 65790 95360 45776 70705 74533 54080 16260 87711 93613 96681 24170 72790 57244 45106 87947 21434 40311 29022 14113 87910 11307 96445 65359 78857 29338 89443 66674 97735 80476 33917 55095 83718 46665 56567 21406 47850 95493 79576 79670 26419 32698 23550 32304 50504 40892 12376 48582 51695 89938 68737 80554 42491 50333 81538 28120 95418 68937 55864 44545 70671 26162 84880 66222 56292 11918 51927 87530 95810 90688 39008 81452 47145 98731 91868 33367 25346 20442 55070 94237 18316 38762 35171 93748 18913 68317 48767 99238 57674 66051 47997 29698 97924 92686 29897 34693 98906 45027 67844 52416 40244 64453 25581 96684 52137 83916 18037 14992 16586 98534 23217 81473 96101 68566 43243 41967 36447 94696 74535 26557 97251 57782 63103 31674 63027 98636 43676 22176 26362 52026 17965 50930 66818 81549 36557 56406 60470 71094 31444 85664 98613 82896 47898 55794 23265 87937 73610 51773 84591 65078 30782 95372 85544 35054 82478 30442 55894 76004 20065 24605 92414 94482 62947 84952 88637 36514 39623 24838 72697 32470 97221 69176 71985 57007 37013 89724 15686 96102 31617 54205 37937 68690 81357 75434 64178 29224 19130 16829 90489 42735 71430 11092 95704 97784 47710 82326 51575 89858 10325 11523 86175 81100 51345 76568 81933 90739 28451 45572 16043 26111 86223 86464 30662 74546 46715 47571 36259 33768 28606 30589 79920 32738 39495 65017 58055 17337 13335 28129 80870 76329 69332 70268 27424 98550 66608 82060 76886 87569 28416 26075 33192 87406 16812 35324 84592 48464 66240 40681 12558 85791 21362 21479 54313 42686 63648 70601 58968 80660 50278 22545 95376 96011 58369 60826 19765 18510 11755 10942 92082 67995 47775 70989 97261 11127 91285 16935 41991 16691 33782 75166 53417 86216 71246 62021 19330 11377 10716