0 1 1 1 2 0 3 1 4 2 5 1 6 1 7 3 8 4 9 4 10 4 11 6 12 8 13 8 14 8 15 11 16 16 17 17 18 17 19 23 20 31 21 32 22 32 23 42 24 54 25 56 26 59 27 77 28 94 29 99 30 106 31 129 32 156 33 167 34 178 35 214 36 257 37 276 38 295 39 350 40 416 41 445 42 474 43 559 44 652 45 698 46 752 47 877 48 1012 49 1089 50 1174 51 1349 52 1542 53 1662 54 1792 55 2042 56 2327 57 2512 58 2706 59 3068 60 3472 61 3740 62 4026 63 4540 64 5106 65 5500 66 5933 67 6661 68 7446 69 8024 70 8656 71 9652 72 10744 73 11581 74 12482 75 13864 76 15384 77 16579 78 17857 79 19763 80 21856 81 23527 82 25318 83 27938 84 30782 85 33114 86 35643 87 39213 88 43070 89 46320 90 49827 91 54635 92 59838 93 64322 94 69140 95 75611 96 82643 97 88790 98 95365 99 104062 100 113475 101 121800 102 130720 103 142340 104 154874 105 166125 106 178215 107 193683 108 210298 109 225442 110 241689 111 262106 112 284070 113 304343 114 326030 115 352959 116 381933 117 408927 118 437751 119 473148 120 511184 121 546888 122 585010 123 631383 124 681076 125 728151 126 778474 127 838986 128 903722 129 965591 130 1031638 131 1110232 132 1194284 133 1275243 134 1361548 135 1463389 136 1572323 137 1677864 138 1790219 139 1921856 140 2062468 141 2199403 142 2345154 143 2514753 144 2695678 145 2872861 146 3061466 147 3279364 148 3511484 149 3740055 150 3983165 151 4262081 152 4559124 153 4853038 154 5165316 155 5521601 156 5900885 157 6277639 158 6677587 159 7131563 160 7614461 161 8095759 162 8606478 163 9183488 164 9796598 165 10409895 166 11060576 167 11792094 168 12568715 169 13348248 170 14174723 171 15099602 172 16081010 173 17069173 174 18116084 175 19282980 176 20520747 177 21770209 178 23093026 179 24562172 180 26119421 181 27694978 182 29362376 183 31207924 184 33162744 185 35145163 186 37242453 187 39555952 188 42004663 189 44493494 190 47125119 191 50018571 192 53079810 193 56197457 194 59492016 195 63104098 196 66923962 197 70820841 198 74936614 199 79437145 200 84193971 201 89054068 202 94185066 203 99781918 204 105693922 205 111743555 206 118128203 207 125075355 208 132409696 209 139925616 210 147853995 211 156460779 212 165543274 213 174862907 214 184689266 215 195333965 216 206562617 217 218097379 218 230253632 219 243396602 220 257253880 221 271503381 222 286515014 223 302715066 224 319787400 225 337360514 226 355867051 227 375802521 228 396801499 229 418436826 230 441212109 231 465703348 232 491491200 233 518083250 234 546064768 235 576107024 236 607727851 237 640358927 238 674681354 239 711476741 240 750189823 241 790166279 242 832200042 243 877199081 244 924523628 245 973424354 246 1024824774 247 1079775514 248 1137543171 249 1197270944 250 1260029106 251 1327034146 252 1397448854 253 1470292923 254 1546805196 255 1628395693 256 1714109014 257 1802821627 258 1895968635 259 1995184162 260 2099375337 261 2207258447 262 2320497914 263 2440982995 264 2567465100 265 2698482717 266 2835962866 267 2982084447 268 3135425219 269 3294325047 270 3461008867 271 3637989315 272 3823654032 273 4016115463 274 4217939754 275 4432027670 276 4656550378 277 4889360884 278 5133420483 279 5392075981 280 5663251811 281 5944510888 282 6239273000 283 6551393743 284 6878518270 285 7217890532 286 7573454509 287 7949641975 288 8343790803 289 8752789018 290 9181175365 291 9634044677 292 10108397304 293 10600719703 294 11116230658 295 11660789888 296 12231019910 297 12822951550 298 13442587215 299 14096664674 300 14781377623 301 15492253118 302 16236198320 303 17020949235 304 17842221926 305 18694990307 306 19587193882 307 20527701529 308 21511704337 309 22533566081 310 23602398010 311 24728365929 312 25906091598 313 27129254705 314 28408303520 315 29754895946 316 31163019516 317 32625588599 318 34154586710 319 35763376957 320 37445239442 321 39192246512 322 41018146462 323 42938241913 324 44945029654 325 47029667762 326 49207915527 327 51497273230 328 53889389468 329 56374420045 330 58970406073 331 61697360287 332 64546016246 333 67505422230 334 70596219452 335 73841297365 336 77230388159 337 80751312168 338 84427686679 339 88285684781 340 92313932430 341 96498917641 342 100867667638 343 105450082871 344 110233587180 345 115203234198 346 120389931275 347 125827805270 348 131502991902 349 137398996631 350 143551128777 351 149998331882 352 156725379900 353 163714087907 354 171004773944 355 178641885446 356 186608727210 357 194885273655 358 203517562195 359 212556305665 360 221983224195 361 231776322402 362 241988172340 363 252676598065 364 263821628382 365 275399189778 366 287469282244 367 300097784667 368 313262965160 369 326938546271 370 341192951060 371 356101227309 372 371639828262 373 387780127994 374 404600123256 375 422185308370 376 440510247715 377 459543813052 378 479374910155 379 500100912771 380 521694411289 381 544121679944 382 567484061614 383 591892395915 384 617317262898 385 643722280305 386 671222913313 387 699945255180 388 729857897594 389 760921753441 390 793268296176 391 827040948338 392 862206401678 393 898722801782 394 936739797492 395 976420526089 396 1017729851140 397 1060623120920 398 1105270660752 399 1151857988110 400 1200348251148 401 1250694075416 402 1303089314566 403 1357744846107 404 1414622305878 405 1473671781703 406 1535113820652 407 1599188004825 408 1665854815827 409 1735062035938 410 1807060454735 411 1882122233012 412 1960207183346 413 2041261071058 414 2125568991756 415 2213440100608 416 2304834095159 417 2399695106185 418 2498347198843 419 2601141487110 420 2708038215969 421 2818980510865 422 2934336714192 423 3054505441994 424 3179448395178 425 3309108547962 426 3443904432914 427 3584288419700 428 3730224865915 429 3881657642608 430 4039062117658 431 4202951588050 432 4373294598850 433 4550037143547 434 4733719004866 435 4924922586657 436 5123622354563 437 5329767947561 438 5543972230100 439 5766895892524 440 5998521401246 441 6238804046466 442 6488439615408 443 6748177385460 444 7018010396932 445 7297902126774 446 7588642285967 447 7891080330417 448 8205223107107 449 8531045272813 450 8869442835610 451 9221378703136 452 9586877425808 453 9965928360789 454 10359547891956 455 10768827442117 456 11193813767722 457 11634515114841 458 12092084284420 459 12567758169466 460 13061610995772 461 13573675121959 462 14105257954202 463 14657760869743 464 15231291930514 465 15825913908682 466 16443109187158 467 17084465068482 468 17750131107671 469 18440207896123 470 19156375725793 471 19900432243332 472 20672577611960 473 21472958835417 474 22303480142910 475 23166177226363 476 24061311312214 477 24989085943126 478 25951658867389 479 26951334968533 480 27988448736821 481 29063272417918 482 30178250764034 483 31335992858661 484 32536920847480 485 33781390118499 486 35072169992416 487 36412213174609 488 37802046530888 489 39242125353125 490 40735585820705 491 42285769077592 492 43893326662394 493 45558833186377 494 47285839600482 495 49078126182947 496 50936492091551 497 52861653832347 498 54857631451029 499 56928701426898 500 59075837038816 501 61299923378036 502 63605510998946 503 65997436690896 504 68476878843560 505 71044922320497 506 73706717132640 507 76467732614985 508 79329388436321 509 82293005295222 510 85364410283227 511 88549787127675 512 91850838798504 513 95269163317959 514 98811352643886 515 102484397409654 516 106290331975950 517 110231079677355 518 114314096682028 519 118547284578471 520 122933064502981 521 127473741041803 522 132177746731962 523 137054011098342 524 142105406126450 525 147334682527730 526 152751375185509 527 158365573224772 528 164180673736722 529 170199948089859 530 176434175288537 531 182894753011994 532 189585689000226 533 196510860788478 534 203682451600504 535 211113335708986 536 218808229295440 537 226771714302965 538 235017559026340 539 243560303353317 540 252405483892655 541 261558500637681 542 271034910897376 543 280851132552517 544 291013651527980 545 301528816644470 546 312414203291897 547 323688346337373 548 335358829226667 549 347433099355768 550 359931007868632 551 372873476387179 552 386269355886782 553 400127363389538 554 414469916342530 555 429320627174680 556 444689808045405 557 460587641382181 558 477039438646370 559 494071844791497 560 511696854306240 561 529926339866761 562 548788876050814 563 568314524258179 564 588517214335856 565 609410766750892 566 631027433683791 567 653401124568182 568 676547994265540 569 700484104704605 570 725245851593952 571 750871478902956 572 777379697117458 573 804789144176802 574 833140884004482 575 862478042606623 576 892822261968871 577 924195137328917 578 956642991743938 579 990214448330897 580 1024934508180653 581 1060828159675581 582 1097947649806718 583 1136347789296798 584 1176057425838446 585 1217105437863458 586 1259550742477774 587 1303455113769341 588 1348851801474733 589 1395774139097930 590 1444288552016898 591 1494464650661516 592 1546340718777008 593 1599955186546650 594 1655382930256522 595 1712702378116663 596 1771957564343022 597 1833192744888859 598 1896492307148509 599 1961944598647845 600 2029600217117384 601 2099510074016217 602 2171769259210396 603 2246477275499690 604 2323692207512456 605 2403472565057573 606 2485925476867704 607 2571162988156612 608 2659251719165445 609 2750258846873614 610 2844305038686438 611 2941516441248005 612 3041969399548806 613 3145740968528796 614 3252967038970836 615 3363789609380763 616 3478296094927354 617 3596574800188668 618 3718778731651024 619 3845067702894009 620 3975541721753278 621 4110301898370922 622 4249520478983270 623 4393377293042335 624 4541986665396778 625 4695464274071079 626 4854003985861233 627 5017808114039528 628 5187007252542271 629 5361733640319242 630 5542205434217294 631 5728650201142276 632 5921217011981758 633 6120056918675228 634 6325415363068544 635 6537548272300589 636 6756625686464405 637 6982820015655319 638 7216407346582270 639 7457675447396759 640 7706818141516178 641 7964032075344562 642 8229627747444252 643 8503928665940681 644 8787155615960410 645 9079532731811684 646 9381409142769062 647 9693148464584433 648 10015002033277007 649 10347225139503186 650 10690210269025280 651 11044366041266307 652 11409978392252422 653 11787337905518146 654 12176885719035700 655 12579080940680857 656 12994248668538801 657 13422719442752709 658 13864988987218475 659 14321573038197110 660 14792840995441265 661 15279168616432008 662 15781112856287154 663 16299252950525899 664 16834008392515090 665 17385806085800817 666 17955271652380908 667 18543055516528074 668 19149633789828318 669 19775491197046037 670 20421330347837529 671 21087881464097822 672 21775684620892316 673 22485289875348901 674 23217486138236308 675 23973093062775936 676 24752722946956841 677 25556999631498145 678 26386808751455881 679 27243070164758752 680 28126477679744002 681 29037738431402547 682 29977846439160972 683 30947833810492678 684 31948486307479558 685 32980605055330241 686 34045305492379801 687 35143745441285396 688 36276814358303600 689 37445419377398911 690 38650811926946284 691 39894290603167982 692 41176861746452506 693 42499551998422367 694 43863765068474132 695 45270957158199225 696 46722266298201242 697 48218853796267523 698 49762293853747004 699 51354219082299536 700 52995915820184998 701 54688697065634540 702 56434327861527184 703 58234638232293135 704 60091081474537166 705 62005141384804387 706 63978796573443478 707 66014097934224022 708 68112686647901889 709 70276238741895824 710 72506971772804007 711 74807183704053722 712 77178727067814808 713 79623494151823482 714 82143969801353874 715 84742728304070085 716 87421859841063915 717 90183499896744953 718 93030432251928677 719 95965540168215635 720 98991180940879599 721 102109763445142680 722 105324405722038276 723 108638336437329955 724 112054213011172132 725 115574751539213120 726 119203443733158029 727 122943904306668694 728 126799127778026079 729 130772175343785515 730 134866956351389932 731 139087516910206709 732 143437230028539066 733 147919544405130380 734 152538836068341670 735 157299633101951967 736 162205733316139566 737 167261020362516182 738 172470391652804451 739 177838913637069340 740 183370860733210908 741 189070604644324120 742 194943625159348880 743 200995589951859738 744 207231307992648756 745 213655698428124384 746 220274891404356359 747 227095225874218901 748 234122110154364592 749 241361077233993485 750 248818983373998393 751 256502916883913193 752 264418957848864086 753 272573327308387575 754 280973692057996700 755 289627976755882072 756 298543014163720586 757 307725796287774490 758 317184894513259511 759 326929166737462383 760 336966288769592144 761 347304116218380776 762 357952229819545782 763 368920528600606213 764 380217632341445492 765 391852363708500737 766 403835429430025466 767 416177889786349665 768 428889421206948632 769 441979928904219618 770 455461375452220383 771 469346116118570714 772 483645009740074036 773 498369172956363193 774 513531968734177420 775 529147196174984098 776 545227036817380775 777 561783962522049344 778 578832897521222927 779 596389250366792679 780 614466681776288427 781 633079179241534490 782 652243407256712286 783 671976568057914683 784 692293976038874554 785 713211313205221123 786 734747183409490307 787 756920787484932822 788 779749288042290743 789 803250261010032285 790 827444471019709692 791 852353345393687880 792 877996111778114396 793 904392462248281842 794 931565568432875582 795 959539337527385403 796 988335303765085153 797 1017975522962987827 798 1048485847487955897 799 1079892946056166994 800 1112220928539330408 801 1145494490311881014 802 1179742468745244120 803 1214994607073939115 804 1251277890431169290 805 1288619960905948734 806 1327052978970185117 807 1366610110155396760 808 1407321548444480186 809 1449218224584190132 810 1492335997773835822 811 1536711842224514177 812 1582379532059722086 813 1629373667249698311 814 1677734222987938478 815 1727502411331793590 816 1778715999660333202 817 1831413680621610922 818 1885640008837978590 819 1941440910780087348 820 1998858606632434787 821 2057936352816151691 822 2118723797974888038 823 2181272112082989702 824 2245628479237804052 825 2311841243574679025 826 2379965719001656103 827 2450058906301252847 828 2522173521794589434 829 2596363579870143936 830 2672690693725960141 831 2751218346789686827 832 2832005419351487970 833 2915112243573317249 834 3000607435546131398 835 3088561684640190961 836 3179040737153575655 837 3272111962616200026 838 3367851760680665097 839 3466338829057233511 840 3567646560043943774 841 3671850160080718062 842 3779034678367176334 843 3889287710922675911 844 4002691162472564798 845 4119328964500550706 846 4239295776140020491 847 4362689078644909945 848 4489600251390786916 849 4620122937167276326 850 4754362469939621844 851 4892427310487306118 852 5034419381167301386 853 5180443131041700603 854 5330615749504999664 855 5485057889933690534 856 5643883203473225229 857 5807208160846353490 858 5975163115499612876 859 6147882257850000541 860 6325492283754381782 861 6508123034399973051 862 6695919477512350560 863 6889030830295209335 864 7087598293349296184 865 7291766574809412293 866 7501696863459770797 867 7717555053758707820 868 7939498470611317668 869 8167688349002233480 870 8402303878701419304 871 8643529459672802656 872 8891540337213277270 873 9146516113892252599 874 9408655951879099036 875 9678164781410664859 876 9955237759504401537 877 10240074897157412628 878 10532897512037184027 879 10833933306577152978 880 11143399556862058828 881 11461518944592242730 882 11788537359958527156 883 12124707759487058355 884 12470271984645640112 885 12825477894978029666 886 13190598628629889275 887 13565915143293626420 888 13951696556400511977 889 14348218683166194926 890 14755784870645512273 891 15174707117809796835 892 15605284820751969304 893 16047824827421431167 894 16502663970191792684 895 16970148653051265150 896 17450611876244597534 897 17944394928284122948 898 18451871751677135007 899 18973426876485440071 900 19509430589346835184 901 20060262392785140333 902 20626337348928936130 903 21208082229471822424 904 21805908683928706080 905 22420238606183886330 906 23051532612047233484 907 23700264265944168865 908 24366891092265465563 909 25051881999682664248 910 25755748060437612686 911 26479014663617515244 912 27222190201447518680 913 27985795713432588747 914 28770398148331843748 915 29576580282390373695 916 30404906899581844329 917 31255956830278386231 918 32130358890697093761 919 33028759392037710200 920 33951785620169491113 921 34900080457028446129 922 35874341206960657734 923 36875284509569467347 924 37903606909929500332 925 38960022265166535543 926 40045303682899545652 927 41160245636752627520 928 42305621402538329918 929 43482223467657412043 930 44690908824089353775 931 45932558070596043136 932 47208029473246576418 933 48518202611816332328 934 49864027288400181980 935 51246479384016084052 936 52666511283630885114 937 54125099011774641392 938 55623295037641638495 939 57162180636178205618 940 58742812398543595517 941 60366273128465056729 942 62033728845616761744 943 63746377382612059366 944 65505390681368070072 945 67311969742096268637 946 69167406149319869074 947 71073026616505472596 948 73030130746593986970 949 75040050347277670267 950 77104215828587752498 951 79224096385705336979 952 81401132877788546804 953 83636801846783090543 954 85932687162052619588 955 88290415508804782885 956 90711584013560666614 957 93197829329473800987 958 95750904931653249768 959 98372611553724929929 960 101064719161088435976 961 103829041493195811971 962 106667519443087192676 963 109582146058207499434 964 112574882433595095834 965 115647738130660042602 966 118802861106590400735 967 122042456867670352579 968 125368697823186646998 969 128783810031251187319 970 132290170178695384152 971 135890218445160715629 972 139586360824456539838 973 143381062681609681960 974 147276953321528497334 975 151276732089543135076 976 155383063130630238050 977 159598676278392902750 978 163926479790838665450 979 168369459177947547809 980 172930563830779494252 981 177612815802163479802 982 182419431330385118170 983 187353711847153050347 984 192418921867725342138 985 197618406264419849973 986 202955721244697929972 987 208434516953584518970 988 214058405971766141575 989 219831089727180088614 990 225756499643522012541 991 231838670708942181003 992 238081599881248860652 993 244489382330560787435 994 251066363527644065232 995 257817003104892493974 996 264745722416726515120 997 271857051358098211686 998 279155792218801502932 999 286646873113470870992 1000 294335183891325191669