0 1 1 1 2 3 3 6 4 9 5 15 6 25 7 34 8 51 9 73 10 97 11 132 12 178 13 226 14 294 15 376 16 466 17 582 18 722 19 872 20 1062 21 1282 22 1522 23 1812 24 2147 25 2507 26 2937 27 3422 28 3947 29 4557 30 5243 31 5978 32 6825 33 7763 34 8771 35 9912 36 11172 37 12516 38 14028 39 15680 40 17444 41 19404 42 21540 43 23808 44 26316 45 29028 46 31908 47 35064 48 38469 49 42069 50 45999 51 50214 52 54669 53 59499 54 64669 55 70114 56 75999 57 82269 58 88869 59 95964 60 103510 61 111430 62 119922 63 128920 64 138358 65 148434 66 159094 67 170248 68 182130 69 194662 70 207766 71 221676 72 236327 73 251615 74 267813 75 284830 76 302575 77 321321 78 340991 79 361466 80 383061 81 405671 82 429191 83 453936 84 479816 85 506696 86 534936 87 564416 88 595016 89 627096 90 660552 91 695232 92 731544 93 769352 94 808520 95 849456 96 892041 97 936105 98 982107 99 1029894 100 1079313 101 1130823 102 1184289 103 1239522 104 1297035 105 1356657 106 1418217 107 1482228 108 1548538 109 1616938 110 1687998 111 1761528 112 1837338 113 1915998 114 1997338 115 2081128 116 2167998 117 2257738 118 2350138 119 2445828 120 2544619 121 2646259 122 2751441 123 2859934 124 2971507 125 3086853 126 3205763 127 3327962 128 3454209 129 3584251 130 3717835 131 3855720 132 3997676 133 4143404 134 4293732 135 4448384 136 4607084 137 4770660 138 4938860 139 5111360 140 5289060 141 5471660 142 5658860 143 5851560 144 6049485 145 6252285 146 6460935 147 6675110 148 6894485 149 7120035 150 7351461 151 7588386 152 7831863 153 8081541 154 8337069 155 8599500 156 8868510 157 9143694 158 9426186 159 9715608 160 10011582 161 10315242 162 10626238 163 10944136 164 11270154 165 11603886 166 11944926 167 12294492 168 12652207 169 13017607 170 13391997 171 13774942 172 14166007 173 14566497 174 14976007 175 15394042 176 15821997 177 16259407 178 16705807 179 17162592 180 17629328 181 18105488 182 18592560 183 19090048 184 19597456 185 20116272 186 20646032 187 21186176 188 21738288 189 22301840 190 22876304 191 23463264 192 24062225 193 24672593 194 25296051 195 25932038 196 26579993 197 27241599 198 27916329 199 28603554 200 29305059 201 30020249 202 30748529 203 31491684 204 32249154 205 33020274 206 33806934 207 34608504 208 35424354 209 36256374 210 37103970 211 37966440 212 38845782 213 39741330 214 40652418 215 41581044 216 42526579 217 43488283 218 44468265 219 45465822 220 46480251 221 47513661 222 48565387 223 49634650 224 50723673 225 51831715 226 52958035 227 54104856 228 55271476 229 56457076 230 57663996 231 58891456 232 60138676 233 61407996 234 62698676 235 64009856 236 65343996 237 66700276 238 68077876 239 69479256 240 70903637 241 72350117 242 73821279 243 75316262 244 76834205 245 78377691 246 79945901 247 81537890 248 83156367 249 84800429 250 86469173 251 88165308 252 89887974 253 91636182 254 93412770 255 95216792 256 97047302 257 98907138 258 100795398 259 102711048 260 104657058 261 106632438 262 108636198 263 110671308 264 112736823 265 114831663 266 116958933 267 119117598 268 121306623 269 123529113 270 125784079 271 128070394 272 130391301 273 132745719 274 135132567 275 137555088 276 140012248 277 142502872 278 145030344 279 147593536 280 150191320 281 152827080 282 155499736 283 158208064 284 160955592 285 163741144 286 166563544 287 169426320 288 172328345 289 175268345 290 178249995 291 181272070 292 184333345 293 187437495 294 190583345 295 193769570 296 196999995 297 200273345 298 203588345 299 206948820 300 210353546 301 213801146 302 217295598 303 220835576 304 224419754 305 228052110 306 231731370 307 235456104 308 239230446 309 243053018 310 246922442 311 250842852 312 254812923 313 258831171 314 262901889 315 267023646 316 271195011 317 275420277 318 279698067 319 284026842 320 288411057 321 292849227 322 297339867 323 301887432 324 306490492 325 311147452 326 315862932 327 320635392 328 325463292 329 330351252 330 335297788 331 340301248 332 345366420 333 350491708 334 355675516 335 360922632 336 366231517 337 371600461 338 377034423 339 382531750 340 388090789 341 393716499 342 399407285 343 405161378 344 410983911 345 416873173 346 422827453 347 428851884 348 434944814 349 441104414 350 447335994 351 453637784 352 460008014 353 466451994 354 472968014 355 479554184 356 486215994 357 492951614 358 499759214 359 506644284 360 513605055 361 520639575 362 527753517 363 534944990 364 542212103 365 549560529 366 556988439 367 564493818 368 572082525 369 579752607 370 587502111 371 595336896 372 603255072 373 611254560 374 619341408 375 627513600 376 635769120 377 644114016 378 652546336 379 661063936 380 669673056 381 678371616 382 687157536 383 696037056 384 705008161 385 714068641 386 723224931 387 732474886 388 741816361 389 751255791 390 760791097 391 770420002 392 780149139 393 789976297 394 799899265 395 809924676 396 820050386 397 830274050 398 840602502 399 851033464 400 861564658 401 872202918 402 882946034 403 893791592 404 904746630 405 915808802 406 926975762 407 938254548 408 949642883 409 961138283 410 972747993 411 984469598 412 996300683 413 1008248493 414 1020310683 415 1032484698 416 1044777993 417 1057188083 418 1069712483 419 1082358648 420 1095124164 421 1108006404 422 1121013036 423 1134141504 424 1147389252 425 1160763948 426 1174263108 427 1187884032 428 1201634604 429 1215512196 430 1229514180 431 1243648440 432 1257912421 433 1272303349 434 1286829327 435 1301487654 436 1316275629 437 1331201355 438 1346262205 439 1361455330 440 1376789055 441 1392260605 442 1407867205 443 1423617180 444 1439507830 445 1455536230 446 1471710930 447 1488029080 448 1504487830 449 1521095730 450 1537850006 451 1554747656 452 1571797458 453 1588996486 454 1606341814 455 1623842220 456 1641494855 457 1659296639 458 1677256581 459 1695371678 460 1713638927 461 1732067337 462 1750653983 463 1769395706 464 1788301749 465 1807369031 466 1826594471 467 1845987312 468 1865544552 469 1885262952 470 1905151992 471 1925208512 472 1945429352 473 1965823992 474 1986389352 475 2007122112 476 2028031992 477 2049115752 478 2070370152 479 2091804912 480 2113416873 481 2135202633 482 2157172155 483 2179322118 484 2201649201 485 2224163367 486 2246861377 487 2269739746 488 2292808683 489 2316064785 490 2339504649 491 2363138484 492 2386962970 493 2410974538 494 2435183646 495 2459586808 496 2484180538 497 2508975294 498 2533967674 499 2559154024 500 2584545054 501 2610137194 502 2635926874 503 2661924804 504 2688127499 505 2714531219 506 2741146929 507 2767970974 508 2794999699 509 2822244069 510 2849700515 511 2877365210 512 2905249377 513 2933349275 514 2961661163 515 2990196264 516 3018950924 517 3047921228 518 3077118660 519 3106539392 520 3136179596 521 3166050756 522 3196149132 523 3226470720 524 3257027268 525 3287814860 526 3318829580 527 3350083176 528 3381571821 529 3413291421 530 3445253991 531 3477455526 532 3509892021 533 3542575491 534 3575502021 535 3608667426 536 3642083991 537 3675747621 538 3709654221 539 3743816076 540 3778229182 541 3812889262 542 3847808874 543 3882983832 544 3918409950 545 3954099786 546 3990049246 547 4026253960 548 4062726762 549 4099463374 550 4136459518 551 4173728028 552 4211264719 553 4249065127 554 4287142365 555 4325492062 556 4364109847 557 4403008833 558 4442184743 559 4481633018 560 4521367053 561 4561382383 562 4601674543 563 4642256928 564 4683125168 565 4724274608 566 4765718928 567 4807453568 568 4849473968 569 4891793808 570 4934408624 571 4977313664 572 5020522896 573 5064031664 574 5107835312 575 5151947808 576 5196364593 577 5241080817 578 5286110739 579 5331449606 580 5377092665 581 5423054175 582 5469329481 583 5515913634 584 5562821187 585 5610047289 586 5657587089 587 5705455140 588 5753646690 589 5802156690 590 5850999990 591 5900171640 592 5949666690 593 5999499990 594 6049666690 595 6100161640 596 6150999990 597 6202176690 598 6253686690 599 6305545140 600 6357747091 601 6410287291 602 6463181193 603 6516423646 604 6570009499 605 6623954205 606 6678252715 607 6732899674 608 6787910841 609 6843280963 610 6899004787 611 6955098072 612 7011555668 613 7068372116 614 7125563484 615 7183124416 616 7241049556 617 7299354972 618 7358035412 619 7417085312 620 7476521052 621 7536337172 622 7596528212 623 7657110552 624 7718078837 625 7779427397 626 7841172927 627 7903309862 628 7965832637 629 8028757947 630 8092080333 631 8155794018 632 8219916015 633 8284440653 634 8349362261 635 8414697852 636 8480441862 637 8546588406 638 8613154818 639 8680135320 640 8747524134 641 8815338594 642 8883573030 643 8952221448 644 9021301506 645 9090807318 646 9160732998 647 9231096204 648 9301891159 649 9373111759 650 9444775989 651 9516877854 652 9589411359 653 9662394489 654 9735821359 655 9809685754 656 9884005989 657 9958775959 658 10033989559 659 10109665104 660 10185796600 661 10262377720 662 10339427112 663 10416938560 664 10494905848 665 10573347624 666 10652257784 667 10731629888 668 10811482920 669 10891810552 670 10972606456 671 11053889616 672 11135653817 673 11217892505 674 11300625003 675 11383844870 676 11467545665 677 11551746711 678 11636441681 679 11721623906 680 11807313051 681 11893502561 682 11980185881 683 12067382676 684 12155086506 685 12243290586 686 12332014926 687 12421252856 688 12510997706 689 12601269486 690 12692061642 691 12783367272 692 12875206734 693 12967573242 694 13060460010 695 13153887396 696 13247848731 697 13342336995 698 13437372897 699 13532949534 700 13629060003 701 13725725013 702 13822937779 703 13920691162 704 14019006225 705 14117875947 706 14217293307 707 14317279368 708 14417827228 709 14518929628 710 14620607988 711 14722855168 712 14825664028 713 14929055988 714 15033024028 715 15137560768 716 15242687988 717 15348398428 718 15454684828 719 15561568968 720 15669043709 721 15777101549 722 15885764631 723 15995025574 724 16104876997 725 16215341043 726 16326410453 727 16438077602 728 16550364999 729 16663265141 730 16776770525 731 16890903660 732 17005657166 733 17121023294 734 17237024922 735 17353654424 736 17470904174 737 17588797050 738 17707325550 739 17826481800 740 17946289050 741 18066739550 742 18187825550 743 18309570300 744 18431966175 745 18555005175 746 18678710925 747 18803075550 748 18928091175 749 19053781425 750 19180138551 751 19307154426 752 19434853053 753 19563226431 754 19692266559 755 19821997440 756 19952411200 757 20083499584 758 20215286976 759 20347765248 760 20480926272 761 20614794432 762 20749361728 763 20884619776 764 21020593344 765 21157274176 766 21294654016 767 21432757632 768 21571576897 769 21711103297 770 21851361987 771 21992344582 772 22134042697 773 22276481487 774 22419652697 775 22563547682 776 22708191987 777 22853577097 778 22999694497 779 23146569732 780 23294194418 781 23442559778 782 23591691750 783 23741581688 784 23892220946 785 24043635462 786 24195816722 787 24348755816 788 24502479078 789 24656977730 790 24812242994 791 24968301204 792 25125143715 793 25282761483 794 25441181241 795 25600394078 796 25760391083 797 25921198989 798 26082809019 799 26245211994 800 26408435049 801 26572469139 802 26737305219 803 26902970424 804 27069455844 805 27236752164 806 27404886924 807 27573850944 808 27743635044 809 27914266764 810 28085737060 811 28258036480 812 28431192972 813 28605197220 814 28780039908 815 28955748984 816 29132315269 817 29309729173 818 29488019055 819 29667175462 820 29847188941 821 30028087851 822 30209862877 823 30392504290 824 30576040863 825 30760463005 826 30945761125 827 31131963996 828 31319062166 829 31507045766 830 31695943986 831 31885747096 832 32076445366 833 32268067986 834 32460605366 835 32654047496 836 32848423986 837 33043724966 838 33239940566 839 33437100396 840 33635194727 841 33834213407 842 34034186469 843 34235103902 844 34436955695 845 34639771881 846 34843542591 847 35048257530 848 35253947157 849 35460601319 850 35668209863 851 35876803248 852 36086371464 853 36296904072 854 36508431960 855 36720944832 856 36934432392 857 37148925528 858 37364414088 859 37580887488 860 37798377048 861 38016872328 862 38236362888 863 38456880048 864 38678413513 865 38900952553 866 39124528923 867 39349132038 868 39574751313 869 39801418503 870 40029123169 871 40257854434 872 40487644491 873 40718482609 874 40950358057 875 41183303028 876 41417306938 877 41652358762 878 41888491134 879 42125693176 880 42363954010 881 42603306270 882 42843739226 883 43085241704 884 43327846782 885 43571543434 886 43816320634 887 44062211460 888 44309205035 889 44557290035 890 44806499985 891 45056823710 892 45308250035 893 45560812485 894 45814500035 895 46069301210 896 46325249985 897 46582335035 898 46840545035 899 47099913960 900 47360430636 901 47622083436 902 47884906788 903 48148889216 904 48414019244 905 48680331300 906 48947814060 907 49216455744 908 49486291236 909 49757308908 910 50029497132 911 50302890792 912 50577478413 913 50853248061 914 51130235079 915 51408427686 916 51687814101 917 51968429667 918 52250262757 919 52533301282 920 52817581047 921 53103090117 922 53389816557 923 53677796172 924 53967017182 925 54257467342 926 54549182922 927 54842151832 928 55136361982 929 55431849642 930 55728602878 931 56026609288 932 56325905610 933 56626479598 934 56928319006 935 57231460572 936 57535892207 937 57841601351 938 58148625213 939 58456951390 940 58766567479 941 59077510689 942 59389768775 943 59703329018 944 60018229101 945 60334456463 946 60651998543 947 60970893024 948 61291127504 949 61612689104 950 61935615984 951 62259895424 952 62585514704 953 62912511984 954 63240874704 955 63570589824 956 63901695984 957 64234180304 958 64568029904 959 64903283424 960 65239928145 961 65577950865 962 65917390707 963 66258234630 964 66600469593 965 66944134719 966 67289217129 967 67635703458 968 67983633315 969 68332993497 970 68683770801 971 69036004836 972 69389682562 973 69744790450 974 70101368598 975 70459403640 976 70818882210 977 71179844406 978 71542277026 979 71906166376 980 72271553046 981 72638423506 982 73006764226 983 73376615796 984 73747964851 985 74120797531 986 74495154921 987 74871023326 988 75248389051 989 75627293181 990 76007722187 991 76389662042 992 76773154329 993 77158185187 994 77544740755 995 77932862616 996 78322537076 997 78713749940 998 79106543292 999 79500903104 1000 79896815348