0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 29 10 40 11 52 12 70 13 89 14 116 15 146 16 186 17 230 18 288 19 352 20 434 21 525 22 638 23 764 24 919 25 1090 26 1297 27 1527 28 1801 29 2104 30 2462 31 2857 32 3319 33 3828 34 4417 35 5066 36 5812 37 6630 38 7564 39 8588 40 9749 41 11018 42 12450 43 14012 44 15765 45 17674 46 19805 47 22122 48 24699 49 27493 50 30588 51 33940 52 37638 53 41635 54 46031 55 50774 56 55974 57 61575 58 67696 59 74280 60 81457 61 89162 62 97539 63 106522 64 116263 65 126692 66 137977 67 150042 68 163069 69 176978 70 191964 71 207945 72 225132 73 243434 74 263081 75 283981 76 306376 77 330170 78 355626 79 382641 80 411498 81 442089 82 474715 83 509267 84 546067 85 584996 86 626401 87 670162 88 716644 89 765722 90 817789 91 872713 92 930912 93 992250 94 1057169 95 1125532 96 1197809 97 1273852 98 1354164 99 1438596 100 1527675 101 1621248 102 1719877 103 1823402 104 1932418 105 2046761 106 2167057 107 2293142 108 2425678 109 2564490 110 2710281 111 2862876 112 3023010 113 3190504 114 3366137 115 3549724 116 3742085 117 3943032 118 4153425 119 4373077 120 4602893 121 4842675 122 5093379 123 5354809 124 5627961 125 5912637 126 6209887 127 6519507 128 6842599 129 7178957 130 7529733 131 7894724 132 8275137 133 8670760 134 9082861 135 9511232 136 9957192 137 10420532 138 10902637 139 11403294 140 11923951 141 12464395 142 13026135 143 13608964 144 14214458 145 14842402 146 15494446 147 16170382 148 16871922 149 17598860 150 18352987 151 19134095 152 19944051 153 20782650 154 21651833 155 22551404 156 23483384 157 24447572 158 25446077 159 26478708 160 27547650 161 28652717 162 29796187 163 30977876 164 32200152 165 33462838 166 34768390 167 36116644 168 37510152 169 38948747 170 40435085 171 41969014 172 43553280 173 45187741 174 46875252 175 48615677 176 50411977 177 52264027 178 54174893 179 56144468 180 58175930 181 60269174 182 62427499 183 64650820 184 66942543 185 69302598 186 71734518 187 74238244 188 76817433 189 79472043 190 82205853 191 85018845 192 87914929 193 90894094 194 93960390 195 97113833 196 100358598 197 103694722 198 107126527 199 110654067 200 114281808 201 118009827 202 121842732 203 125780632 204 129828285 205 133985814 206 138258138 207 142645414 208 147152707 209 151780202 210 156533133 211 161411709 212 166421329 213 171562234 214 176839986 215 182254866 216 187812609 217 193513517 218 199363509 219 205362930 220 211517867 221 217828702 222 224301714 223 230937318 224 237741982 225 244716161 226 251866510 227 259193534 228 266704085 229 274398698 230 282284434 231 290361881 232 298638292 233 307114302 234 315797382 235 324688210 236 333794471 237 343116894 238 352663377 239 362434709 240 372439012 241 382677115 242 393157376 243 403880689 244 414855630 245 426083152 246 437572076 247 449323409 248 461346215 249 473641563 250 486218758 251 499078942 252 512231672 253 525678142 254 539428174 255 553483040 256 567852809 257 582538824 258 597551430 259 612892037 260 628571262 261 644590591 262 660960912 263 677683798 264 694770420 265 712222416 266 730051254 267 748258664 268 766856392 269 785846254 270 805240304 271 825040439 272 845259018 273 865898029 274 886970134 275 908477424 276 930432877 277 952838664 278 975708094 279 999043446 280 1022858341 281 1047155159 282 1071947864 283 1097238934 284 1123042672 285 1149361664 286 1176210551 287 1203592039 288 1231521121 289 1260000599 290 1289045834 291 1318659754 292 1348858067 293 1379643821 294 1411033104 295 1443029079 296 1475648211 297 1508893789 298 1542782654 299 1577318234 300 1612517760 301 1648384775 302 1684936916 303 1722177872 304 1760125666 305 1798784126 306 1838171695 307 1878292336 308 1919164909 309 1960793523 310 2003197454 311 2046380971 312 2090363781 313 2135150288 314 2180760647 315 2227199430 316 2274487218 317 2322628744 318 2371645052 319 2421541031 320 2472338185 321 2524041571 322 2576673152 323 2630238168 324 2684759056 325 2740241214 326 2796707571 327 2854163716 328 2912633049 329 2972121343 330 3032652506 331 3094232491 332 3156885711 333 3220618312 334 3285455211 335 3351402762 336 3418486403 337 3486712669 338 3556107538 339 3626677762 340 3698449836 341 3771430722 342 3845647471 343 3921107251 344 3997837666 345 4075846103 346 4155160719 347 4235789136 348 4317760081 349 4401081384 350 4485782362 351 4571871089 352 4659377449 353 4748309754 354 4838698495 355 4930552218 356 5023902018 357 5118756689 358 5215147930 359 5313084799 360 5412599618 361 5513701681 362 5616423953 363 5720776003 364 5826791415 365 5934480026 366 6043876081 367 6154989681 368 6267855730 369 6382484607 370 6498911875 371 6617148209 372 6737229849 373 6859167738 374 6982998815 375 7108734330 376 7236411897 377 7366043066 378 7497666170 379 7631293055 380 7766962770 381 7904687473 382 8044506929 383 8186433626 384 8330508065 385 8476743035 386 8625179795 387 8775831476 388 8928740071 389 9083919046 390 9241411173 391 9401230249 392 9563419823 393 9727994039 394 9894997223 395 10064443886 396 10236379151 397 10410817866 398 10587805975 399 10767358705 400 10949522796 401 11134313847 402 11321779441 403 11511935546 404 11704830585 405 11900480912 406 12098935791 407 12300211981 408 12504359609 409 12711395809 410 12921371595 411 13134304520 412 13350246459 413 13569215378 414 13791264061 415 14016410883 416 14244709536 417 14476178821 418 14710873339 419 14948812338 420 15190051350 421 15434610039 422 15682544893 423 15933876038 424 16188660892 425 16446920036 426 16708711868 427 16974057421 428 17243016071 429 17515609321 430 17791897527 431 18071902683 432 18355686148 433 18643270376 434 18934717755 435 19230051246 436 19529334239 437 19832590196 438 20139883561 439 20451238293 440 20766719889 441 21086352824 442 21410203649 443 21738297378 444 22070701640 445 22407441956 446 22748587060 447 23094163028 448 23444239673 449 23798843619 450 24158045811 451 24521873419 452 24890398518 453 25263648844 454 25641697604 455 26024573123 456 26412349765 457 26805056411 458 27202768611 459 27605515852 460 28013374842 461 28426375668 462 28844596251 463 29268067275 464 29696867873 465 30131029347 466 30570632044 467 31015707908 468 31466338526 469 31922556451 470 32384444539 471 32852036003 472 33325414941 473 33804615220 474 34289722236 475 34780770508 476 35277846729 477 35780986091 478 36290276587 479 36805754107 480 37327507971 481 37855574733 482 38390045070 483 38930956254 484 39478400290 485 40032415162 486 40593094262 487 41160476283 488 41734656004 489 42315672849 490 42903622987 491 43498546599 492 44100541271 493 44709647908 494 45325965544 495 45949535862 496 46580459316 497 47218778361 498 47864594931 499 48517952251 500 49178953735 501 49847643401 502 50524126146 503 51208446808 504 51900711796 505 52600966733 506 53309319572 507 54025816778 508 54750567819 509 55483619996 510 56225084354 511 56975009028 512 57733506640 513 58500626183 514 59276481860 515 60061123550 516 60854667066 517 61657163138 518 62468729223 519 63289416959 520 64119345418 521 64958567141 522 65807202878 523 66665306072 524 67532999151 525 68410336485 526 69297442184 527 70194371573 528 71101250476 529 72018135137 530 72945153128 531 73882361672 532 74829890059 533 75787796486 534 76756212026 535 77735195849 536 78724880812 537 79725327083 538 80736669308 539 81758968683 540 82792361674 541 83836910469 542 84892753390 543 85959953678 544 87038651481 545 88128911088 546 89230874540 547 90344607173 548 91470252922 549 92607878197 550 93757628832 551 94919572341 552 96093856490 553 97280549861 554 98479802188 555 99691683184 556 100916344521 557 102153857038 558 103404374414 559 104667968613 560 105944795323 561 107234927660 562 108538523326 563 109855656622 564 111186487297 565 112531090800 566 113889628965 567 115262178453 568 116648903153 569 118049880933 570 119465277808 571 120895172853 572 122339734210 573 123799042190 574 125273267068 575 126762490423 576 128266884698 577 129786532703 578 131321609088 579 132872197960 580 134438476145 581 136020529043 582 137618535728 583 139232582893 584 140862851863 585 142509430653 586 144172502845 587 145852157810 588 147548581423 589 149261864373 590 150992194868 591 152739664983 592 154504465228 593 156286689060 594 158086529365 595 159904080983 596 161739539178 597 163593000203 598 165464661708 599 167354621393 600 169263079331 601 171190134631 602 173135989830 603 175100745516 604 177084606658 605 179087675320 606 181110158979 607 183152161175 608 185213891897 609 187295456192 610 189397066568 611 191518829615 612 193660960398 613 195823567012 614 198006867121 615 200210970396 616 202436097069 617 204682358383 618 206949977216 619 209239066385 620 211549851417 621 213882446735 622 216237080523 623 218613868847 624 221013042587 625 223434719413 626 225879132945 627 228346402530 628 230836764496 629 233350339864 630 235887367750 631 238447970850 632 241032391072 633 243640752821 634 246273300805 635 248930161176 636 251611581482 637 254317689583 638 257048735912 639 259804850111 640 262586285467 641 265393173401 642 268225770135 643 271084208872 644 273968748773 645 276879524857 646 279816799233 647 282780708775 648 285771518582 649 288789367343 650 291834523193 651 294907126713 652 298007449041 653 301135632648 654 304291951759 655 307476550737 656 310689706899 657 313931566535 658 317202410064 659 320502385743 660 323831777135 661 327190734425 662 330579544367 663 333998359152 664 337447468693 665 340927027185 666 344437327785 667 347978526695 668 351550920322 669 355154666911 670 358790066129 671 362457278305 672 366156606410 673 369888212817 674 373652403849 675 377449344004 676 381279342924 677 385142567230 678 389039329971 679 392969799894 680 396934293461 681 400932981582 682 404966184143 683 409034074260 684 413136975287 685 417275062506 686 421448662789 687 425657953665 688 429903265492 689 434184778045 690 438502825257 691 442857589153 692 447249407247 693 451678463853 694 456145100077 695 460649502565 696 465192016062 697 469772829505 698 474392291329 699 479050592846 700 483748086148 701 488484964921 702 493261585005 703 498078142465 704 502934996896 705 507832346781 706 512770555482 707 517749823945 708 522770519346 709 527832845053 710 532937172109 711 538083706389 712 543272822770 713 548504729634 714 553779805785 715 559098262117 716 564460481368 717 569866676985 718 575317235653 719 580812373417 720 586352480958 721 591937776878 722 597568655907 723 603245339292 724 608968225779 725 614737539260 726 620553682592 727 626416882317 728 632327545412 729 638285901110 730 644292360521 731 650347155617 732 656450701690 733 662603233410 734 668805170306 735 675056749835 736 681358395730 737 687710348235 738 694113035385 739 700566700217 740 707071775076 741 713628505835 742 720237329163 743 726898493817 744 733612440841 745 740379421835 746 747199882274 747 754074076692 748 761002454962 749 767985274553 750 775022989835 751 782115861218 752 789264347579 753 796468712313 754 803729418818 755 811046733524 756 818421124402 757 825852860875 758 833342415545 759 840890060921 760 848496274203 761 856161330987 762 863885713172 763 871669699449 764 879513776425 765 887418225931 766 895383539298 767 903410001547 768 911498108787 769 919648149187 770 927860623693 771 936135823717 772 944474255008 773 952876212224 774 961342206020 775 969872534307 776 978467712657 777 987128042280 778 995854043681 779 1004646021421 780 1013504500993 781 1022429790267 782 1031422419784 783 1040482700820 784 1049611168931 785 1058808138801 786 1068074151106 787 1077409523947 788 1086814803131 789 1096290310223 790 1105836596178 791 1115453986078 792 1125143036082 793 1134904074747 794 1144737663498 795 1154644134466 796 1164624054308 797 1174677758732 798 1184805819735 799 1195008576610 800 1205286606706 801 1215640252950 802 1226070098060 803 1236576488652 804 1247160012870 805 1257821020977 806 1268560106606 807 1279377623767 808 1290274171550 809 1301250107715 810 1312306036918 811 1323442320679 812 1334659569232 813 1345958147907 814 1357338672534 815 1368801512309 816 1380347288717 817 1391976374777 818 1403689397694 819 1415486734413 820 1427369017825 821 1439336628805 822 1451390206042 823 1463530134351 824 1475757058232 825 1488071366491 826 1500473709458 827 1512964479987 828 1525544334298 829 1538213669251 830 1550973147022 831 1563823168581 832 1576764402027 833 1589797252445 834 1602922393970 835 1616140235813 836 1629451458159 837 1642856474397 838 1656355970782 839 1669950364939 840 1683640349255 841 1697426345548 842 1711309052404 843 1725288895942 844 1739366580913 845 1753542537742 846 1767817477461 847 1782191834812 848 1796666327123 849 1811241393506 850 1825917757606 851 1840695862965 852 1855576439607 853 1870559935462 854 1885647087002 855 1900838346653 856 1916134457302 857 1931535875877 858 1947043351798 859 1962657346507 860 1978378615972 861 1994207626204 862 2010145139740 863 2026191627221 864 2042347857818 865 2058614306759 866 2074991749919 867 2091480667224 868 2108081841220 869 2124795756537 870 2141623202512 871 2158564668492 872 2175620950621 873 2192792543019 874 2210080248659 875 2227484566497 876 2245006306400 877 2262645972117 878 2280404380482 879 2298282040149 880 2316279774886 881 2334398098259 882 2352637841092 883 2370999521877 884 2389483978510 885 2408091734467 886 2426823634739 887 2445680207849 888 2464662305951 889 2483770462572 890 2503005537102 891 2522368068187 892 2541858922420 893 2561478643574 894 2581228105569 895 2601107857319 896 2621118780089 897 2641261427992 898 2661536689662 899 2681945124477 900 2702487628508 901 2723164766355 902 2743977441601 903 2764926224185 904 2786012025169 905 2807235419839 906 2828597326863 907 2850098326889 908 2871739346209 909 2893520970893 910 2915444134882 911 2937509429734 912 2959717797109 913 2982069834011 914 3004566489895 915 3027208367330 916 3049996423533 917 3072931266647 918 3096013861780 919 3119244822664 920 3142625122318 921 3166155380124 922 3189836577037 923 3213669338158 924 3237654652449 925 3261793150687 926 3286085829919 927 3310533326719 928 3335136646187 929 3359896430703 930 3384813693551 931 3409889082934 932 3435123620339 933 3460517959855 934 3486073131199 935 3511789794415 936 3537668987523 937 3563711376479 938 3589918007686 939 3616289553135 940 3642827067579 941 3669531229055 942 3696403100799 943 3723443366911 944 3750653099131 945 3778032987686 946 3805584112847 947 3833307171039 948 3861203251139 949 3889273055727 950 3917517682367 951 3945937839919 952 3974534634602 953 4003308781567 954 4032261395823 955 4061393198831 956 4090705314411 957 4120198470399 958 4149873799455 959 4179732035862 960 4209774321196 961 4240001396144 962 4270414411281 963 4301014113826 964 4331801663320 965 4362777813526 966 4393943733089 967 4425300182334 968 4456848339033 969 4488588970140 970 4520523262583 971 4552651990019 972 4584976348609 973 4617497118671 974 4650215505683 975 4683132296753 976 4716248706645 977 4749565529269 978 4783083988815 979 4816804886015 980 4850729454508 981 4884858501916 982 4919193271357 983 4953734577419 984 4988483672778 985 5023441378945 986 5058608958240 987 5093987239229 988 5129577493844 989 5165380557719 990 5201397712541 991 5237629801032 992 5274078114658 993 5310743503299 994 5347627268231 995 5384730266569 996 5422053809479 997 5459598761269 998 5497366443083 999 5535357726555 1000 5573573942776