0 1 1 1 2 2 3 3 4 4 5 6 6 9 7 11 8 14 9 20 10 26 11 33 12 41 13 50 14 64 15 81 16 97 17 120 18 150 19 176 20 210 21 255 22 303 23 362 24 426 25 503 26 595 27 703 28 816 29 953 30 1113 31 1283 32 1482 33 1721 34 1988 35 2299 36 2650 37 3031 38 3464 39 3965 40 4492 41 5115 42 5820 43 6592 44 7467 45 8484 46 9568 47 10822 48 12185 49 13724 50 15445 51 17381 52 19475 53 21855 54 24478 55 27367 56 30571 57 34143 58 38027 59 42405 60 47178 61 52446 62 58247 63 64746 64 71722 65 79565 66 88135 67 97558 68 107855 69 119327 70 131671 71 145423 72 160319 73 176696 74 194527 75 214256 76 235432 77 258901 78 284369 79 312240 80 342460 81 375783 82 411628 83 451123 84 493767 85 540366 86 590901 87 646290 88 705738 89 771034 90 841438 91 918147 92 1000950 93 1091447 94 1188552 95 1294811 96 1409017 97 1533303 98 1667183 99 1813092 100 1969456 101 2139916 102 2323109 103 2521707 104 2735422 105 2967614 106 3216187 107 3486437 108 3776357 109 4090136 110 4427030 111 4792125 112 5182501 113 5605990 114 6059564 115 6549488 116 7074613 117 7642555 118 8249348 119 8905647 120 9607639 121 10364623 122 11174847 123 12049158 124 12982329 125 13989391 126 15065732 127 16224007 128 17461892 129 18795254 130 20217388 131 21748910 132 23383513 133 25139922 134 27015541 135 29031521 136 31179488 137 33488614 138 35951040 139 38592225 140 41409027 141 44431887 142 47650564 143 51104135 144 54782608 145 58722911 146 62920991 147 67418810 148 72203236 149 77329256 150 82784497 151 88619399 152 94829222 153 101472799 154 108534927 155 116089301 156 124121011 157 132701282 158 141825313 159 151572775 160 161925460 161 172985121 162 184734429 163 197269890 164 210587192 165 224796857 166 239878241 167 255967785 168 273046059 169 291246746 170 310566661 171 331155823 172 352991096 173 376257126 174 400935430 175 427205160 176 455066839 177 484725279 178 516158286 179 549611323 180 585066725 181 622769808 182 662728190 183 705216023 184 750213438 185 798052219 186 848718362 187 902542795 188 959542627 189 1020091908 190 1084174555 191 1152233816 192 1224263461 193 1300712294 194 1381615557 195 1467472035 196 1558278425 197 1654628326 198 1756533646 199 1864590962 200 1978865554 201 2100026553 202 2228096103 203 2363857258 204 2507351300 205 2659379351 206 2820051786 207 2990257830 208 3170055513 209 3360488866 210 3561645533 211 3774589383 212 3999496108 213 4237552943 214 4488880758 215 4754849694 216 5035622663 217 5332617784 218 5646110720 219 5977665805 220 6327499080 221 6697426359 222 7087719443 223 7500247932 224 7935431686 225 8395346887 226 8880349462 227 9392819880 228 9933191552 229 10503946543 230 11105704397 231 11741201028 232 12410992099 233 13118216671 234 13863539292 235 14650222924 236 15479176062 237 16354010185 238 17275572239 239 18247968039 240 19272191566 241 20352550398 242 21490354134 243 22690334680 244 23953753866 245 25285994529 246 26688522667 247 28166977263 248 29723227730 249 31363492231 250 33089612839 251 34908607076 252 36822594479 253 38838978877 254 40960400654 255 43194980282 256 45545368602 257 48020732512 258 50624099100 259 53365129601 260 56247523195 261 59281898919 262 62472029756 263 65829820290 264 69359557259 265 73073849313 266 76977853502 267 81085380368 268 85401741788 269 89942420497 270 94713415545 271 99731124272 272 105002669453 273 110546029544 274 116368612895 275 122490473743 276 128919944549 277 135678350595 278 142775465338 279 150234614038 280 158066026419 281 166295703196 282 174935115585 283 184011901362 284 193539399180 285 203547857674 286 214051321732 287 225083386503 288 236659735410 289 248816190795 290 261570846081 291 274962813916 292 289011243306 293 303759533723 294 319229016307 295 335465956678 296 352494792047 297 370366076655 298 389105771107 299 408769780383 300 429386939021 301 451017007917 302 473692825969 303 497479548277 304 522412173283 305 548562710009 306 575969943124 307 604710839771 308 634829332555 309 666409373257 310 699497908763 311 734187455256 312 770529944414 313 808624439965 314 848529499909 315 890352992422 316 934157628189 317 980062213628 318 1028135964727 319 1078506096112 320 1131250334140 321 1186507216120 322 1244360160978 323 1304961364753 324 1368402731815 325 1434847498926 326 1504398489862 327 1577233217939 328 1653462183544 329 1733280278892 330 1816809047528 331 1904257503644 332 1995761180717 333 2091547390807 334 2191761965542 335 2296653941334 336 2406383508902 337 2521218088315 338 2641335739162 339 2767026954523 340 2898483496588 341 3036023424645 342 3179857107430 343 3330325990925 344 3487663328294 345 3652240004667 346 3824307414820 347 4004270963561 348 4192406025982 349 4389148264075 350 4594802262071 351 4809840730244 352 5034592148828 353 5269572863858 354 5515142285414 355 5771855210836 356 6040108285719 357 6320503471916 358 6613468696030 359 6919660495604 360 7239546569053 361 7573832844840 362 7923034444942 363 8287916578715 364 8669035174671 365 9067224288726 366 9483090924174 367 9917531733368 368 10371213995999 369 10845109527839 370 11339938626171 371 11856759202360 372 12396356924807 373 12959869635033 374 13548159616583 375 14162459053910 376 14803698858453 377 15473219578232 378 16172035662154 379 16901588733981 380 17662990335844 381 18457801320190 382 19287221867658 383 20152948135208 384 21056286771819 385 21999062432931 386 22982704877758 387 24009188223090 388 25080056074570 389 26197452559859 390 27363056827137 391 28579174950103 392 29847641828233 393 31170951788387 394 32551085787939 395 33990750227951 396 35492098278982 397 37058041442546 398 38690929575668 399 40393909861837 400 42169518864748 401 44021169493086 402 45951616799587 403 47964531519609 404 50062916781175 405 52250739356906 406 54531240689415 407 56908718765446 408 59386691336531 409 61969781720231 410 64661820313914 411 67467800327479 412 70391855297404 413 73439392443161 414 76614894675208 415 79924177191562 416 83372116130285 417 86964990206582 418 90708060445545 419 94608120924510 420 98670873175703 421 102903624172976 422 107312569883693 423 111905595215389 424 116689383484001 425 121672462588854 426 126862070911074 427 132267378022441 428 137896242437849 429 143758556149400 430 149862793861653 431 156219646676907 432 162838287184293 433 169730210510477 434 176905366668304 435 184376150089035 436 192153288004369 437 200250169791837 438 208678398992704 439 217452368536511 440 226584654767307 441 236090771853658 442 245984275075060 443 256281913086892 444 266998339695424 445 278151557347006 446 289757436244670 447 301835372194347 448 314402465314236 449 327479645362827 450 341085387764077 451 355242183472743 452 369970026577511 453 385293140899593 454 401233063908373 455 417815919896972 456 435064965425395 457 453008270137242 458 471670984342941 459 491083327081478 460 511272381484991 461 532270723105910 462 554107581547615 463 576817948801570 464 600433412942410 465 624991633461572 466 650526615565101 467 677078933882566 468 704685268928823 469 733389198397378 470 763230337053126 471 794255564939232 472 826507514367938 473 860036672818744 474 894889003677849 475 931118716767051 476 968775421278135 477 1007917416654759 478 1048598073500604 479 1090880146456591 480 1134821147602234 481 1180488445858329 482 1227944078566996 483 1277260467945293 484 1328504333173445 485 1381753599160050 486 1437080128257253 487 1494567553233320 488 1554293345364932 489 1616347382193829 490 1680812954597458 491 1747786724351090 492 1817358360793031 493 1889631584431659 494 1964703010637294 495 2042684062018127 496 2123678577086501 497 2207806342898073 498 2295179098858183 499 2385925344885701 500 2480165411275171 501 2578037296891719 502 2679670286057834 503 2785212671865076 504 2894803513830185 505 3008601856502829 506 3126757374054287 507 3249440805859117 508 3376812909596219 509 3509057093145103 510 3646346194332535 511 3788876864686151 512 3936835042415219 513 4090431772887720 514 4249866698226708 515 4415366429451159 516 4587145519598875 517 4765446887483427 518 4950501237110409 519 5142569176284458 520 5341898330268298 521 5548768427429138 522 5763445478638608 523 5986229259932053 524 6217405672877329 525 6457296223758996 526 6706207684469731 527 6964485015989990 528 7232457632489177 529 7510495129833818 530 7798951394115200 531 8098222678640565 532 8408688578693208 533 8730774106648794 534 9064886715052638 535 9411481643534279 536 9770996420654529 537 10143918973383365 538 10530718464555940 539 10931918039892826 540 11348021096340842 541 11779587849659754 542 12227158625488088 543 12691333666550524 544 13172692179103127 545 13671877515280892 546 14189510910663015 547 14726281118649380 548 15282854668401297 549 15859969304978807 550 16458339293451970 551 17078755083743549 552 17721982485204709 553 18388867518699218 554 19080231497407400 555 19796980332340189 556 20539993879178718 557 21310242452975962 558 22108669060188528 559 22936311951731476 560 23794182079857799 561 24683390869130117 562 25605020995298055 563 26560262491743611 564 27550275327304297 565 28576332535982526 566 29639677188173303 567 30741671619660346 568 31883646676912762 569 33067060592411198 570 34293338724625767 571 35564040595308769 572 36880693102800856 573 38244964686638619 574 39658489564641571 575 41123053037174453 576 42640404774898792 577 44212453607727202 578 45841073162704011 579 47528304972902363 580 49276153743517049 581 51086803333713143 582 52962399354533900 583 54905276151540506 584 56917730517722858 585 59002258380519119 586 61161316480010632 587 63397573910283590 588 65713659214244151 589 68112424694603329 590 70596683119646810 591 73169483339648301 592 75833833106605019 593 78592991828689262 594 81450176550184066 595 84408869496081962 596 87472511998423154 597 90644825209527386 598 93929487936774356 599 97330477116099592 600 100851726279613592 601 104497483170022890 602 108271954151249283 603 112179677130024026 604 116225147428404047 605 120413213477761282 606 124748680354288202 607 129236725305997421 608 133882484993655730 609 138691488827464139 610 143669224758267603 611 148821598837865162 612 154154475353715070 613 159674159333259872 614 165386917725196933 615 171299482573524056 616 177418547508485766 617 183751301117651346 618 190304893873601688 619 197086998028690681 620 204105252608849610 621 211367847307685621 622 218882938962021008 623 226659270175222836 624 234705551882352997 625 243031112615610049 626 251645255597840218 627 260557935829742774 628 269779084384893198 629 279319325452042735 630 289189261608864376 631 299400226238232324 632 309963539373455566 633 320891292356489417 634 332195565868653369 635 343889260492647915 636 355985270021570262 637 368497352845722198 638 381439271138826750 639 394825699580093491 640 408671321095805347 641 422991788334658556 642 437802768021456338 643 453120949486912494 644 468963049672488670 645 485346864862142945 646 502290225658579410 647 519812109274699860 648 537931535657585564 649 556668734037188733 650 576043993504285021 651 596078879505529729 652 616795027021698476 653 638215426569289603 654 660363149857592531 655 683262698255873339 656 706938675983292435 657 731417196307257315 658 756724488709564286 659 782888384816224123 660 809936848308647973 661 837899532786244144 662 866806251070502183 663 896688599698093965 664 927578352572855195 665 959509176884995488 666 992514938223743193 667 1026631499230363596 668 1061894954970341152 669 1098343508518004677 670 1136015619425425700 671 1174951984070970693 672 1215193582945141451 673 1256783756138105717 674 1299766170219104305 675 1344186982403819365 676 1390092707951606871 677 1437532504364527794 678 1486555922933345284 679 1537215302270888377 680 1589563427456552810 681 1643656025807010161 682 1699549311913540351 683 1757302620804449270 684 1816975820741678758 685 1878632071975865630 686 1942335133162083049 687 2008152237836279005 688 2076151270320252416 689 2146403799500785962 690 2218982103496597613 691 2293962347593654599 692 2371421486848792472 693 2451440579545160961 694 2534101540313786833 695 2619490633483980187 696 2707695053724233801 697 2798806584832010251 698 2892918040025202302 699 2990127076624904665 700 3090532465561209419 701 3194238111812016393 702 3301349126900687703 703 3411976039002932871 704 3526230704643296257 705 3644230698046962073 706 3766095027448685044 707 3891948759578704865 708 4021918511469243191 709 4156137292425934178 710 4294739811223442190 711 4437867524003128790 712 4585663718498939159 713 4738278830598420790 714 4895865272473868749 715 5058582998229182578 716 5226594120756420674 717 5400068713915806657 718 5579179174573669843 719 5764106331589723796 720 5955033516303120541 721 6152152956825154756 722 6355659606354790406 723 6565757808862789386 724 6782654836968836399 725 7006567907893446818 726 7237717389082821788 727 7476334140652044254 728 7722652444153645446 729 7976917656451661981 730 8239378806964015401 731 8510296651174440461 732 8789935890031126812 733 9078573597007205235 734 9376491120654907997 735 9683982868620290905 736 10001347832683634036 737 10328898828688962505 738 10666953591410160704 739 11015844441613034200 740 11375909019141985974 741 11747500359115394392 742 12130977194645328798 743 12526714552746701903 744 12935093568375767865 745 13356512568585851706 746 13791376473059719497 747 14240108346768149726 748 14703138310884504292 749 15180915687936785317 750 15673897356956183629 751 16182560456370760377 752 16707390267624659589 753 17248893454436841234 754 17807585388967115361 755 18384004065968237434 756 18978696798158368976 757 19592234767394329998 758 20225199181745979882 759 20878196440340275658 760 21551843656884705224 761 22246784593270865240 762 22963674466537316093 763 23703196609461205399 764 24466046664488325077 765 25252949946191612923 766 26064644914644382451 767 26901901412978412905 768 27765503328143662824 769 28656267658154172829 770 29575026473937781671 771 30522646788785331760 772 31500011702185937110 773 32508041265258700122 774 33547672702539434353 775 34619882223496815823 776 35725664449249878378 777 36866055140775431419 778 38042109696220085881 779 39254927012149982154 780 40505626936224003591 781 41795375207206003395 782 43125360002425968415 783 44496817924473786109 784 45911009494737650981 785 47369246428729100466 786 48872865945456694192 787 50423259271953835169 788 52021844923986006752 789 53670098405645479443 790 55369524293965650195 791 57121687403391246985 792 58928183530150569488 793 60790672017059391989 794 62710845328331387413 795 64690462977720907205 796 66731319748283945053 797 68835281285498262593 798 71004250799223642166 799 73240206251326250456 800 75545165730103782461 801 77921226193068675627 802 80370527305338296888 803 82895292073709596725 804 85497788968965848187 805 88180374375050689666 806 90945453203786818627 807 93795523116793167127 808 96733133401674978119 809 99760931342277461542 810 102881619153445292289 811 106098002416422977072 812 109412945304461283149 813 112829421038522233779 814 116350465144464828048 815 119979228347547047678 816 123718927636546560228 817 127572901507469524980 818 131544559088943140317 819 135637437687197740234 820 139855149685807486569 821 144201442859023315737 822 148680144793143057629 823 153295225870589381245 824 158050741496018819300 825 162950897700908287848 826 167999990852350820830 827 173202476398475792023 828 178562905780140845128 829 184085998212459287661 830 189776575109397498173 831 195639634847804354600 832 201680284348795270368 833 207903817404602622560 834 214315643102418440317 835 220921367600533943303 836 227726719739032931508 837 234737636209721891472 838 241960183954295652292 839 249400649374249434704 840 257065457168893712212 841 264961263463564246359 842 273094871464532197676 843 281473328446695693835 844 290103837784019502825 845 298993860517275537807 846 308151023369509985388 847 317583224762567514499 848 327298539236007350179 849 337305327852271561301 850 347612138524823165983 851 358227821613620190916 852 369161425730918119561 853 380422318386836097163 854 392020077730772389451 855 403964618184289621598 856 416266077571745688454 857 428934948634158346447 858 441981961064752977094 859 455418218753248348299 860 469255077234311778619 861 483504286598763471042 862 498177863743922275090 863 513288241945395873998 864 528848137374430523444 865 544870705170568185944 866 561369400781198834143 867 578358142470020498041 868 595851166803511376894 869 613863198702451790909 870 632409300476012038991 871 651505049245213655517 872 671166380140220192844 873 691409771031259834007 874 712252079134839411796 875 733710734283168299699 876 755803568277101728787 877 778549016513859244332 878 801965940759071724949 879 826073839068373894029 880 850892661145673248627 881 876443027929196019040 882 902746038795152363575 883 929823500616108688116 884 957697727555040851556 885 986391779534833780122 886 1015929253692714269273 887 1046334533784345220464 888 1077632572480327170741 889 1109849151504201738086 890 1143010655584760655678 891 1177144343268619205506 892 1212278111502255173501 893 1248440778814430173239 894 1285661839613560119313 895 1323971759527982846725 896 1363401720318925382305 897 1403983927326172278609 898 1445751343851822848182 899 1488738012595235185225 900 1532978778498555617032 901 1578509623950816203789 902 1625367381078523738494 903 1673590080671685325103 904 1723216652657177039768 905 1774287290842692166312 906 1826843140445797694692 907 1880926678425795807144 908 1936581389155337577032 909 1993852160304903655429 910 2052784945250615328134 911 2113427176838864850600 912 2175827415287629024935 913 2240035779595116726163 914 2306103582121411606640 915 2374083777616714698423 916 2444030582932589979128 917 2515999946258864310944 918 2590049150577684676881 919 2666237302865544976020 920 2744624922601749583404 921 2825274450929205575873 922 2908249822491681148278 923 2993616997427319838554 924 3081443515006752213525 925 3171799048214002801374 926 3264754940616199606673 927 3360384783544250552468 928 3458763934292294785755 929 3559970119094094238278 930 3664082930949654501342 931 3771184458147779623698 932 3881358763300587829153 933 3994692537451917110119 934 4111274558205733259275 935 4231196372967796555264 936 4354551734292025365718 937 4481437312010594474220 938 4611952107521916444074 939 4746198194878300635762 940 4884280111687810240196 941 5026305633101858675045 942 5172385137243505601153 943 5322632411852073101602 944 5477163996141458410944 945 5636100020212175026771 946 5799563520753555639070 947 5967681317598628766363 948 6140583300971453789316 949 6318403344956059533714 950 6501278568365081431632 951 6689350285275916199313 952 6882763236675611203467 953 7081666582925038937608 954 7286213103625142279695 955 7496560231793094739658 956 7712869224240313512800 957 7935306237673695946727 958 8164041466427387851567 959 8399250265882928645554 960 8641112254744241200968 961 8889812485586729464625 962 9145540514174034581302 963 9408491617411367779961 964 9678865826232430012781 965 9956869196948712942942 966 10242712804584808038751 967 10536614067461843344773 968 10838795703736112796249 969 11149487109576770630366 970 11468923275059549506606 971 11797346222584284634869 972 12135003878692920188535 973 12482151572609737701239 974 12839050866989137301985 975 13205971117028852737234 976 13583188255918369812920 977 13970986421906529500269 978 14369656694643801058812 979 14779498790136912036778 980 15200819751299258857947 981 15633935711358849426330 982 16079170533934864946691 983 16536857653084052606661 984 17007338658723462154515 985 17490965213320524627073 986 17988097586275863313269 987 18499106647950860986562 988 19024372347868586655284 989 19564285795168797618337 990 20119247675995971189524 991 20689670420464710203035 992 21275976563220350985981 993 21878600997767909516689 994 22497989274519447761887 995 23134599952566492870252 996 23788902830131066577537 997 24461381393975276692548 998 25152530986601949905317 999 25862861354331554447396 1000 26592894745014892985683