0 0 1 1 2 3 3 7 4 15 5 31 6 62 7 119 8 218 9 381 10 637 11 1023 12 1585 13 2379 14 3472 15 4943 16 6884 17 9401 18 12615 19 16663 20 21699 21 27895 22 35442 23 44551 24 55454 25 68405 26 83681 27 101583 28 122437 29 146595 30 174436 31 206367 32 242824 33 284273 34 331211 35 384167 36 443703 37 510415 38 584934 39 667927 40 760098 41 862189 42 974981 43 1099295 44 1235993 45 1385979 46 1550200 47 1729647 48 1925356 49 2138409 50 2369935 51 2621111 52 2893163 53 3187367 54 3505050 55 3847591 56 4216422 57 4613029 58 5038953 59 5495791 60 5985197 61 6508883 62 7068620 63 7666239 64 8303632 65 8982753 66 9705619 67 10474311 68 11290975 69 12157823 70 13077134 71 14051255 72 15082602 73 16173661 74 17326989 75 18545215 76 19831041 77 21187243 78 22616672 79 24122255 80 25706996 81 27373977 82 29126359 83 30967383 84 32900371 85 34928727 86 37055938 87 39285575 88 41621294 89 44066837 90 46626033 91 49302799 92 52101141 93 55025155 94 58079028 95 61267039 96 64593560 97 68063057 98 71680091 99 75449319 100 79375495 101 83463471 102 87718198 103 92144727 104 96748210 105 101533901 106 106507157 107 111673439 108 117038313 109 122607451 110 128386632 111 134381743 112 140598780 113 147043849 114 153723167 115 160643063 116 167809979 117 175230471 118 182911210 119 190858983 120 199080694 121 207583365 122 216374137 123 225460271 124 234849149 125 244548275 126 254565276 127 264907903 128 275584032 129 286601665 130 297968931 131 309694087 132 321785519 133 334251743 134 347101406 135 360343287 136 373986298 137 388039485 138 402512029 139 417413247 140 432752593 141 448539659 142 464784176 143 481496015 144 498685188 145 516361849 146 534536295 147 553218967 148 572420451 149 592151479 150 612422930 151 633245831 152 654631358 153 676590837 154 699135745 155 722277711 156 746028517 157 770400099 158 795404548 159 821054111 160 847361192 161 874338353 162 901998315 163 930353959 164 959418327 165 989204623 166 1019726214 167 1050996631 168 1083029570 169 1115838893 170 1149438629 171 1183842975 172 1219066297 173 1255123131 174 1292028184 175 1329796335 176 1368442636 177 1407982313 178 1448430767 179 1489803575 180 1532116491 181 1575385447 182 1619626554 183 1664856103 184 1711090566 185 1758346597 186 1806641033 187 1855990895 188 1906413389 189 1957925907 190 2010546028 191 2064291519 192 2119180336 193 2175230625 194 2232460723 195 2290889159 196 2350534655 197 2411416127 198 2473552686 199 2536963639 200 2601668490 201 2667686941 202 2735038893 203 2803744447 204 2873823905 205 2945297771 206 3018186752 207 3092511759 208 3168293908 209 3245554521 210 3324315127 211 3404597463 212 3486423475 213 3569815319 214 3654795362 215 3741386183 216 3829610574 217 3919491541 218 4011052305 219 4104316303 220 4199307189 221 4296048835 222 4394565332 223 4494880991 224 4597020344 225 4701008145 226 4806869371 227 4914629223 228 5024313127 229 5135946735 230 5249555926 231 5365166807 232 5482805714 233 5602499213 234 5724274101 235 5848157407 236 5974176393 237 6102358555 238 6232731624 239 6365323567 240 6500162588 241 6637277129 242 6776695871 243 6918447735 244 7062561883 245 7209067719 246 7357994890 247 7509373287 248 7663233046 249 7819604549 250 7978518425 251 8140005551 252 8304097053 253 8470824307 254 8640218940 255 8812312831 256 8987138112 257 9164727169 258 9345112643 259 9528327431 260 9714404687 261 9903377823 262 10095280510 263 10290146679 264 10488010522 265 10688906493 266 10892869309 267 11099933951 268 11310135665 269 11523509963 270 11740092624 271 11959919695 272 12183027492 273 12409452601 274 12639231879 275 12872402455 276 13109001731 277 13349067383 278 13592637362 279 13839749895 280 14090443486 281 14344756917 282 14602729249 283 14864399823 284 15129808261 285 15398994467 286 15671998628 287 15948861215 288 16229622984 289 16514324977 290 16803008523 291 17095715239 292 17392487031 293 17693366095 294 17998394918 295 18307616279 296 18621073250 297 18938809197 298 19260867781 299 19587292959 300 19918128985 301 20253420411 302 20593212088 303 20937549167 304 21286477100 305 21640041641 306 21998288847 307 22361265079 308 22729017003 309 23101591591 310 23479036122 311 23861398183 312 24248725670 313 24641066789 314 25038470057 315 25440984303 316 25848658669 317 26261542611 318 26679685900 319 27103138623 320 27531951184 321 27966174305 322 28405859027 323 28851056711 324 29301819039 325 29758198015 326 30220245966 327 30688015543 328 31161559722 329 31640931805 330 32126185421 331 32617374527 332 33114553409 333 33617776683 334 34127099296 335 34642576527 336 35164263988 337 35692217625 338 36226493719 339 36767148887 340 37314240083 341 37867824599 342 38427960066 343 38994704455 344 39568116078 345 40148253589 346 40735175985 347 41328942607 348 41929613141 349 42537247619 350 43151906420 351 43773650271 352 44402540248 353 45038637777 354 45682004635 355 46332702951 356 46990795207 357 47656344239 358 48329413238 359 49010065751 360 49698365682 361 50394377293 362 51098165205 363 51809794399 364 52529330217 365 53256838363 366 53992384904 367 54736036271 368 55487859260 369 56247921033 370 57016289119 371 57793031415 372 58578216187 373 59371912071 374 60174188074 375 60985113575 376 61804758326 377 62633192453 378 63470486457 379 64316711215 380 65171937981 381 66036238387 382 66909684444 383 67792348543 384 68684303456 385 69585622337 386 70496378723 387 71416646535 388 72346500079 389 73286014047 390 74235263518 391 75194323959 392 76163271226 393 77142181565 394 78131131613 395 79130198399 396 80139459345 397 81158992267 398 82188875376 399 83229187279 400 84280006980 401 85341413881 402 86413487783 403 87496308887 404 88589957795 405 89694515511 406 90810063442 407 91936683399 408 93074457598 409 94223468661 410 95383799617 411 96555533903 412 97738755365 413 98933548259 414 100139997252 415 101358187423 416 102588204264 417 103830133681 418 105084061995 419 106350075943 420 107628262679 421 108918709775 422 110221505222 423 111536737431 424 112864495234 425 114204867885 426 115557945061 427 116923816863 428 118302573817 429 119694306875 430 121099107416 431 122517067247 432 123948278604 433 125392834153 434 126850826991 435 128322350647 436 129807499083 437 131306366695 438 132819048314 439 134345639207 440 135886235078 441 137440932069 442 139009826761 443 140593016175 444 142190597773 445 143802669459 446 145429329580 447 147070676927 448 148726810736 449 150397830689 450 152083836915 451 153784929991 452 155501210943 453 157232781247 454 158979742830 455 160742198071 456 162520249802 457 164314001309 458 166123556333 459 167949019071 460 169790494177 461 171648086763 462 173521902400 463 175412047119 464 177318627412 465 179241750233 466 181181522999 467 183138053591 468 185111450355 469 187101822103 470 189109278114 471 191133928135 472 193175882382 473 195235251541 474 197312146769 475 199406679695 476 201518962421 477 203649107523 478 205797228052 479 207963437535 480 210147849976 481 212350579857 482 214571742139 483 216811452263 484 219069826151 485 221346980207 486 223643031318 487 225958096855 488 228292294674 489 230645743117 490 233018561013 491 235410867679 492 237822782921 493 240254427035 494 242705920808 495 245177385519 496 247668942940 497 250180715337 498 252712825471 499 255265396599 500 257838552475 501 260432417351 502 263047115978 503 265682773607 504 268339515990 505 271017469381 506 273716760537 507 276437516719 508 279179865693 509 281943935731 510 284729855612 511 287537754623 512 290367762560 513 293220009729 514 296094626947 515 298991745543 516 301911497359 517 304854014751 518 307819430590 519 310807878263 520 313819491674 521 316854405245 522 319912753917 523 322994673151 524 326100298929 525 329229767755 526 332383216656 527 335560783183 528 338762605412 529 341988821945 530 345239571911 531 348514994967 532 351815231299 533 355140421623 534 358490707186 535 361866229767 536 365267131678 537 368693555765 538 372145645409 539 375623544527 540 379127397573 541 382657349539 542 386213545956 543 389796132895 544 393405256968 545 397041065329 546 400703705675 547 404393326247 548 408110075831 549 411854103759 550 415625559910 551 419424594711 552 423251359138 553 427106004717 554 430988683525 555 434899548191 556 438838751897 557 442806448379 558 446802791928 559 450827937391 560 454882040172 561 458965256233 562 463077742095 563 467219654839 564 471391152107 565 475592392103 566 479823533594 567 484084735911 568 488376158950 569 492697963173 570 497050309609 571 501433359855 572 505847276077 573 510292221011 574 514768357964 575 519275850815 576 523814864016 577 528385562593 578 532988112147 579 537622678855 580 542289429471 581 546988531327 582 551720152334 583 556484460983 584 561281626346 585 566111818077 586 570975206413 587 575871962175 588 580802256769 589 585766262187 590 590764151008 591 595796096399 592 600862272116 593 605962852505 594 611098012503 595 616267927639 596 621472774035 597 626712728407 598 631987968066 599 637298670919 600 642645015470 601 648027180821 602 653445346673 603 658899693327 604 664390401685 605 669917653251 606 675481630132 607 681082515039 608 686720491288 609 692395742801 610 698108454107 611 703858810343 612 709646997255 613 715473201199 614 721337609142 615 727240408663 616 733181787954 617 739161935821 618 745181041685 619 751239295583 620 757336888169 621 763474010715 622 769650855112 623 775867613871 624 782124480124 625 788421647625 626 794759310751 627 801137664503 628 807556904507 629 814017227015 630 820518828906 631 827061907687 632 833646661494 633 840273289093 634 846941989881 635 853652963887 636 860406411773 637 867202534835 638 874041535004 639 880923614847 640 887848977568 641 894817827009 642 901830367651 643 908886804615 644 915987343663 645 923132191199 646 930321554270 647 937555640567 648 944834658426 649 952158816829 650 959528325405 651 966943394431 652 974404234833 653 981911058187 654 989464076720 655 997063503311 656 1004709551492 657 1012402435449 658 1020142370023 659 1027929570711 660 1035764253667 661 1043646635703 662 1051576934290 663 1059555367559 664 1067582154302 665 1075657513973 666 1083781666689 667 1091954833231 668 1100177235045 669 1108449094243 670 1116770633604 671 1125142076575 672 1133563647272 673 1142035570481 674 1150558071659 675 1159131376935 676 1167755713111 677 1176431307663 678 1185158388742 679 1193937185175 680 1202767926466 681 1211650842797 682 1220586165029 683 1229574124703 684 1238614954041 685 1247708885947 686 1256856154008 687 1266056992495 688 1275311636364 689 1284620321257 690 1293983283503 691 1303400760119 692 1312872988811 693 1322400207975 694 1331982656698 695 1341620574759 696 1351314202630 697 1361063781477 698 1370869553161 699 1380731760239 700 1390650645965 701 1400626454291 702 1410659429868 703 1420749818047 704 1430897864880 705 1441103817121 706 1451367922227 707 1461690428359 708 1472071584383 709 1482511639871 710 1493010845102 711 1503569451063 712 1514187709450 713 1524865872669 714 1535604193837 715 1546402926783 716 1557262326049 717 1568182646891 718 1579164145280 719 1590207077903 720 1601311702164 721 1612478276185 722 1623707058807 723 1634998309591 724 1646352288819 725 1657769257495 726 1669249477346 727 1680793210823 728 1692400721102 729 1704072272085 730 1715808128401 731 1727608555407 732 1739473819189 733 1751404186563 734 1763399925076 735 1775461303007 736 1787588589368 737 1799782053905 738 1812041967099 739 1824368600167 740 1836762225063 741 1849223114479 742 1861751541846 743 1874347781335 744 1887012107858 745 1899744797069 746 1912546125365 747 1925416369887 748 1938355808521 749 1951364719899 750 1964443383400 751 1977592079151 752 1990811088028 753 2004100691657 754 2017461172415 755 2030892813431 756 2044395898587 757 2057970712519 758 2071617540618 759 2085336669031 760 2099128384662 761 2112992975173 762 2126930728985 763 2140941935279 764 2155026883997 765 2169185865843 766 2183419172284 767 2197727095551 768 2212109928640 769 2226567965313 770 2241101500099 771 2255710828295 772 2270396245967 773 2285158049951 774 2299996537854 775 2314912008055 776 2329904759706 777 2344975092733 778 2360123307837 779 2375349706495 780 2390654590961 781 2406038264267 782 2421501030224 783 2437043193423 784 2452665059236 785 2468366933817 786 2484149124103 787 2500011937815 788 2515955683459 789 2531980670327 790 2548087208498 791 2564275608839 792 2580546183006 793 2596899243445 794 2613335103393 795 2629854076879 796 2646456478725 797 2663142624547 798 2679912830756 799 2696767414559 800 2713706693960 801 2730730987761 802 2747840615563 803 2765035897767 804 2782317155575 805 2799684710991 806 2817138886822 807 2834680006679 808 2852308394978 809 2870024376941 810 2887828278597 811 2905720426783 812 2923701149145 813 2941770774139 814 2959929631032 815 2978178049903 816 2996516361644 817 3014944897961 818 3033463991375 819 3052073975223 820 3070775183659 821 3089567951655 822 3108452615002 823 3127429510311 824 3146498975014 825 3165661347365 826 3184916966441 827 3204266172143 828 3223709305197 829 3243246707155 830 3262878720396 831 3282605688127 832 3302427954384 833 3322345864033 834 3342359762771 835 3362469997127 836 3382676914463 837 3402980862975 838 3423382191694 839 3443881250487 840 3464478390058 841 3485173961949 842 3505968318541 843 3526861813055 844 3547854799553 845 3568947632939 846 3590140668960 847 3611434264207 848 3632828776116 849 3654324562969 850 3675921983895 851 3697621398871 852 3719423168723 853 3741327655127 854 3763335220610 855 3785446228551 856 3807661043182 857 3829980029589 858 3852403553713 859 3874931982351 860 3897565683157 861 3920305024643 862 3943150376180 863 3966102107999 864 3989160591192 865 4012326197713 866 4035599300379 867 4058980272871 868 4082469489735 869 4106067326383 870 4129774159094 871 4153590365015 872 4177516322162 873 4201552409421 874 4225699006549 875 4249956494175 876 4274325253801 877 4298805667803 878 4323398119432 879 4348102992815 880 4372920672956 881 4397851545737 882 4422895997919 883 4448054417143 884 4473327191931 885 4498714711687 886 4524217366698 887 4549835548135 888 4575569648054 889 4601420059397 890 4627387175993 891 4653471392559 892 4679673104701 893 4705992708915 894 4732430602588 895 4758987183999 896 4785662852320 897 4812458007617 898 4839373050851 899 4866408383879 900 4893564409455 901 4920841531231 902 4948240153758 903 4975760682487 904 5003403523770 905 5031169084861 906 5059057773917 907 5087069999999 908 5115206173073 909 5143466704011 910 5171852004592 911 5200362487503 912 5228998566340 913 5257760655609 914 5286649170727 915 5315664528023 916 5344807144739 917 5374077439031 918 5403475829970 919 5433002737543 920 5462658582654 921 5492443787125 922 5522358773697 923 5552403966031 924 5582579788709 925 5612886667235 926 5643325028036 927 5673895298463 928 5704597906792 929 5735433282225 930 5766401854891 931 5797504055847 932 5828740317079 933 5860111071503 934 5891616752966 935 5923257796247 936 5955034637058 937 5986947712045 938 6018997458789 939 6051184315807 940 6083508722553 941 6115971119419 942 6148571947736 943 6181311649775 944 6214190668748 945 6247209448809 946 6280368435055 947 6313668073527 948 6347108811211 949 6380691096039 950 6414415376890 951 6448282103591 952 6482291726918 953 6516444698597 954 6550741471305 955 6585182498671 956 6619768235277 957 6654499136659 958 6689375659308 959 6724398260671 960 6759567399152 961 6794883534113 962 6830347125875 963 6865958635719 964 6901718525887 965 6937627259583 966 6973685300974 967 7009893115191 968 7046251168330 969 7082759927453 970 7119419860589 971 7156231436735 972 7193195125857 973 7230311398891 974 7267580727744 975 7305003585295 976 7342580445396 977 7380311782873 978 7418198073527 979 7456239794135 980 7494437422451 981 7532791437207 982 7571302318114 983 7609970545863 984 7648796602126 985 7687780969557 986 7726924131793 987 7766226573455 988 7805688780149 989 7845311238467 990 7885094435988 991 7925038861279 992 7965145003896 993 8005413354385 994 8045844404283 995 8086438646119 996 8127196573415 997 8168118680687 998 8209205463446 999 8250457418199 1000 8291875042450