1 2 2 5 3 16 4 41 5 86 6 157 7 260 8 401 9 586 10 821 11 1112 12 1465 13 1886 14 2381 15 2956 16 3617 17 4370 18 5221 19 6176 20 7241 21 8422 22 9725 23 11156 24 12721 25 14426 26 16277 27 18280 28 20441 29 22766 30 25261 31 27932 32 30785 33 33826 34 37061 35 40496 36 44137 37 47990 38 52061 39 56356 40 60881 41 65642 42 70645 43 75896 44 81401 45 87166 46 93197 47 99500 48 106081 49 112946 50 120101 51 127552 52 135305 53 143366 54 151741 55 160436 56 169457 57 178810 58 188501 59 198536 60 208921 61 219662 62 230765 63 242236 64 254081 65 266306 66 278917 67 291920 68 305321 69 319126 70 333341 71 347972 72 363025 73 378506 74 394421 75 410776 76 427577 77 444830 78 462541 79 480716 80 499361 81 518482 82 538085 83 558176 84 578761 85 599846 86 621437 87 643540 88 666161 89 689306 90 712981 91 737192 92 761945 93 787246 94 813101 95 839516 96 866497 97 894050 98 922181 99 950896 100 980201 101 1010102 102 1040605 103 1071716 104 1103441 105 1135786 106 1168757 107 1202360 108 1236601 109 1271486 110 1307021 111 1343212 112 1380065 113 1417586 114 1455781 115 1494656 116 1534217 117 1574470 118 1615421 119 1657076 120 1699441 121 1742522 122 1786325 123 1830856 124 1876121 125 1922126 126 1968877 127 2016380 128 2064641 129 2113666 130 2163461 131 2214032 132 2265385 133 2317526 134 2370461 135 2424196 136 2478737 137 2534090 138 2590261 139 2647256 140 2705081 141 2763742 142 2823245 143 2883596 144 2944801 145 3006866 146 3069797 147 3133600 148 3198281 149 3263846 150 3330301 151 3397652 152 3465905 153 3535066 154 3605141 155 3676136 156 3748057 157 3820910 158 3894701 159 3969436 160 4045121 161 4121762 162 4199365 163 4277936 164 4357481 165 4438006 166 4519517 167 4602020 168 4685521 169 4770026 170 4855541 171 4942072 172 5029625 173 5118206 174 5207821 175 5298476 176 5390177 177 5482930 178 5576741 179 5671616 180 5767561 181 5864582 182 5962685 183 6061876 184 6162161 185 6263546 186 6366037 187 6469640 188 6574361 189 6680206 190 6787181 191 6895292 192 7004545 193 7114946 194 7226501 195 7339216 196 7453097 197 7568150 198 7684381 199 7801796 200 7920401 201 8040202 202 8161205 203 8283416 204 8406841 205 8531486 206 8657357 207 8784460 208 8912801 209 9042386 210 9173221 211 9305312 212 9438665 213 9573286 214 9709181 215 9846356 216 9984817 217 10124570 218 10265621 219 10407976 220 10551641 221 10696622 222 10842925 223 10990556 224 11139521 225 11289826 226 11441477 227 11594480 228 11748841 229 11904566 230 12061661 231 12220132 232 12379985 233 12541226 234 12703861 235 12867896 236 13033337 237 13200190 238 13368461 239 13538156 240 13709281 241 13881842 242 14055845 243 14231296 244 14408201 245 14586566 246 14766397 247 14947700 248 15130481 249 15314746 250 15500501 251 15687752 252 15876505 253 16066766 254 16258541 255 16451836 256 16646657 257 16843010 258 17040901 259 17240336 260 17441321 261 17643862 262 17847965 263 18053636 264 18260881 265 18469706 266 18680117 267 18892120 268 19105721 269 19320926 270 19537741 271 19756172 272 19976225 273 20197906 274 20421221 275 20646176 276 20872777 277 21101030 278 21330941 279 21562516 280 21795761 281 22030682 282 22267285 283 22505576 284 22745561 285 22987246 286 23230637 287 23475740 288 23722561 289 23971106 290 24221381 291 24473392 292 24727145 293 24982646 294 25239901 295 25498916 296 25759697 297 26022250 298 26286581 299 26552696 300 26820601 301 27090302 302 27361805 303 27635116 304 27910241 305 28187186 306 28465957 307 28746560 308 29029001 309 29313286 310 29599421 311 29887412 312 30177265 313 30468986 314 30762581 315 31058056 316 31355417 317 31654670 318 31955821 319 32258876 320 32563841 321 32870722 322 33179525 323 33490256 324 33802921 325 34117526 326 34434077 327 34752580 328 35073041 329 35395466 330 35719861 331 36046232 332 36374585 333 36704926 334 37037261 335 37371596 336 37707937 337 38046290 338 38386661 339 38729056 340 39073481 341 39419942 342 39768445 343 40118996 344 40471601 345 40826266 346 41182997 347 41541800 348 41902681 349 42265646 350 42630701 351 42997852 352 43367105 353 43738466 354 44111941 355 44487536 356 44865257 357 45245110 358 45627101 359 46011236 360 46397521 361 46785962 362 47176565 363 47569336 364 47964281 365 48361406 366 48760717 367 49162220 368 49565921 369 49971826 370 50379941 371 50790272 372 51202825 373 51617606 374 52034621 375 52453876 376 52875377 377 53299130 378 53725141 379 54153416 380 54583961 381 55016782 382 55451885 383 55889276 384 56328961 385 56770946 386 57215237 387 57661840 388 58110761 389 58562006 390 59015581 391 59471492 392 59929745 393 60390346 394 60853301 395 61318616 396 61786297 397 62256350 398 62728781 399 63203596 400 63680801 401 64160402 402 64642405 403 65126816 404 65613641 405 66102886 406 66594557 407 67088660 408 67585201 409 68084186 410 68585621 411 69089512 412 69595865 413 70104686 414 70615981 415 71129756 416 71646017 417 72164770 418 72686021 419 73209776 420 73736041 421 74264822 422 74796125 423 75329956 424 75866321 425 76405226 426 76946677 427 77490680 428 78037241 429 78586366 430 79138061 431 79692332 432 80249185 433 80808626 434 81370661 435 81935296 436 82502537 437 83072390 438 83644861 439 84219956 440 84797681 441 85378042 442 85961045 443 86546696 444 87135001 445 87725966 446 88319597 447 88915900 448 89514881 449 90116546 450 90720901 451 91327952 452 91937705 453 92550166 454 93165341 455 93783236 456 94403857 457 95027210 458 95653301 459 96282136 460 96913721 461 97548062 462 98185165 463 98825036 464 99467681 465 100113106 466 100761317 467 101412320 468 102066121 469 102722726 470 103382141 471 104044372 472 104709425 473 105377306 474 106048021 475 106721576 476 107397977 477 108077230 478 108759341 479 109444316 480 110132161 481 110822882 482 111516485 483 112212976 484 112912361 485 113614646 486 114319837 487 115027940 488 115738961 489 116452906 490 117169781 491 117889592 492 118612345 493 119338046 494 120066701 495 120798316 496 121532897 497 122270450 498 123010981 499 123754496 500 124501001 501 125250502 502 126003005 503 126758516 504 127517041 505 128278586 506 129043157 507 129810760 508 130581401 509 131355086 510 132131821 511 132911612 512 133694465 513 134480386 514 135269381 515 136061456 516 136856617 517 137654870 518 138456221 519 139260676 520 140068241 521 140878922 522 141692725 523 142509656 524 143329721 525 144152926 526 144979277 527 145808780 528 146641441 529 147477266 530 148316261 531 149158432 532 150003785 533 150852326 534 151704061 535 152558996 536 153417137 537 154278490 538 155143061 539 156010856 540 156881881 541 157756142 542 158633645 543 159514396 544 160398401 545 161285666 546 162176197 547 163070000 548 163967081 549 164867446 550 165771101 551 166678052 552 167588305 553 168501866 554 169418741 555 170338936 556 171262457 557 172189310 558 173119501 559 174053036 560 174989921 561 175930162 562 176873765 563 177820736 564 178771081 565 179724806 566 180681917 567 181642420 568 182606321 569 183573626 570 184544341 571 185518472 572 186496025 573 187477006 574 188461421 575 189449276 576 190440577 577 191435330 578 192433541 579 193435216 580 194440361 581 195448982 582 196461085 583 197476676 584 198495761 585 199518346 586 200544437 587 201574040 588 202607161 589 203643806 590 204683981 591 205727692 592 206774945 593 207825746 594 208880101 595 209938016 596 210999497 597 212064550 598 213133181 599 214205396 600 215281201 601 216360602 602 217443605 603 218530216 604 219620441 605 220714286 606 221811757 607 222912860 608 224017601 609 225125986 610 226238021 611 227353712 612 228473065 613 229596086 614 230722781 615 231853156 616 232987217 617 234124970 618 235266421 619 236411576 620 237560441 621 238713022 622 239869325 623 241029356 624 242193121 625 243360626 626 244531877 627 245706880 628 246885641 629 248068166 630 249254461 631 250444532 632 251638385 633 252836026 634 254037461 635 255242696 636 256451737 637 257664590 638 258881261 639 260101756 640 261326081 641 262554242 642 263786245 643 265022096 644 266261801 645 267505366 646 268752797 647 270004100 648 271259281 649 272518346 650 273781301 651 275048152 652 276318905 653 277593566 654 278872141 655 280154636 656 281441057 657 282731410 658 284025701 659 285323936 660 286626121 661 287932262 662 289242365 663 290556436 664 291874481 665 293196506 666 294522517 667 295852520 668 297186521 669 298524526 670 299866541 671 301212572 672 302562625 673 303916706 674 305274821 675 306636976 676 308003177 677 309373430 678 310747741 679 312126116 680 313508561 681 314895082 682 316285685 683 317680376 684 319079161 685 320482046 686 321889037 687 323300140 688 324715361 689 326134706 690 327558181 691 328985792 692 330417545 693 331853446 694 333293501 695 334737716 696 336186097 697 337638650 698 339095381 699 340556296 700 342021401 701 343490702 702 344964205 703 346441916 704 347923841 705 349409986 706 350900357 707 352394960 708 353893801 709 355396886 710 356904221 711 358415812 712 359931665 713 361451786 714 362976181 715 364504856 716 366037817 717 367575070 718 369116621 719 370662476 720 372212641 721 373767122 722 375325925 723 376889056 724 378456521 725 380028326 726 381604477 727 383184980 728 384769841 729 386359066 730 387952661 731 389550632 732 391152985 733 392759726 734 394370861 735 395986396 736 397606337 737 399230690 738 400859461 739 402492656 740 404130281 741 405772342 742 407418845 743 409069796 744 410725201 745 412385066 746 414049397 747 415718200 748 417391481 749 419069246 750 420751501 751 422438252 752 424129505 753 425825266 754 427525541 755 429230336 756 430939657 757 432653510 758 434371901 759 436094836 760 437822321 761 439554362 762 441290965 763 443032136 764 444777881 765 446528206 766 448283117 767 450042620 768 451806721 769 453575426 770 455348741 771 457126672 772 458909225 773 460696406 774 462488221 775 464284676 776 466085777 777 467891530 778 469701941 779 471517016 780 473336761 781 475161182 782 476990285 783 478824076 784 480662561 785 482505746 786 484353637 787 486206240 788 488063561 789 489925606 790 491792381 791 493663892 792 495540145 793 497421146 794 499306901 795 501197416 796 503092697 797 504992750 798 506897581 799 508807196 800 510721601 801 512640802 802 514564805 803 516493616 804 518427241 805 520365686 806 522308957 807 524257060 808 526210001 809 528167786 810 530130421 811 532097912 812 534070265 813 536047486 814 538029581 815 540016556 816 542008417 817 544005170 818 546006821 819 548013376 820 550024841 821 552041222 822 554062525 823 556088756 824 558119921 825 560156026 826 562197077 827 564243080 828 566294041 829 568349966 830 570410861 831 572476732 832 574547585 833 576623426 834 578704261 835 580790096 836 582880937 837 584976790 838 587077661 839 589183556 840 591294481 841 593410442 842 595531445 843 597657496 844 599788601 845 601924766 846 604065997 847 606212300 848 608363681 849 610520146 850 612681701 851 614848352 852 617020105 853 619196966 854 621378941 855 623566036 856 625758257 857 627955610 858 630158101 859 632365736 860 634578521 861 636796462 862 639019565 863 641247836 864 643481281 865 645719906 866 647963717 867 650212720 868 652466921 869 654726326 870 656990941 871 659260772 872 661535825 873 663816106 874 666101621 875 668392376 876 670688377 877 672989630 878 675296141 879 677607916 880 679924961 881 682247282 882 684574885 883 686907776 884 689245961 885 691589446 886 693938237 887 696292340 888 698651761 889 701016506 890 703386581 891 705761992 892 708142745 893 710528846 894 712920301 895 715317116 896 717719297 897 720126850 898 722539781 899 724958096 900 727381801 901 729810902 902 732245405 903 734685316 904 737130641 905 739581386 906 742037557 907 744499160 908 746966201 909 749438686 910 751916621 911 754400012 912 756888865 913 759383186 914 761882981 915 764388256 916 766899017 917 769415270 918 771937021 919 774464276 920 776997041 921 779535322 922 782079125 923 784628456 924 787183321 925 789743726 926 792309677 927 794881180 928 797458241 929 800040866 930 802629061 931 805222832 932 807822185 933 810427126 934 813037661 935 815653796 936 818275537 937 820902890 938 823535861 939 826174456 940 828818681 941 831468542 942 834124045 943 836785196 944 839452001 945 842124466 946 844802597 947 847486400 948 850175881 949 852871046 950 855571901 951 858278452 952 860990705 953 863708666 954 866432341 955 869161736 956 871896857 957 874637710 958 877384301 959 880136636 960 882894721 961 885658562 962 888428165 963 891203536 964 893984681 965 896771606 966 899564317 967 902362820 968 905167121 969 907977226 970 910793141 971 913614872 972 916442425 973 919275806 974 922115021 975 924960076 976 927810977 977 930667730 978 933530341 979 936398816 980 939273161 981 942153382 982 945039485 983 947931476 984 950829361 985 953733146 986 956642837 987 959558440 988 962479961 989 965407406 990 968340781 991 971280092 992 974225345 993 977176546 994 980133701 995 983096816 996 986065897 997 989040950 998 992021981 999 995008996 1000 998002001