0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 42 11 55 12 75 13 97 14 128 15 164 16 212 17 267 18 340 19 423 20 530 21 653 22 807 23 984 24 1204 25 1455 26 1761 27 2112 28 2534 29 3015 30 3590 31 4242 32 5013 33 5888 34 6912 35 8070 36 9418 37 10936 38 12690 39 14663 40 16928 41 19466 42 22367 43 25608 44 29292 45 33401 46 38047 47 43214 48 49037 49 55494 50 62740 51 70760 52 79725 53 89623 54 100654 55 112804 56 126299 57 141136 58 157564 59 175586 60 195491 61 217280 62 241279 63 267507 64 296320 65 327748 66 362198 67 399705 68 440725 69 485315 70 533975 71 586779 72 644295 73 706607 74 774345 75 847628 76 927143 77 1013036 78 1106080 79 1206440 80 1314972 81 1431884 82 1558110 83 1693899 84 1840292 85 1997569 86 2166875 87 2348553 88 2543849 89 2753159 90 2977866 91 3218412 92 3476314 93 3752096 94 4047402 95 4362833 96 4700201 97 5060174 98 5444732 99 5854649 100 6292069 101 6757864 102 7254388 103 7782608 104 8345084 105 8942920 106 9578879 107 10254199 108 10971900 109 11733342 110 12541802 111 13398814 112 14307910 113 15270794 114 16291308 115 17371322 116 18514989 117 19724399 118 21004018 119 22356152 120 23785645 121 25295011 122 26889475 123 28571827 124 30347671 125 32220069 126 34195076 127 36276024 128 38469427 129 40778952 130 43211575 131 45771300 132 48465645 133 51298950 134 54279279 135 57411388 136 60703893 137 64161965 138 67794864 139 71608176 140 75611815 141 79811865 142 84218903 143 88839522 144 93685056 145 98762607 146 104084280 147 109657784 148 115496010 149 121607276 150 128005367 151 134699218 152 141703526 153 149027949 154 156688108 155 164694398 156 173063483 157 181806502 158 190941187 159 200479536 160 210440370 161 220836558 162 231688140 163 243008877 164 254820051 165 267136439 166 279980591 167 293368323 168 307323599 169 321863286 170 337012795 171 352790186 172 369222348 173 386328561 174 404137344 175 422669224 176 441954389 177 462014762 178 482882242 179 504580179 180 527142353 181 550593568 182 574969531 183 600296674 184 626612672 185 653945620 186 682335346 187 711811649 188 742416568 189 774181780 190 807151588 191 841359596 192 876852573 193 913666096 194 951849458 195 991440410 196 1032490831 197 1075040697 198 1119144696 199 1164845082 200 1212199424 201 1261252465 202 1312064727 203 1364683514 204 1419172533 205 1475581709 206 1533978017 207 1594414239 208 1656960705 209 1721673120 210 1788625426 211 1857876328 212 1929503474 213 2003568823 214 2080153818 215 2159323761 216 2241164168 217 2325743765 218 2413152252 219 2503462052 220 2596767156 221 2693143777 222 2792690497 223 2895487426 224 3001637852 225 3111226073 226 3224360204 227 3341128846 228 3461645269 229 3586002480 230 3714319039 231 3846692681 232 3983247392 233 4124085762 234 4269337546 235 4419110319 236 4573539756 237 4732738757 238 4896849074 239 5065989072 240 5240306955 241 5419926691 242 5605003104 243 5795666145 244 5992077422 245 6194373023 246 6402721743 247 6617265971 248 6838181881 249 7065618551 250 7299759723 251 7540761345 252 7788815159 253 8044084163 254 8306768300 255 8577038050 256 8855101766 257 9141137602 258 9435362790 259 9737963356 260 10049165639 261 10369163991 262 10698194089 263 11036458839 264 11384203747 265 11741640489 266 12109024651 267 12486577175 268 12874563987 269 13273215526 270 13682808589 271 14103583360 272 14535827783 273 14979792315 274 15435776320 275 15904040798 276 16384897101 277 16878617036 278 17385524251 279 17905901922 280 18440086299 281 18988372213 282 19551109123 283 20128603822 284 20721219301 285 21329274912 286 21953147513 287 22593169339 288 23249731768 289 23923180231 290 24613920986 291 25322313307 292 26048778697 293 26793690624 294 27557486519 295 28340554403 296 29143348027 297 29966270645 298 30809792731 299 31674333152 300 32560379840 301 33468367656 302 34398802415 303 35352135714 304 36328891676 305 37329539043 306 38354621028 307 39404623944 308 40480110561 309 41581585529 310 42709631643 311 43864772345 312 45047611286 313 46258691159 314 47498636963 315 48768011474 316 50067461545 317 51397570518 318 52759007990 319 54152378363 320 55578374517 321 57037622787 322 58530839883 323 60058674614 324 61621868450 325 63221093205 326 64857115690 327 66530631663 328 68242433873 329 69993242580 330 71783877465 331 73615083875 332 75487709049 333 77402524413 334 79360405392 335 81362150112 336 83408663238 337 85500770215 338 87639405628 339 89825423290 340 92059788389 341 94343383763 342 96677206319 343 99062168606 344 101499299965 345 103989543763 346 106533962509 347 109133531106 348 111789346419 349 114502415598 350 117273870639 351 120104752122 352 122996227961 353 125949372933 354 128965392111 355 132045395252 356 135190625418 357 138402228586 358 141681486657 359 145029582647 360 148447838616 361 151937475445 362 155499856241 363 159136241082 364 162848035015 365 166636538187 366 170503198979 367 174449358505 368 178476509436 369 182586035231 370 186779473814 371 191058251934 372 195423954239 373 199878051724 374 204422176765 375 209057846078 376 213786740795 377 218610424350 378 223530628190 379 228548963484 380 233667213073 381 238887037405 382 244210271810 383 249638627100 384 255173992721 385 260818130929 386 266572986435 387 272440374580 388 278422296514 389 284520621789 390 290737409717 391 297074585225 392 303534267009 393 310118437095 394 316829274795 395 323668820455 396 330639315816 397 337742860770 398 344981760794 399 352358177138 400 359874480333 401 367532894271 402 375335856445 403 383285654715 404 391384794906 405 399635630748 406 408040737797 407 416602537031 408 425323675752 409 434206643563 410 443254160974 411 452468788227 412 461853320524 413 471410390204 414 481142869260 415 491053463612 416 501145123594 417 511420630810 418 521883015516 419 532535136542 420 543380106280 421 554420862345 422 565660600906 423 577102340596 424 588749363016 425 600604769445 426 612671929241 427 624954027995 428 637454524566 429 650176691169 430 663124077925 431 676300045410 432 689708237446 433 703352104728 434 717235386604 435 731361626338 436 745734660665 437 760358127241 438 775235962754 439 790371901107 440 805769980879 441 821434034774 442 837368205227 443 853576425694 444 870062945137 445 886831799718 446 903887346971 447 921233728457 448 938875412365 449 956816647680 450 975062016054 451 993615875974 452 1012482924711 453 1031667633071 454 1051174816121 455 1071009059147 456 1091175297952 457 1111678234479 458 1132522927549 459 1153714198707 460 1175257232096 461 1197156971126 462 1219418728339 463 1242047571330 464 1265048943423 465 1288428039475 466 1312190436018 467 1336341457571 468 1360886817102 469 1385831971200 470 1411182771787 471 1436944810757 472 1463124081539 473 1489726313852 474 1516757645987 475 1544223948049 476 1572131505839 477 1600486333215 478 1629294866182 479 1658563264998 480 1688298119389 481 1718505738690 482 1749192869131 483 1780365972670 484 1812031954851 485 1844197433032 486 1876869475745 487 1910054858578 488 1943760815984 489 1977994285449 490 2012762670309 491 2048073072881 492 2083933069220 493 2120349929442 494 2157331405378 495 2194884938800 496 2233018460424 497 2271739586741 498 2311056431366 499 2350976788620 500 2391508958235 501 2432660916371 502 2474441152138 503 2516857826777 504 2559919622942 505 2603634890212 506 2648012508159 507 2693061018901 508 2738789502356 509 2785206696542 510 2832321886079 511 2880144008317 512 2928682556113 513 2977946670524 514 3027946056214 515 3078690061497 516 3130188607385 517 3182451253029 518 3235488139501 519 3289309041345 520 3343924323443 521 3399343979433 522 3455578602738 523 3512638409868 524 3570534226650 525 3629276497208 526 3688876283697 527 3749344261747 528 3810691734780 529 3872929613846 530 3936069447687 531 4000122387730 532 4065100232141 533 4131014376790 534 4197876874387 535 4265699369369 536 4334494173227 537 4404273184109 538 4475048976589 539 4546833706773 540 4619640217658 541 4693480927602 542 4768368952453 543 4844316978205 544 4921338398029 545 4999446169987 546 5078653970129 547 5158975033091 548 5240423322438 549 5323012354941 550 5406756386362 551 5491669220255 552 5577765410358 553 5665059051708 554 5753565000835 555 5843297650073 556 5934272163632 557 6026503235978 558 6120006345020 559 6214796492258 560 6310889474338 561 6408300605820 562 6507046007187 563 6607141311136 564 6708602968218 565 6811446934376 566 6915689995484 567 7021348437013 568 7128439385490 569 7236979461167 570 7346986137711 571 7458476375502 572 7571468000825 573 7685978320709 574 7802025519589 575 7919627256651 576 8038802081217 577 8159568010186 578 8281943963487 579 8405948322500 580 8531600383538 581 8658918898183 582 8787923546126 583 8918633454973 584 9051068693727 585 9185248773037 586 9321194157235 587 9458924745993 588 9598461406243 589 9739824432700 590 9883035101087 591 10028114108467 592 10175083145618 593 10323963318171 594 10474776739478 595 10627544930038 596 10782290432220 597 10939035188952 598 11097802178151 599 11258613771642 600 11421493390702 601 11586463842590 602 11753548998646 603 11922772109438 604 12094157503137 605 12267728880343 606 12443511034158 607 12621528122035 608 12801805408990 609 12984367517449 610 13169240191393 611 13356448525233 612 13546018750311 613 13737976440109 614 13932348320563 615 14129160452677 616 14328440064310 617 14530213711257 618 14734509132013 619 14941353384525 620 15150774725453 621 15362800723633 622 15577460161505 623 15794781126382 624 16014792935484 625 16237524202242 626 16463004786477 627 16691263836810 628 16922331763585 629 17156238258449 630 17393014291603 631 17632690105677 632 17875297238850 633 18120866494124 634 18369429985854 635 18621019085585 636 18875666493512 637 19133404157965 638 19394265373421 639 19658282674710 640 19925489959114 641 20195920356423 642 20469608376727 643 20746587753366 644 21026893617970 645 21310560317477 646 21597623613900 647 21888118476576 648 22182081308264 649 22479547709564 650 22780554733053 651 23085138621013 652 23393337085010 653 23705187018130 654 24020726801621 655 24339993988602 656 24663027639410 657 24989865977954 658 25320548753182 659 25655114869246 660 25993604774778 661 26336058063721 662 26682515894141 663 27033018560933 664 27387607941439 665 27746325041297 666 28109212468573 667 28476311949567 668 28847666833186 669 29223319577882 670 29603314283615 671 29987694151157 672 30376504043354 673 30769787913568 674 31167591397983 675 31569959214464 676 31976937783110 677 32388572596801 678 32804910871793 679 33225998886613 680 33651884664512 681 34082615281952 682 34518239580132 683 34958805444372 684 35404362546437 685 35854959591507 686 36310647093133 687 36771474589073 688 37237493446016 689 37708754045555 690 38185308620564 691 38667208407883 692 39154506518183 693 39647255056679 694 40145508023557 695 40649318404095 696 41158741101467 697 41673829992801 698 42194640896287 699 42721228594453 700 43253649832643 701 43791960310855 702 44336217715495 703 44886478676264 704 45442801833041 705 46005244759210 706 46573867060677 707 47148727267017 708 47729885964531 709 48317402651585 710 48911338907724 711 49511755214556 712 50118714157850 713 50732277215382 714 51352507993941 715 51979468980537 716 52613224816261 717 53253839012246 718 53901377257316 719 54555904100083 720 55217486292383 721 55886189433789 722 56562081352875 723 57245228715574 724 57935700441047 725 58633564275381 726 59338890244082 727 60051747187348 728 60772206251226 729 61500337385852 730 62236212872137 731 62979903784431 732 63731483554757 733 64491024396090 734 65258600906197 735 66034286453037 736 66818156814914 737 67610286529493 738 68410752572380 739 69219630665823 740 70036998997855 741 70862934492148 742 71697516564436 743 72540823355057 744 73392935524694 745 74253932445704 746 75123896039333 747 76002906927339 748 76891048307313 749 77788402066094 750 78695052695407 751 79611083363045 752 80536579870982 753 81471626685867 754 82416310936179 755 83370718403647 756 84334937561581 757 85309055523147 758 86293162123129 759 87287345824567 760 88291697840507 761 89306308000578 762 90331268914964 763 91366671796801 764 92412610670547 765 93469178151826 766 94536469696687 767 95614579340510 768 96703603990389 769 97803639118854 770 98914783101733 771 100037132868277 772 101170788280906 773 102315847743393 774 103472412624746 775 104640582821239 776 105820461226707 777 107012149250050 778 108215751328357 779 109431370401501 780 110659112470425 781 111899082024486 782 113151386647282 783 114416132398412 784 115693428463090 785 116983382490060 786 118286105287353 787 119601706111965 788 120930297414135 789 122271990080416 790 123626898222812 791 124995134376940 792 126376814338383 793 127772052311503 794 129180965795409 795 130603670685172 796 132040286203576 797 133490929956475 798 134955722912785 799 136434784409413 800 137928237181972 801 139436202320991 802 140958804349534 803 142496166132474 804 144048414003391 805 145615672622372 806 147198070154692 807 148795733078892 808 150408791413332 809 152037373476288 810 153681611162941 811 155341634652821 812 157017577739737 813 158709572488363 814 160417754613125 815 162142258085797 816 163883220565826 817 165640777954216 818 167415069877901 819 169206234191670 820 171014412512596 821 172839744671829 822 174682374301668 823 176542443232448 824 178420097134782 825 180315479863422 826 182228739150608 827 184160020898772 828 186109474927581 829 188077249210576 830 190063495678626 831 192068364402341 832 194092009447780 833 196134583006550 834 198196241306377 835 200277138684017 836 202377433553323 837 204497282422849 838 206636845917269 839 208796282741545 840 210975755758393 841 213175425894001 842 215395458274286 843 217636016074087 844 219897266707885 845 222179375624474 846 224482512554861 847 226806845247349 848 229152545775361 849 231519784214818 850 233908735007659 851 236319570583472 852 238752467781430 853 241207601411057 854 243685150735344 855 246185292972665 856 248708209836663 857 251254080981318 858 253823090600432 859 256415420810591 860 259031258313102 861 261670787716820 862 264334198258140 863 267021677065737 864 269733415941353 865 272469604561226 866 275230437320551 867 278016106473613 868 280826809037425 869 283662739872571 870 286524098648962 871 289411082862022 872 292323894863441 873 295262734814765 874 298227807778573 875 301219316611611 876 304237469119246 877 307282470882723 878 310354532479887 879 313453862248580 880 316580673569050 881 319735177565582 882 322917590453561 883 326128126173862 884 329367003807468 885 332634440144773 886 335930657163095 887 339255874533034 888 342610317161847 889 345994207631240 890 349407773809712 891 352851241223889 892 356324840735078 893 359828800846331 894 363363355446199 895 366928736045941 896 370525179593495 897 374152920642986 898 377812199234169 899 381503252996379 900 385226325096527 901 388981656271761 902 392769492849148 903 396590078709247 904 400443663372536 905 404330493896180 906 408250823030310 907 412204901042197 908 416192983945517 909 420215325254087 910 424272184279281 911 428363817815565 912 432490488509173 913 436652456469595 914 440849987712670 915 445083345700325 916 449352799853054 917 453658617020192 918 458001070065005 919 462380429259505 920 466796970945403 921 471250968855714 922 475742702846558 923 480272450147887 924 484840494169264 925 489447115673756 926 494092601660968 927 498777236466399 928 503501310716610 929 508265112356330 930 513068935679103 931 517913072276033 932 522797820145189 933 527723474564336 934 532690337273894 935 537698707276085 936 542748890094698 937 547841188494483 938 552975911821121 939 558153366643165 940 563373866167001 941 568637720803719 942 573945247662437 943 579296761035877 944 584692581975354 945 590133028697501 946 595618426235629 947 601149096770033 948 606725369359095 949 612347570186790 950 618016032377054 951 623731086160886 952 629493068768580 953 635302314518904 954 641159164792593 955 647063958037263 956 653017039825590 957 659018752778406 958 665069446702175 959 671169468432705 960 677319172055417 961 683518908663173 962 689769036662888 963 696069911449969 964 702421895795675 965 708825349440750 966 715280639567052 967 721788130303820 968 728348193287123 969 734961197081208 970 741627517820287 971 748347528547500 972 755121609942562 973 761950139571722 974 768833502704845 975 775772081478965 976 782766265799111 977 789816442418037 978 796923005924441 979 804086347732093 980 811306867159122 981 818584960329090 982 825921031335672 983 833315481058311 984 840768718415838 985 848281149089969 986 855853186871568 987 863485242294584 988 871177734069170 989 878931077628647 990 886745696653253 991 894622011523232 992 902560450936919 993 910561440272603 994 918625413295073 995 926752800428995 996 934944040557594 997 943199569200582 998 951519830408807 999 959905264849333 1000 968356321790171