0 1 1 6 2 19 3 44 4 85 5 147 6 236 7 357 8 514 9 711 10 953 11 1246 12 1595 13 2004 14 2477 15 3019 16 3636 17 4333 18 5114 19 5983 20 6945 21 8006 22 9171 23 10444 24 11829 25 13331 26 14956 27 16709 28 18594 29 20615 30 22777 31 25086 32 27547 33 30164 34 32941 35 35883 36 38996 37 42285 38 45754 39 49407 40 53249 41 57286 42 61523 43 65964 44 70613 45 75475 46 80556 47 85861 48 91394 49 97159 50 103161 51 109406 52 115899 53 122644 54 129645 55 136907 56 144436 57 152237 58 160314 59 168671 60 177313 61 186246 62 195475 63 205004 64 214837 65 224979 66 235436 67 246213 68 257314 69 268743 70 280505 71 292606 72 305051 73 317844 74 330989 75 344491 76 358356 77 372589 78 387194 79 402175 80 417537 81 433286 82 449427 83 465964 84 482901 85 500243 86 517996 87 536165 88 554754 89 573767 90 593209 91 613086 92 633403 93 654164 94 675373 95 697035 96 719156 97 741741 98 764794 99 788319 100 812321 101 836806 102 861779 103 887244 104 913205 105 939667 106 966636 107 994117 108 1022114 109 1050631 110 1079673 111 1109246 112 1139355 113 1170004 114 1201197 115 1232939 116 1265236 117 1298093 118 1331514 119 1365503 120 1400065 121 1435206 122 1470931 123 1507244 124 1544149 125 1581651 126 1619756 127 1658469 128 1697794 129 1737735 130 1778297 131 1819486 132 1861307 133 1903764 134 1946861 135 1990603 136 2034996 137 2080045 138 2125754 139 2172127 140 2219169 141 2266886 142 2315283 143 2364364 144 2414133 145 2464595 146 2515756 147 2567621 148 2620194 149 2673479 150 2727481 151 2782206 152 2837659 153 2893844 154 2950765 155 3008427 156 3066836 157 3125997 158 3185914 159 3246591 160 3308033 161 3370246 162 3433235 163 3497004 164 3561557 165 3626899 166 3693036 167 3759973 168 3827714 169 3896263 170 3965625 171 4035806 172 4106811 173 4178644 174 4251309 175 4324811 176 4399156 177 4474349 178 4550394 179 4627295 180 4705057 181 4783686 182 4863187 183 4943564 184 5024821 185 5106963 186 5189996 187 5273925 188 5358754 189 5444487 190 5531129 191 5618686 192 5707163 193 5796564 194 5886893 195 5978155 196 6070356 197 6163501 198 6257594 199 6352639 200 6448641 201 6545606 202 6643539 203 6742444 204 6842325 205 6943187 206 7045036 207 7147877 208 7251714 209 7356551 210 7462393 211 7569246 212 7677115 213 7786004 214 7895917 215 8006859 216 8118836 217 8231853 218 8345914 219 8461023 220 8577185 221 8694406 222 8812691 223 8932044 224 9052469 225 9173971 226 9296556 227 9420229 228 9544994 229 9670855 230 9797817 231 9925886 232 10055067 233 10185364 234 10316781 235 10449323 236 10582996 237 10717805 238 10853754 239 10990847 240 11129089 241 11268486 242 11409043 243 11550764 244 11693653 245 11837715 246 11982956 247 12129381 248 12276994 249 12425799 250 12575801 251 12727006 252 12879419 253 13033044 254 13187885 255 13343947 256 13501236 257 13659757 258 13819514 259 13980511 260 14142753 261 14306246 262 14470995 263 14637004 264 14804277 265 14972819 266 15142636 267 15313733 268 15486114 269 15659783 270 15834745 271 16011006 272 16188571 273 16367444 274 16547629 275 16729131 276 16911956 277 17096109 278 17281594 279 17468415 280 17656577 281 17846086 282 18036947 283 18229164 284 18422741 285 18617683 286 18813996 287 19011685 288 19210754 289 19411207 290 19613049 291 19816286 292 20020923 293 20226964 294 20434413 295 20643275 296 20853556 297 21065261 298 21278394 299 21492959 300 21708961 301 21926406 302 22145299 303 22365644 304 22587445 305 22810707 306 23035436 307 23261637 308 23489314 309 23718471 310 23949113 311 24181246 312 24414875 313 24650004 314 24886637 315 25124779 316 25364436 317 25605613 318 25848314 319 26092543 320 26338305 321 26585606 322 26834451 323 27084844 324 27336789 325 27590291 326 27845356 327 28101989 328 28360194 329 28619975 330 28881337 331 29144286 332 29408827 333 29674964 334 29942701 335 30212043 336 30482996 337 30755565 338 31029754 339 31305567 340 31583009 341 31862086 342 32142803 343 32425164 344 32709173 345 32994835 346 33282156 347 33571141 348 33861794 349 34154119 350 34448121 351 34743806 352 35041179 353 35340244 354 35641005 355 35943467 356 36247636 357 36553517 358 36861114 359 37170431 360 37481473 361 37794246 362 38108755 363 38425004 364 38742997 365 39062739 366 39384236 367 39707493 368 40032514 369 40359303 370 40687865 371 41018206 372 41350331 373 41684244 374 42019949 375 42357451 376 42696756 377 43037869 378 43380794 379 43725535 380 44072097 381 44420486 382 44770707 383 45122764 384 45476661 385 45832403 386 46189996 387 46549445 388 46910754 389 47273927 390 47638969 391 48005886 392 48374683 393 48745364 394 49117933 395 49492395 396 49868756 397 50247021 398 50627194 399 51009279 400 51393281 401 51779206 402 52167059 403 52556844 404 52948565 405 53342227 406 53737836 407 54135397 408 54534914 409 54936391 410 55339833 411 55745246 412 56152635 413 56562004 414 56973357 415 57386699 416 57802036 417 58219373 418 58638714 419 59060063 420 59483425 421 59908806 422 60336211 423 60765644 424 61197109 425 61630611 426 62066156 427 62503749 428 62943394 429 63385095 430 63828857 431 64274686 432 64722587 433 65172564 434 65624621 435 66078763 436 66534996 437 66993325 438 67453754 439 67916287 440 68380929 441 68847686 442 69316563 443 69787564 444 70260693 445 70735955 446 71213356 447 71692901 448 72174594 449 72658439 450 73144441 451 73632606 452 74122939 453 74615444 454 75110125 455 75606987 456 76106036 457 76607277 458 77110714 459 77616351 460 78124193 461 78634246 462 79146515 463 79661004 464 80177717 465 80696659 466 81217836 467 81741253 468 82266914 469 82794823 470 83324985 471 83857406 472 84392091 473 84929044 474 85468269 475 86009771 476 86553556 477 87099629 478 87647994 479 88198655 480 88751617 481 89306886 482 89864467 483 90424364 484 90986581 485 91551123 486 92117996 487 92687205 488 93258754 489 93832647 490 94408889 491 94987486 492 95568443 493 96151764 494 96737453 495 97325515 496 97915956 497 98508781 498 99103994 499 99701599 500 100301601 501 100904006 502 101508819 503 102116044 504 102725685 505 103337747 506 103952236 507 104569157 508 105188514 509 105810311 510 106434553 511 107061246 512 107690395 513 108322004 514 108956077 515 109592619 516 110231636 517 110873133 518 111517114 519 112163583 520 112812545 521 113464006 522 114117971 523 114774444 524 115433429 525 116094931 526 116758956 527 117425509 528 118094594 529 118766215 530 119440377 531 120117086 532 120796347 533 121478164 534 122162541 535 122849483 536 123538996 537 124231085 538 124925754 539 125623007 540 126322849 541 127025286 542 127730323 543 128437964 544 129148213 545 129861075 546 130576556 547 131294661 548 132015394 549 132738759 550 133464761 551 134193406 552 134924699 553 135658644 554 136395245 555 137134507 556 137876436 557 138621037 558 139368314 559 140118271 560 140870913 561 141626246 562 142384275 563 143145004 564 143908437 565 144674579 566 145443436 567 146215013 568 146989314 569 147766343 570 148546105 571 149328606 572 150113851 573 150901844 574 151692589 575 152486091 576 153282356 577 154081389 578 154883194 579 155687775 580 156495137 581 157305286 582 158118227 583 158933964 584 159752501 585 160573843 586 161397996 587 162224965 588 163054754 589 163887367 590 164722809 591 165561086 592 166402203 593 167246164 594 168092973 595 168942635 596 169795156 597 170650541 598 171508794 599 172369919 600 173233921 601 174100806 602 174970579 603 175843244 604 176718805 605 177597267 606 178478636 607 179362917 608 180250114 609 181140231 610 182033273 611 182929246 612 183828155 613 184730004 614 185634797 615 186542539 616 187453236 617 188366893 618 189283514 619 190203103 620 191125665 621 192051206 622 192979731 623 193911244 624 194845749 625 195783251 626 196723756 627 197667269 628 198613794 629 199563335 630 200515897 631 201471486 632 202430107 633 203391764 634 204356461 635 205324203 636 206294996 637 207268845 638 208245754 639 209225727 640 210208769 641 211194886 642 212184083 643 213176364 644 214171733 645 215170195 646 216171756 647 217176421 648 218184194 649 219195079 650 220209081 651 221226206 652 222246459 653 223269844 654 224296365 655 225326027 656 226358836 657 227394797 658 228433914 659 229476191 660 230521633 661 231570246 662 232622035 663 233677004 664 234735157 665 235796499 666 236861036 667 237928773 668 238999714 669 240073863 670 241151225 671 242231806 672 243315611 673 244402644 674 245492909 675 246586411 676 247683156 677 248783149 678 249886394 679 250992895 680 252102657 681 253215686 682 254331987 683 255451564 684 256574421 685 257700563 686 258829996 687 259962725 688 261098754 689 262238087 690 263380729 691 264526686 692 265675963 693 266828564 694 267984493 695 269143755 696 270306356 697 271472301 698 272641594 699 273814239 700 274990241 701 276169606 702 277352339 703 278538444 704 279727925 705 280920787 706 282117036 707 283316677 708 284519714 709 285726151 710 286935993 711 288149246 712 289365915 713 290586004 714 291809517 715 293036459 716 294266836 717 295500653 718 296737914 719 297978623 720 299222785 721 300470406 722 301721491 723 302976044 724 304234069 725 305495571 726 306760556 727 308029029 728 309300994 729 310576455 730 311855417 731 313137886 732 314423867 733 315713364 734 317006381 735 318302923 736 319602996 737 320906605 738 322213754 739 323524447 740 324838689 741 326156486 742 327477843 743 328802764 744 330131253 745 331463315 746 332798956 747 334138181 748 335480994 749 336827399 750 338177401 751 339531006 752 340888219 753 342249044 754 343613485 755 344981547 756 346353236 757 347728557 758 349107514 759 350490111 760 351876353 761 353266246 762 354659795 763 356057004 764 357457877 765 358862419 766 360270636 767 361682533 768 363098114 769 364517383 770 365940345 771 367367006 772 368797371 773 370231444 774 371669229 775 373110731 776 374555956 777 376004909 778 377457594 779 378914015 780 380374177 781 381838086 782 383305747 783 384777164 784 386252341 785 387731283 786 389213996 787 390700485 788 392190754 789 393684807 790 395182649 791 396684286 792 398189723 793 399698964 794 401212013 795 402728875 796 404249556 797 405774061 798 407302394 799 408834559 800 410370561 801 411910406 802 413454099 803 415001644 804 416553045 805 418108307 806 419667436 807 421230437 808 422797314 809 424368071 810 425942713 811 427521246 812 429103675 813 430690004 814 432280237 815 433874379 816 435472436 817 437074413 818 438680314 819 440290143 820 441903905 821 443521606 822 445143251 823 446768844 824 448398389 825 450031891 826 451669356 827 453310789 828 454956194 829 456605575 830 458258937 831 459916286 832 461577627 833 463242964 834 464912301 835 466585643 836 468262996 837 469944365 838 471629754 839 473319167 840 475012609 841 476710086 842 478411603 843 480117164 844 481826773 845 483540435 846 485258156 847 486979941 848 488705794 849 490435719 850 492169721 851 493907806 852 495649979 853 497396244 854 499146605 855 500901067 856 502659636 857 504422317 858 506189114 859 507960031 860 509735073 861 511514246 862 513297555 863 515085004 864 516876597 865 518672339 866 520472236 867 522276293 868 524084514 869 525896903 870 527713465 871 529534206 872 531359131 873 533188244 874 535021549 875 536859051 876 538700756 877 540546669 878 542396794 879 544251135 880 546109697 881 547972486 882 549839507 883 551710764 884 553586261 885 555466003 886 557349996 887 559238245 888 561130754 889 563027527 890 564928569 891 566833886 892 568743483 893 570657364 894 572575533 895 574497995 896 576424756 897 578355821 898 580291194 899 582230879 900 584174881 901 586123206 902 588075859 903 590032844 904 591994165 905 593959827 906 595929836 907 597904197 908 599882914 909 601865991 910 603853433 911 605845246 912 607841435 913 609842004 914 611846957 915 613856299 916 615870036 917 617888173 918 619910714 919 621937663 920 623969025 921 626004806 922 628045011 923 630089644 924 632138709 925 634192211 926 636250156 927 638312549 928 640379394 929 642450695 930 644526457 931 646606686 932 648691387 933 650780564 934 652874221 935 654972363 936 657074996 937 659182125 938 661293754 939 663409887 940 665530529 941 667655686 942 669785363 943 671919564 944 674058293 945 676201555 946 678349356 947 680501701 948 682658594 949 684820039 950 686986041 951 689156606 952 691331739 953 693511444 954 695695725 955 697884587 956 700078036 957 702276077 958 704478714 959 706685951 960 708897793 961 711114246 962 713335315 963 715561004 964 717791317 965 720026259 966 722265836 967 724510053 968 726758914 969 729012423 970 731270585 971 733533406 972 735800891 973 738073044 974 740349869 975 742631371 976 744917556 977 747208429 978 749503994 979 751804255 980 754109217 981 756418886 982 758733267 983 761052364 984 763376181 985 765704723 986 768037996 987 770376005 988 772718754 989 775066247 990 777418489 991 779775486 992 782137243 993 784503764 994 786875053 995 789251115 996 791631956 997 794017581 998 796407994 999 798803199 1000 801203201