0 0 1 3 2 14 3 39 4 84 5 155 6 258 7 399 8 584 9 819 10 1110 11 1463 12 1884 13 2379 14 2954 15 3615 16 4368 17 5219 18 6174 19 7239 20 8420 21 9723 22 11154 23 12719 24 14424 25 16275 26 18278 27 20439 28 22764 29 25259 30 27930 31 30783 32 33824 33 37059 34 40494 35 44135 36 47988 37 52059 38 56354 39 60879 40 65640 41 70643 42 75894 43 81399 44 87164 45 93195 46 99498 47 106079 48 112944 49 120099 50 127550 51 135303 52 143364 53 151739 54 160434 55 169455 56 178808 57 188499 58 198534 59 208919 60 219660 61 230763 62 242234 63 254079 64 266304 65 278915 66 291918 67 305319 68 319124 69 333339 70 347970 71 363023 72 378504 73 394419 74 410774 75 427575 76 444828 77 462539 78 480714 79 499359 80 518480 81 538083 82 558174 83 578759 84 599844 85 621435 86 643538 87 666159 88 689304 89 712979 90 737190 91 761943 92 787244 93 813099 94 839514 95 866495 96 894048 97 922179 98 950894 99 980199 100 1010100 101 1040603 102 1071714 103 1103439 104 1135784 105 1168755 106 1202358 107 1236599 108 1271484 109 1307019 110 1343210 111 1380063 112 1417584 113 1455779 114 1494654 115 1534215 116 1574468 117 1615419 118 1657074 119 1699439 120 1742520 121 1786323 122 1830854 123 1876119 124 1922124 125 1968875 126 2016378 127 2064639 128 2113664 129 2163459 130 2214030 131 2265383 132 2317524 133 2370459 134 2424194 135 2478735 136 2534088 137 2590259 138 2647254 139 2705079 140 2763740 141 2823243 142 2883594 143 2944799 144 3006864 145 3069795 146 3133598 147 3198279 148 3263844 149 3330299 150 3397650 151 3465903 152 3535064 153 3605139 154 3676134 155 3748055 156 3820908 157 3894699 158 3969434 159 4045119 160 4121760 161 4199363 162 4277934 163 4357479 164 4438004 165 4519515 166 4602018 167 4685519 168 4770024 169 4855539 170 4942070 171 5029623 172 5118204 173 5207819 174 5298474 175 5390175 176 5482928 177 5576739 178 5671614 179 5767559 180 5864580 181 5962683 182 6061874 183 6162159 184 6263544 185 6366035 186 6469638 187 6574359 188 6680204 189 6787179 190 6895290 191 7004543 192 7114944 193 7226499 194 7339214 195 7453095 196 7568148 197 7684379 198 7801794 199 7920399 200 8040200 201 8161203 202 8283414 203 8406839 204 8531484 205 8657355 206 8784458 207 8912799 208 9042384 209 9173219 210 9305310 211 9438663 212 9573284 213 9709179 214 9846354 215 9984815 216 10124568 217 10265619 218 10407974 219 10551639 220 10696620 221 10842923 222 10990554 223 11139519 224 11289824 225 11441475 226 11594478 227 11748839 228 11904564 229 12061659 230 12220130 231 12379983 232 12541224 233 12703859 234 12867894 235 13033335 236 13200188 237 13368459 238 13538154 239 13709279 240 13881840 241 14055843 242 14231294 243 14408199 244 14586564 245 14766395 246 14947698 247 15130479 248 15314744 249 15500499 250 15687750 251 15876503 252 16066764 253 16258539 254 16451834 255 16646655 256 16843008 257 17040899 258 17240334 259 17441319 260 17643860 261 17847963 262 18053634 263 18260879 264 18469704 265 18680115 266 18892118 267 19105719 268 19320924 269 19537739 270 19756170 271 19976223 272 20197904 273 20421219 274 20646174 275 20872775 276 21101028 277 21330939 278 21562514 279 21795759 280 22030680 281 22267283 282 22505574 283 22745559 284 22987244 285 23230635 286 23475738 287 23722559 288 23971104 289 24221379 290 24473390 291 24727143 292 24982644 293 25239899 294 25498914 295 25759695 296 26022248 297 26286579 298 26552694 299 26820599 300 27090300 301 27361803 302 27635114 303 27910239 304 28187184 305 28465955 306 28746558 307 29028999 308 29313284 309 29599419 310 29887410 311 30177263 312 30468984 313 30762579 314 31058054 315 31355415 316 31654668 317 31955819 318 32258874 319 32563839 320 32870720 321 33179523 322 33490254 323 33802919 324 34117524 325 34434075 326 34752578 327 35073039 328 35395464 329 35719859 330 36046230 331 36374583 332 36704924 333 37037259 334 37371594 335 37707935 336 38046288 337 38386659 338 38729054 339 39073479 340 39419940 341 39768443 342 40118994 343 40471599 344 40826264 345 41182995 346 41541798 347 41902679 348 42265644 349 42630699 350 42997850 351 43367103 352 43738464 353 44111939 354 44487534 355 44865255 356 45245108 357 45627099 358 46011234 359 46397519 360 46785960 361 47176563 362 47569334 363 47964279 364 48361404 365 48760715 366 49162218 367 49565919 368 49971824 369 50379939 370 50790270 371 51202823 372 51617604 373 52034619 374 52453874 375 52875375 376 53299128 377 53725139 378 54153414 379 54583959 380 55016780 381 55451883 382 55889274 383 56328959 384 56770944 385 57215235 386 57661838 387 58110759 388 58562004 389 59015579 390 59471490 391 59929743 392 60390344 393 60853299 394 61318614 395 61786295 396 62256348 397 62728779 398 63203594 399 63680799 400 64160400 401 64642403 402 65126814 403 65613639 404 66102884 405 66594555 406 67088658 407 67585199 408 68084184 409 68585619 410 69089510 411 69595863 412 70104684 413 70615979 414 71129754 415 71646015 416 72164768 417 72686019 418 73209774 419 73736039 420 74264820 421 74796123 422 75329954 423 75866319 424 76405224 425 76946675 426 77490678 427 78037239 428 78586364 429 79138059 430 79692330 431 80249183 432 80808624 433 81370659 434 81935294 435 82502535 436 83072388 437 83644859 438 84219954 439 84797679 440 85378040 441 85961043 442 86546694 443 87134999 444 87725964 445 88319595 446 88915898 447 89514879 448 90116544 449 90720899 450 91327950 451 91937703 452 92550164 453 93165339 454 93783234 455 94403855 456 95027208 457 95653299 458 96282134 459 96913719 460 97548060 461 98185163 462 98825034 463 99467679 464 100113104 465 100761315 466 101412318 467 102066119 468 102722724 469 103382139 470 104044370 471 104709423 472 105377304 473 106048019 474 106721574 475 107397975 476 108077228 477 108759339 478 109444314 479 110132159 480 110822880 481 111516483 482 112212974 483 112912359 484 113614644 485 114319835 486 115027938 487 115738959 488 116452904 489 117169779 490 117889590 491 118612343 492 119338044 493 120066699 494 120798314 495 121532895 496 122270448 497 123010979 498 123754494 499 124500999 500 125250500 501 126003003 502 126758514 503 127517039 504 128278584 505 129043155 506 129810758 507 130581399 508 131355084 509 132131819 510 132911610 511 133694463 512 134480384 513 135269379 514 136061454 515 136856615 516 137654868 517 138456219 518 139260674 519 140068239 520 140878920 521 141692723 522 142509654 523 143329719 524 144152924 525 144979275 526 145808778 527 146641439 528 147477264 529 148316259 530 149158430 531 150003783 532 150852324 533 151704059 534 152558994 535 153417135 536 154278488 537 155143059 538 156010854 539 156881879 540 157756140 541 158633643 542 159514394 543 160398399 544 161285664 545 162176195 546 163069998 547 163967079 548 164867444 549 165771099 550 166678050 551 167588303 552 168501864 553 169418739 554 170338934 555 171262455 556 172189308 557 173119499 558 174053034 559 174989919 560 175930160 561 176873763 562 177820734 563 178771079 564 179724804 565 180681915 566 181642418 567 182606319 568 183573624 569 184544339 570 185518470 571 186496023 572 187477004 573 188461419 574 189449274 575 190440575 576 191435328 577 192433539 578 193435214 579 194440359 580 195448980 581 196461083 582 197476674 583 198495759 584 199518344 585 200544435 586 201574038 587 202607159 588 203643804 589 204683979 590 205727690 591 206774943 592 207825744 593 208880099 594 209938014 595 210999495 596 212064548 597 213133179 598 214205394 599 215281199 600 216360600 601 217443603 602 218530214 603 219620439 604 220714284 605 221811755 606 222912858 607 224017599 608 225125984 609 226238019 610 227353710 611 228473063 612 229596084 613 230722779 614 231853154 615 232987215 616 234124968 617 235266419 618 236411574 619 237560439 620 238713020 621 239869323 622 241029354 623 242193119 624 243360624 625 244531875 626 245706878 627 246885639 628 248068164 629 249254459 630 250444530 631 251638383 632 252836024 633 254037459 634 255242694 635 256451735 636 257664588 637 258881259 638 260101754 639 261326079 640 262554240 641 263786243 642 265022094 643 266261799 644 267505364 645 268752795 646 270004098 647 271259279 648 272518344 649 273781299 650 275048150 651 276318903 652 277593564 653 278872139 654 280154634 655 281441055 656 282731408 657 284025699 658 285323934 659 286626119 660 287932260 661 289242363 662 290556434 663 291874479 664 293196504 665 294522515 666 295852518 667 297186519 668 298524524 669 299866539 670 301212570 671 302562623 672 303916704 673 305274819 674 306636974 675 308003175 676 309373428 677 310747739 678 312126114 679 313508559 680 314895080 681 316285683 682 317680374 683 319079159 684 320482044 685 321889035 686 323300138 687 324715359 688 326134704 689 327558179 690 328985790 691 330417543 692 331853444 693 333293499 694 334737714 695 336186095 696 337638648 697 339095379 698 340556294 699 342021399 700 343490700 701 344964203 702 346441914 703 347923839 704 349409984 705 350900355 706 352394958 707 353893799 708 355396884 709 356904219 710 358415810 711 359931663 712 361451784 713 362976179 714 364504854 715 366037815 716 367575068 717 369116619 718 370662474 719 372212639 720 373767120 721 375325923 722 376889054 723 378456519 724 380028324 725 381604475 726 383184978 727 384769839 728 386359064 729 387952659 730 389550630 731 391152983 732 392759724 733 394370859 734 395986394 735 397606335 736 399230688 737 400859459 738 402492654 739 404130279 740 405772340 741 407418843 742 409069794 743 410725199 744 412385064 745 414049395 746 415718198 747 417391479 748 419069244 749 420751499 750 422438250 751 424129503 752 425825264 753 427525539 754 429230334 755 430939655 756 432653508 757 434371899 758 436094834 759 437822319 760 439554360 761 441290963 762 443032134 763 444777879 764 446528204 765 448283115 766 450042618 767 451806719 768 453575424 769 455348739 770 457126670 771 458909223 772 460696404 773 462488219 774 464284674 775 466085775 776 467891528 777 469701939 778 471517014 779 473336759 780 475161180 781 476990283 782 478824074 783 480662559 784 482505744 785 484353635 786 486206238 787 488063559 788 489925604 789 491792379 790 493663890 791 495540143 792 497421144 793 499306899 794 501197414 795 503092695 796 504992748 797 506897579 798 508807194 799 510721599 800 512640800 801 514564803 802 516493614 803 518427239 804 520365684 805 522308955 806 524257058 807 526209999 808 528167784 809 530130419 810 532097910 811 534070263 812 536047484 813 538029579 814 540016554 815 542008415 816 544005168 817 546006819 818 548013374 819 550024839 820 552041220 821 554062523 822 556088754 823 558119919 824 560156024 825 562197075 826 564243078 827 566294039 828 568349964 829 570410859 830 572476730 831 574547583 832 576623424 833 578704259 834 580790094 835 582880935 836 584976788 837 587077659 838 589183554 839 591294479 840 593410440 841 595531443 842 597657494 843 599788599 844 601924764 845 604065995 846 606212298 847 608363679 848 610520144 849 612681699 850 614848350 851 617020103 852 619196964 853 621378939 854 623566034 855 625758255 856 627955608 857 630158099 858 632365734 859 634578519 860 636796460 861 639019563 862 641247834 863 643481279 864 645719904 865 647963715 866 650212718 867 652466919 868 654726324 869 656990939 870 659260770 871 661535823 872 663816104 873 666101619 874 668392374 875 670688375 876 672989628 877 675296139 878 677607914 879 679924959 880 682247280 881 684574883 882 686907774 883 689245959 884 691589444 885 693938235 886 696292338 887 698651759 888 701016504 889 703386579 890 705761990 891 708142743 892 710528844 893 712920299 894 715317114 895 717719295 896 720126848 897 722539779 898 724958094 899 727381799 900 729810900 901 732245403 902 734685314 903 737130639 904 739581384 905 742037555 906 744499158 907 746966199 908 749438684 909 751916619 910 754400010 911 756888863 912 759383184 913 761882979 914 764388254 915 766899015 916 769415268 917 771937019 918 774464274 919 776997039 920 779535320 921 782079123 922 784628454 923 787183319 924 789743724 925 792309675 926 794881178 927 797458239 928 800040864 929 802629059 930 805222830 931 807822183 932 810427124 933 813037659 934 815653794 935 818275535 936 820902888 937 823535859 938 826174454 939 828818679 940 831468540 941 834124043 942 836785194 943 839451999 944 842124464 945 844802595 946 847486398 947 850175879 948 852871044 949 855571899 950 858278450 951 860990703 952 863708664 953 866432339 954 869161734 955 871896855 956 874637708 957 877384299 958 880136634 959 882894719 960 885658560 961 888428163 962 891203534 963 893984679 964 896771604 965 899564315 966 902362818 967 905167119 968 907977224 969 910793139 970 913614870 971 916442423 972 919275804 973 922115019 974 924960074 975 927810975 976 930667728 977 933530339 978 936398814 979 939273159 980 942153380 981 945039483 982 947931474 983 950829359 984 953733144 985 956642835 986 959558438 987 962479959 988 965407404 989 968340779 990 971280090 991 974225343 992 977176544 993 980133699 994 983096814 995 986065895 996 989040948 997 992021979 998 995008994 999 998001999 1000 1001001000