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 1802 29 2105 30 2464 31 2860 32 3324 33 3835 34 4428 35 5081 36 5834 37 6659 38 7604 39 8640 40 9819 41 11107 42 12566 43 14158 44 15951 45 17904 46 20093 47 22474 48 25133 49 28018 50 31226 51 34704 52 38557 53 42725 54 47328 55 52301 56 57775 57 63679 58 70158 59 77137 60 84776 61 92990 62 101956 63 111588 64 122075 65 133322 66 145541 67 158630 68 172818 69 187996 70 204414 71 221957 72 240897 73 261108 74 282886 75 306103 76 331075 77 357663 78 386214 79 416581 80 449136 81 483724 82 520746 83 560041 84 602041 85 646571 86 694097 87 744442 88 798101 89 854884 90 915328 91 979235 92 1047175 93 1118942 94 1195146 95 1275574 96 1360878 97 1450830 98 1546128 99 1646541 100 1752807 101 1864682 102 1982958 103 2107383 104 2238794 105 2376931 106 2522683 107 2675783 108 2837176 109 3006579 110 3184996 111 3372143 112 3569077 113 3775500 114 3992538 115 4219886 116 4458729 117 4708754 118 4971214 119 5245790 120 5533805 121 5834925 122 6150548 123 6480341 124 6825770 125 7186489 126 7564051 127 7958103 128 8370274 129 8800205 130 9249610 131 9718126 132 10207555 133 10717521 134 11249918 135 11804374 136 12382870 137 12985022 138 13612918 139 14266170 140 14946961 141 15654899 142 16392272 143 17158688 144 17956543 145 18785434 146 19647871 147 20543459 148 21474815 149 22441535 150 23446366 151 24488904 152 25572012 153 26695287 154 27861720 155 29070911 156 30325983 157 31626529 158 32975810 159 34373432 160 35822787 161 37323477 162 38879048 163 40489108 164 42157344 165 43883370 166 45671027 167 47519938 168 49434103 169 51413142 170 53461220 171 55577978 172 57767738 173 60030143 174 62369698 175 64786059 176 67283899 177 69862887 178 72527880 179 75278563 180 78119981 181 81051824 182 84079332 183 87202224 184 90425927 185 93750170 186 97180595 187 100716952 188 104365083 189 108124760 190 112002040 191 115996721 192 120115081 193 124356932 194 128728780 195 133230477 196 137868750 197 142643469 198 147561612 199 152623081 200 157835088 201 163197568 202 168717984 203 174396309 204 180240262 205 186249841 206 192433031 207 198789882 208 205328637 209 212049376 210 218960632 211 226062529 212 233363872 213 240864832 214 248574504 215 256493110 216 264630042 217 272985560 218 281569362 219 290381775 220 299432796 221 308722796 222 318262104 223 328051151 224 338100580 225 348410883 226 358993037 227 369847601 228 380985893 229 392408525 230 404127166 231 416142513 232 428466577 233 441100116 234 454055520 235 467333624 236 480947178 237 494897096 238 509196510 239 523846418 240 538860341 241 554239349 242 569997362 243 586135555 244 602668239 245 619596669 246 636935585 247 654686339 248 672864082 249 691470265 250 710520472 251 730016260 252 749973654 253 770394303 254 791294684 255 812676574 256 834556894 257 856937522 258 879835864 259 903253918 260 927209554 261 951704893 262 976758294 263 1002372008 264 1028564891 265 1055339310 266 1082714631 267 1110693373 268 1139295404 269 1168523369 270 1198397680 271 1228921128 272 1260114648 273 1291981181 274 1324542210 275 1357800833 276 1391779092 277 1426480227 278 1461926852 279 1498122388 280 1535090013 281 1572833301 282 1611376038 283 1650721974 284 1690895481 285 1731900488 286 1773761981 287 1816484076 288 1860092383 289 1904591190 290 1950006746 291 1996343552 292 2043628487 293 2091866237 294 2141084358 295 2191287743 296 2242504603 297 2294740043 298 2348022958 299 2402358673 300 2457776778 301 2514282804 302 2571907050 303 2630655296 304 2690558543 305 2751622790 306 2813879789 307 2877335782 308 2942023250 309 3007948682 310 3075145318 311 3143619905 312 3213406453 313 3284511952 314 3356971198 315 3430791469 316 3506008339 317 3582629343 318 3660690886 319 3740200785 320 3821196252 321 3903685392 322 3987706256 323 4073267247 324 4160407267 325 4249135003 326 4339490225 327 4431481950 328 4525150809 329 4620506118 330 4717589422 331 4816410363 332 4917011377 333 5019402438 334 5123626906 335 5229695098 336 5337651312 337 5447506192 338 5559304992 339 5673058733 340 5788813617 341 5906581010 342 6026408118 343 6148306681 344 6272324884 345 6398474847 346 6526805771 347 6657330167 348 6790098266 349 6925122955 350 7062455514 351 7202109257 352 7344136505 353 7488550968 354 7635406066 355 7784715934 356 7936535067 357 8090878032 358 8247800436 359 8407317290 360 8569485329 361 8734319993 362 8901879164 363 9072178765 364 9245277818 365 9421192695 366 9599983619 367 9781667443 368 9966305566 369 10153915329 370 10344559346 371 10538255460 372 10735067515 373 10935013841 374 11138159534 375 11344523466 376 11554171978 377 11767124450 378 11983448532 379 12203164144 380 12426340219 381 12652997227 382 12883205424 383 13116985844 384 13354410083 385 13595499724 386 13840327725 387 14088916275 388 14341339689 389 14597620727 390 14857835126 391 15122006252 392 15390211238 393 15662474065 394 15938873304 395 16219433567 396 16504234881 397 16793302473 398 17086717850 399 17384506914 400 17686752645 401 17993481585 402 18304778256 403 18620669876 404 18941242482 405 19266523978 406 19596601961 407 19931505036 408 20271322379 409 20616083282 410 20965878524 411 21320738146 412 21680754524 413 22045958413 414 22416443856 415 22792242359 416 23173449607 417 23560097867 418 23952284512 419 24350042587 420 24753471173 421 25162604078 422 25577542116 423 25998319924 424 26425040043 425 26857737902 426 27296517843 427 27741416126 428 28192538867 429 28649923168 430 29113676968 431 29583838229 432 30060516733 433 30543751288 434 31033653546 435 31530263227 436 32033693848 437 32543986005 438 33061255156 439 33585542813 440 34116966348 441 34655568202 442 35201467710 443 35754708261 444 36315411176 445 36883620777 446 37459460399 447 38042975366 448 38634291023 449 39233453658 450 39840590704 451 40455749457 452 41079059410 453 41710568880 454 42350409472 455 42998630544 456 43655365836 457 44320665732 458 44994666138 459 45677418535 460 46369060990 461 47069646044 462 47779314006 463 48498118521 464 49226202112 465 49963619543 466 50710515605 467 51466946201 468 52233058415 469 53008909275 470 53794648188 471 54590333381 472 55396116581 473 56212057176 474 57038309296 475 57874933536 476 58722086402 477 59579829710 478 60448322398 479 61327627526 480 62217906489 481 63119223577 482 64031742674 483 64955529377 484 65890750055 485 66837471573 486 67795862873 487 68765992135 488 69748030846 489 70742048517 490 71748219238 491 72766613874 492 73797409144 493 74840677255 494 75896597588 495 76965243770 496 78046797842 497 79141334812 498 80249039470 499 81369988254 500 82504368676 501 83652258621 502 84813848382 503 85989217316 504 87178558525 505 88381952824 506 89599596159 507 90831570885 508 92078075790 509 93339194729 510 94615129424 511 95905965282 512 97211906930 513 98533041345 514 99869576122 515 101221599833 516 102589323070 517 103972835987 518 105372352210 519 106787963558 520 108219886689 521 109668215049 522 111133168422 523 112614841934 524 114113458467 525 115629114846 526 117162037115 527 118712323824 528 120280204211 529 121865778538 530 123469279274 531 125090808480 532 126730601855 533 128388763219 534 130065531598 535 131761012627 536 133475448631 537 135208947079 538 136961753662 539 138733977711 540 140525868314 541 142337536652 542 144169235250 543 146021077228 544 147893318547 545 149786074226 546 151699603763 547 153634024132 548 155589598340 549 157566445338 550 159564831710 551 161584878413 552 163626855641 553 165690886346 554 167777244372 555 169886054757 556 172017594997 557 174171992175 558 176349527542 559 178550330285 560 180774685382 561 183022724146 562 185294735352 563 187590852471 564 189911368109 565 192256417883 566 194626298273 567 197021147136 568 199441264827 569 201886791402 570 204358031198 571 206855126531 572 209378385691 573 211927953278 574 214504141608 575 217107097596 576 219737137620 577 222394410900 578 225079237920 579 227791770301 580 230532332635 581 233301078904 582 236098337916 583 238924266077 584 241779196384 585 244663287691 586 247576877259 587 250520126423 588 253493376746 589 256496792033 590 259530718194 591 262595321605 592 265690952525 593 268817779860 594 271976158330 595 275166259436 596 278388442331 597 281642881136 598 284929939516 599 288249794246 600 291602813541 601 294989176821 602 298409256898 603 301863235939 604 305351491356 605 308874208023 606 312431768067 607 316024359135 608 319652368042 609 323315985235 610 327015602296 611 330751412508 612 334523812261 613 338332997665 614 342179369966 615 346063128206 616 349984678492 617 353944222756 618 357942172084 619 361978731368 620 366054316645 621 370169135795 622 374323609888 623 378517949830 624 382752581765 625 387027719616 626 391343794653 627 395701023923 628 400099843827 629 404540474495 630 409023357580 631 413548716366 632 418116997730 633 422728428141 634 427383459784 635 432082322351 636 436825473379 637 441613145775 638 446445802480 639 451323679726 640 456247245865 641 461216740413 642 466232637256 643 471295179268 644 476404845842 645 481561883240 646 486766776449 647 492019775160 648 497321369999 649 502671814078 650 508071603716 651 513520995560 652 519020491628 653 524570352061 654 530171084704 655 535822953267 656 541526471395 657 547281906399 658 553089777814 659 558950356593 660 564864168207 661 570831487246 662 576852845172 663 582928520328 664 589059050175 665 595244716768 666 601486063697 667 607783376806 668 614137205789 669 620547840312 670 627015836264 671 633541487177 672 640125355183 673 646767737674 674 653469203082 675 660230052779 676 667050861506 677 673931934573 678 680873853164 679 687876926607 680 694941742502 681 702068614230 682 709258135902 683 716510624997 684 723826682186 685 731206629041 686 738651072853 687 746160339408 688 753735042627 689 761375512470 690 769082369624 691 776855948305 692 784696875940 693 792605491038 694 800582427862 695 808628029260 696 816742936384 697 824927496416 698 833182357458 699 841507871151 700 849904692558 701 858373177738 702 866913988854 703 875527486469 704 884214339820 705 892974914011 706 901809885453 707 910719623839 708 919704812807 709 928765826635 710 937903356252 711 947117780649 712 956409798057 713 965779792140 714 975228468574 715 984756215782 716 994363746860 717 1004051455030 718 1013820060910 719 1023669962570 720 1033601888205 721 1043616240731 722 1053713755984 723 1063894841857 724 1074160241841 725 1084510368765 726 1094945973921 727 1105467475163 728 1116075631560 729 1126770866031 730 1137553945526 731 1148425298082 732 1159385698586 733 1170435580191 734 1181575725788 735 1192806573780 736 1204128915076 737 1215543193288 738 1227050207494 739 1238650406606 740 1250344597846 741 1262133235469 742 1274017134948 743 1285996755934 744 1298072922209 745 1310246098820 746 1322517117927 747 1334886450109 748 1347354935920 749 1359923051431 750 1372591645742 751 1385361200510 752 1398232573358 753 1411206251573 754 1424283101410 755 1437463615841 756 1450748669814 757 1464138761985 758 1477634776066 759 1491237216538 760 1504946975893 761 1518764564397 762 1532690883478 763 1546726449284 764 1560872172155 765 1575128574166 766 1589496574683 767 1603976701764 768 1618569883863 769 1633276655022 770 1648097952856 771 1663034317534 772 1678086695849 773 1693255634059 774 1708542088294 775 1723946610999 776 1739470167619 777 1755113316833 778 1770877033516 779 1786761882639 780 1802768848572 781 1818898502580 782 1835151838602 783 1851529434344 784 1868032293333 785 1884660999676 786 1901416566651 787 1918299584868 788 1935311077334 789 1952451641210 790 1969722309350 791 1987123685527 792 2004656812507 793 2022322300678 794 2040121202796 795 2058054136013 796 2076122163095 797 2094325907919 798 2112666443428 799 2131144400327 800 2149760861714 801 2168516465174 802 2187412304080 803 2206449022959 804 2225627725527 805 2244949063257 806 2264414150287 807 2284023645188 808 2303778672543 809 2323679897982 810 2343728456702 811 2363925021499 812 2384270738163 813 2404766286708 814 2425412823640 815 2446211036256 816 2467162091848 817 2488266685000 818 2509525993872 819 2530940720491 820 2552512053907 821 2574240703552 822 2596127869540 823 2618174268817 824 2640381112540 825 2662749125223 826 2685279529193 827 2707973056597 828 2730830941004 829 2753853922201 830 2777043245082 831 2800399657233 832 2823924414897 833 2847618273422 834 2871482500576 835 2895517859580 836 2919725629709 837 2944106582112 838 2968662007700 839 2993392685618 840 3018299918487 841 3043384493455 842 3068647724938 843 3094090408251 844 3119713869630 845 3145518912519 846 3171506875155 847 3197678569225 848 3224035344948 849 3250578022311 850 3277307963648 851 3304225997316 852 3331333497839 853 3358631301953 854 3386120796460 855 3413802826640 856 3441678791600 857 3469749545128 858 3498016498820 859 3526480515088 860 3555143017999 861 3584004878649 862 3613067533710 863 3642331863034 864 3671799315977 865 3701470781156 866 3731347720701 867 3761431032163 868 3791722190475 869 3822222102085 870 3852932254916 871 3883853564434 872 3914987531534 873 3946335080761 874 3977897726120 875 4009676401309 876 4041672633523 877 4073887365623 878 4106322138088 879 4138977903114 880 4171856214493 881 4204958033721 882 4238284928094 883 4271837868530 884 4305618435812 885 4339627610344 886 4373866986537 887 4408337554356 888 4443040921923 889 4477978088776 890 4513150676842 891 4548559695408 892 4584206780238 893 4620092950333 894 4656219855488 895 4692588524543 896 4729200621309 897 4766057184529 898 4803159892174 899 4840509792969 900 4878108579129 901 4915957309374 902 4954057690260 903 4992410790682 904 5031018331569 905 5069881391956 906 5109001707345 907 5148380367038 908 5188019121095 909 5227919069152 910 5268081975974 911 5308508951611 912 5349201775619 913 5390161568478 914 5431390124634 915 5472888575179 916 5514658729484 917 5556701729219 918 5599019398882 919 5641612890851 920 5684484044738 921 5727634023698 922 5771064682606 923 5814777195477 924 5858773432538 925 5903054578679 926 5947622519581 927 5992478451196 928 6037624274695 929 6083061197058 930 6128791135152 931 6174815307119 932 6221135645508 933 6267753379694 934 6314670458062 935 6361888121304 936 6409408333732 937 6457232347372 938 6505362142568 939 6553798982869 940 6602544864688 941 6651601063066 942 6700969590694 943 6750651734241 944 6800649522664 945 6850964254333 946 6901597974627 947 6952551993703 948 7003828373457 949 7055428435851 950 7107354259404 951 7159607178077 952 7212189287051 953 7265101932254 954 7318347225742 955 7371926525550 956 7425841960598 957 7480094901102 958 7534687493006 959 7589621118796 960 7644897941535 961 7700519355999 962 7756487542480 963 7812803908241 964 7869470650843 965 7926489190005 966 7983861740775 967 8041589735469 968 8099675406612 969 8158120199195 970 8216926363382 971 8276095356930 972 8335629447740 973 8395530106357 974 8455799618530 975 8516439467792 976 8577451957784 977 8638838584996 978 8700601671182 979 8762742725934 980 8825264089110 981 8888167283483 982 8951454667180 983 9015127776250 984 9079188987189 985 9143639849344 986 9208482757695 987 9273719275091 988 9339351815040 989 9405381953863 990 9471812123822 991 9538643914858 992 9605879777978 993 9673521316825 994 9741571001320 995 9810030448903 996 9878902148512 997 9948187731409 998 10017889705666 999 10088009716574 1000 10158550291385