0 1 1 1 2 1 3 2 4 3 5 3 6 5 7 7 8 8 9 11 10 15 11 17 12 23 13 30 14 35 15 44 16 57 17 66 18 82 19 103 20 121 21 146 22 181 23 211 24 253 25 308 26 360 27 425 28 513 29 596 30 700 31 834 32 969 33 1127 34 1333 35 1541 36 1786 37 2093 38 2415 39 2781 40 3241 41 3723 42 4273 43 4946 44 5669 45 6476 46 7461 47 8519 48 9705 49 11123 50 12669 51 14379 52 16418 53 18638 54 21101 55 23993 56 27173 57 30671 58 34763 59 39256 60 44211 61 49940 62 56267 63 63207 64 71204 65 80020 66 89707 67 100771 68 113011 69 126410 70 141666 71 158513 72 176980 73 197861 74 220963 75 246221 76 274703 77 306156 78 340573 79 379176 80 421843 81 468440 82 520578 83 578103 84 640961 85 710993 86 788274 87 872593 88 966342 89 1069617 90 1182326 91 1307212 92 1444755 93 1594677 94 1760495 95 1942825 96 2141575 97 2360787 98 2601702 99 2864038 100 3152926 101 3469935 102 3815091 103 4194311 104 4610164 105 5062517 106 5558821 107 6102305 108 6693353 109 7340584 110 8048796 111 8818335 112 9659985 113 10579732 114 11578794 115 12669702 116 13860868 117 15153731 118 16563889 119 18101789 120 19770330 121 21587707 122 23568077 123 25715074 124 28051260 125 30594123 126 33349716 127 36344483 128 39601526 129 43128541 130 46958212 131 51118970 132 55622463 133 60507165 134 65809926 135 71545599 136 77761619 137 84503164 138 91791454 139 99682573 140 108234239 141 117473425 142 127469137 143 138291916 144 149978856 145 162611857 146 176280015 147 191030279 148 206963235 149 224187452 150 242765759 151 262817967 152 284479944 153 307830783 154 333017390 155 360204910 156 389497060 157 421069325 158 455126820 159 491799426 160 531301975 161 573883178 162 619710684 163 669041738 164 722183307 165 779344231 166 840838922 167 907038809 168 978210078 169 1054729871 170 1137054174 171 1225512959 172 1320566422 173 1422765188 174 1532525511 175 1650400082 176 1777061802 177 1913024273 178 2058960734 179 2215682251 180 2383831151 181 2564216533 182 2757825653 183 2965447662 184 3188066353 185 3426869594 186 3682837102 187 3957151497 188 4251253663 189 4566342421 190 4903853036 191 5265516316 192 5652811198 193 6067462704 194 6511563821 195 6986917507 196 7495613267 197 8040161183 198 8622773255 199 9245959587 200 9912747076 201 10625822969 202 11388221724 203 12203567873 204 13075142331 205 14006587501 206 15002263143 207 16066142212 208 17202619189 209 18416906768 210 19713834659 211 21098672490 212 22577675800 213 24156675328 214 25842015964 215 27641166108 216 29561186390 217 31609676276 218 33795578982 219 36127394497 220 38614254521 221 41266820813 222 44095350158 223 47110765539 224 50325808411 225 53752793699 226 57404820461 227 61297057015 228 65444316050 229 69862243965 230 74568933369 231 79582124964 232 84920545106 233 90605702221 234 96658872686 235 103102391363 236 109961866935 237 117262721518 238 125031634434 239 133299006952 240 142095245296 241 151452121022 242 161405768445 243 171992437789 244 183250008063 245 195221316959 246 207949612970 247 221479934648 248 235863113546 249 251150601778 250 267395995113 251 284659472930 252 303002276949 253 322488032791 254 343188035529 255 365174997851 256 388524495597 257 413320820878 258 439650331780 259 467602606077 260 497277350726 261 528776903864 262 562207478059 263 597686799185 264 635336160311 265 675281254706 266 717661127845 267 762619256083 268 810304415344 269 860880561822 270 914517416164 271 971390768592 272 1031693983634 273 1095627472964 274 1163398957754 275 1235236146203 276 1311375672648 277 1392062600029 278 1477565096826 279 1568162122899 280 1664142779253 281 1765822454966 282 1873529953620 283 1987605834187 284 2108421008497 285 2236362470920 286 2371831337818 287 2515263275094 288 2667113663875 289 2827854318335 290 2997996904279 291 3178076569561 292 3368648163355 293 3570311919109 294 3783696548628 295 4009453750151 296 4248287527292 297 4500935623146 298 4768163274356 299 5050795315862 300 5349697152316 301 5665766319625 302 5999968993380 303 6353319201631 304 6726869306169 305 7121749920431 306 7539148798087 307 7980298531794 308 8446521785117 309 8939208366475 310 9459801437570 311 10009846898157 312 10590970362359 313 11204859866782 314 11853321646623 315 12538255305793 316 13261634525451 317 14025567876011 318 14832274235459 319 15684059130834 320 16583383212662 321 17532835968572 322 18535109441193 323 19593072784607 324 20709746729454 325 21888271895058 326 23131992505380 327 24444429381207 328 25829244872086 329 27290333890714 330 28831798367222 331 30457905540009 332 32173189908839 333 33982426625893 334 35890585500566 335 37902941729229 336 40025051727883 337 42262699038085 338 44622018040384 339 47109469372279 340 49731780475177 341 52496079801864 342 55409876003173 343 58480988670074 344 61717697944763 345 65128724257529 346 68723152455246 347 72510593927070 348 76501171881442 349 80705433690763 350 85134531255558 351 89800208210654 352 94714704207210 353 99890950167360 354 105342563369276 355 111083737671545 356 117129460325106 357 123495510903549 358 130198341816064 359 137255312804031 360 144684700806705 361 152505563831839 362 160738000896396 363 169403168345164 364 178523132163269 365 188121148889848 366 198221696835654 367 208850308850653 368 220033883235772 369 231800724905589 370 244180364570737 371 257203894497456 372 270904029672341 373 285314904226207 374 300472442534976 375 316414434946764 376 333180318447478 377 350811577184704 378 369351844729134 379 388846658484540 380 409343901831561 381 430893926993566 382 453549291432968 383 477365234834416 384 502399836822050 385 528713723375783 386 556370592830734 387 585437402037868 388 615984052527197 389 648083957779722 390 681814274783290 391 717255556360164 392 754492376191708 393 793613598914974 394 834712010124694 395 877884990340935 396 923234843813279 397 970868390851075 398 1020897709899895 399 1073440517814662 400 1128619738173281 401 1186564301482372 402 1247409600910256 403 1311297019335643 404 1378374809984461 405 1448798620098789 406 1522730992965926 407 1600342317739361 408 1681811449583741 409 1767325167409034 410 1857079218850052 411 1951279029229422 412 2050139134375997 413 2153884308161472 414 2262750394237927 415 2376983692542714 416 2496842199675994 417 2622596555837026 418 2754529408197550 419 2892936750101151 420 3038129023605570 421 3190430436149770 422 3350180433932153 423 3517734952869858 424 3693465716365079 425 3877761827394736 426 4071031215985350 427 4273699892336713 428 4486213698968336 429 4709039948321828 430 4942666664683185 431 5187604479495185 432 5444388516360937 433 5713577593953714 434 5995756312933226 435 6291537183324150 436 6601559828734519 437 6926493246661376 438 7267038246475795 439 7623926625293814 440 7997923658535291 441 8389830845593957 442 8800485106098245 443 9230761481395298 444 9681576269235741 445 10153886209313487 446 10648691462585525 447 11167039135135152 448 11710022512037167 449 12278784294429788 450 12874520609562268 451 13498480261038410 452 14151968302567486 453 14836350538723323 454 15553052863260255 455 16303565149268613 456 17089446356431381 457 17912323925543689 458 18773898078423944 459 19675947542219420 460 20620329087355814 461 21608982217573980 462 22643935649600996 463 23727306964046775 464 24861307796286546 465 26048251090211678 466 27290550968398701 467 28590728406053891 468 29951419424220285 469 31375375151935131 470 32865468114941767 471 34424701397980648 472 36056209028760579 473 37763262867178866 474 39549282934618873 475 41417838098122189 476 43372653717250688 477 45417623184444424 478 47556809068162082 479 49794451508957226 480 52134981208012736 481 54583021016617744 482 57143395269497956 483 59821144284485824 484 62621526592762500 485 65550029209962410 486 68612383931361886 487 71814570203624701 488 75162826559380157 489 78663668795481359 490 82323893724648756 491 86150591787161118 492 90151167453639908 493 94333343876452475 494 98705176950222201 495 103275078058489400 496 108051819917489724 497 113044552117758105 498 118262826625136771 499 123716604863402752 500 129416275064997135 501 135372680686632517 502 141597129090277183 503 148101410761168729 504 154897831132047174 505 161999220945255471 506 169418957735168174 507 177171001273687841 508 185269906055502859 509 193730845138422589 510 202569649805458606 511 211802824304719087 512 221447572529693832 513 231521842177387340 514 242044342286741188 515 253034572899943430 516 264512874434882545 517 276500448218185007 518 289019389714101643 519 302092743475726985 520 315744527342229774 521 329999769439765040 522 344884569579135911 523 360426127398142030 524 376652783849854185 525 393594089518892250 526 411280837533571864 527 429745109829637865 528 449020353434592996 529 469141418541049187 530 490144610420130081 531 512067774282243654 532 534950339527698994 533 558833377707425442 534 583759697230973635 535 609773894328695497 536 636922418130142935 537 665253675999519121 538 694818092461601378 539 725668181938011890 540 757858666250720480 541 791446542229724361 542 826491163419898485 543 863054370749064633 544 901200570360860087 545 940996825016770367 546 982512999798560383 547 1025821851119360989 548 1070999129433144163 549 1118123741239752479 550 1167277851176824102 551 1218546996998699266 552 1272020270155796841 553 1327790432219705602 554 1385954044114175517 555 1446611666877828941 556 1509867994767883687 557 1575832000009435980 558 1644617156504406129 559 1716341591245916606 560 1791128247026578113 561 1869105131129258725 562 1950405487943414848 563 2035167981286918599 564 2123536971442061352 565 2215662711085875948 566 2311701550232727791 567 2411816244184406847 568 2516176176338281390 569 2624957587899111246 570 2738343920841271734 571 2856526070311759048 572 2979702642819033024 573 3108080337441850905 574 3241874232219350111 575 3381308073591578896 576 3526614700852094158 577 3678036370002500906 578 3835825079018732791 579 4000243039611609745 580 4171563043958004249 581 4350068829359082377 582 4536055603406817047 583 4729830458022419167 584 4931712779151417260 585 5142034830433241627 586 5361142221214405623 587 5589394365844503373 588 5827165133295087799 589 6074843374770597028 590 6332833439573402583 591 6601555897053421741 592 6881448132028618326 593 7172964923037993185 594 7476579245719739025 595 7792782943152640592 596 8122087375099671994 597 8465024310791176387 598 8822146684298103172 599 9194029322159389874 600 9581269936691464753 601 9984489975358839873 602 10404335437406065372 603 10841477977648758877 604 11296615862286798347 605 11770474883904863766 606 12263809589345650775 607 12777404353237098763 608 13312074404472762116 609 13868667190574441061 610 14448063584246606355 611 15051179033162965051 612 15678965077457127912 613 16332410703438629407 614 17012543632868584397 615 17720432009021028591 616 18457185916395509952 617 19223958824378849894 618 20021949462238045936 619 20852403522512982965 620 21716615279033453405 621 22615929670040018736 622 23551744208414529753 623 24525510792771899256 624 25538738023630055261 625 26592993342555296539 626 27689905060962232492 627 28831164933166817529 628 30018530552907313797 629 31253827623322355975 630 32538952817394222027 631 33875876459353801999 632 35266645066212374745 633 36713384525153152003 634 38218303094783538974 635 39783694247585053484 636 41411940201601436600 637 43105515275752521344 638 44866989070642442009 639 46699030391160824658 640 48604410998790648150 641 50586009167442236320 642 52646814042692040821 643 54789929833568449010 644 57018579789537317301 645 59336111041690930822 646 61745999286705512723 647 64251853230681265071 648 66857419968258803374 649 69566590211418684330 650 72383403256973037480 651 75312052959626160723 652 78356893570260191518 653 81522445283945044377 654 84813400875466184931 655 88234632212300518181 656 91791196453043599939 657 95488343414585590521 658 99331522839043930287 659 103326391313250142100 660 107478820451442909693 661 111794904996767710348 662 116280970547796958052 663 120943582642097390663 664 125789555789445512289 665 130825962093000970145 666 136060141336381069450 667 141499711048120118641 668 147152576123178087148 669 153026940018739884515 670 159131315968924397629 671 165474537715147477198 672 172065771936212325115 673 178914530736004420927 674 186030683612536929891 675 193424471251913617019 676 201106519434715767001 677 209087852377946452896 678 217379908046449762564 679 225994553629171010774 680 234944100413390005621 681 244241320773041998201 682 253899465393156224983 683 263932279842157476522 684 274354023424885082440 685 285179488341224012520 686 296424018152032133027 687 308103528692879377281 688 320234529384954935167 689 332834143799125921086 690 345920132859950422182 691 359510918537493719464 692 373625606749292745089 693 388284013095428306424 694 403506689197846033985 695 419314948192200071928 696 435730893274478863520 697 452777446968565152746 698 470478379501753634870 699 488858340458455052613 700 507942891301721088641 701 527758536942534529575 702 548332760843197842162 703 569694061137199834207 704 591871985752024010508 705 614897171324634465446 706 638801383317441711392 707 663617555075835649078 708 689379830974067771823 709 716123610949372141419 710 743885593934429120567 711 772703825677728248741 712 802617748181300113593 713 833668247976227774073 714 865897709127983291883 715 899350068094565319474 716 934070867383358614189 717 970107314285176954144 718 1007508341744974517784 719 1046324667974300817277 720 1086608861536774076218 721 1128415408863619935760 722 1171800780479532872108 723 1216823503104805981824 724 1263544234537640312513 725 1312025837197148491868 726 1362333458001412376470 727 1414534611389423750225 728 1468699260984544938841 729 1524899908061740141852 730 1583211683588824009712 731 1643712438871969101341 732 1706482843537421320661 733 1771606487536027773196 734 1839169981751136528409 735 1909263066488251818320 736 1981978724514123397987 737 2057413292680904172668 738 2135666582050841575977 739 2216842003121985170985 740 2301046689664192365649 741 2388391631691557368264 742 2478991814178639778472 743 2572966354396199838570 744 2670438649103550695135 745 2771536528160239943318 746 2876392406818639211092 747 2985143448615473168237 748 3097931735465111988925 749 3214904436481491509320 750 3336213988238519682957 751 3462018283057009868950 752 3592480856130627276716 753 3727771084958269409929 754 3868064397753085445303 755 4013542480790766804819 756 4164393499044549101852 757 4320812326801046412791 758 4483000777390945023343 759 4651167847222904704921 760 4825529970949506689216 761 5006311275918624072558 762 5193743852074520018205 763 5388068034210655016479 764 5589532683769119960592 765 5798395487282254833598 766 6014923268558135647128 767 6239392300675923886445 768 6472088635966649867486 769 6713308451215986018714 770 6963358393049261895772 771 7222555942703151054041 772 7491229797699925670528 773 7769720254087880705776 774 8058379609644873822079 775 8357572585772273403193 776 8667676750470496124921 777 8989082963927005419525 778 9322195844820261261276 779 9667434238244810238543 780 10025231708102141974368 781 10396037052366150658877 782 10780314820667764017513 783 11178545858289955601890 784 11591227875475203418364 785 12018876019790665648135 786 12462023477086235366625 787 12921222100367300500989 788 13397043042654809057503 789 13890077420734705056771 790 14400937009752362979899 791 14930254942785541732162 792 15478686443881148611880 793 16046909595069567102317 794 16635626109579027496365 795 17245562141230121409057 796 17877469131326019400377 797 18532124663052789609937 798 19210333355101541199317 799 19912927796552383020461 800 20640769490856182881334 801 21394749842255977181590 802 22175791187689688858682 803 22984847839500917302325 804 23822907174188692174317 805 24690990771161099076895 806 25590155564341903659508 807 26521495043633574519565 808 27486140511440060658090 809 28485262354252828477336 810 29520071368358790226283 811 30591820146033284162310 812 31701804479409861698212 813 32851364823006943997421 814 34041887822792423091759 815 35274807865757367589707 816 36551608693208649293289 817 37873825087101617435710 818 39243044580200024221734 819 40660909235349162523922 820 42129117505029977993458 821 43649426118343717643322 822 45223652043125028164669 823 46853674536122042353387 824 48541437224795393551047 825 50288950270669715968829 826 52098292629408245502736 827 53971614347062029606034 828 55911138945028216624613 829 57919165911047734857497 830 59998073231637617711532 831 62150320020891069484921 832 64378449265658296726893 833 66685090617890576817730 834 69072963291876077274099 835 71544879088996027904433 836 74103745476220252520643 837 76752568778634002964418 838 79494457511832863727149 839 82332625775226090319709 840 85270396769534232758990 841 88311206467466180857814 842 91458607353493038581270 843 94716272298732685464361 844 98087998603749485588016 845 101577712119384520475674 846 105189471514824622646834 847 108927472729484013718724 848 112796053513075473302248 849 116799698125969162922214 850 120943042240941424824803 851 125230877944203481477175 852 129668158911202690541996 853 134260005802789942035432 854 139011711773229482429802 855 143928748168589745862212 856 149016770466458460983378 857 154281624341220748720693 858 159729351937030099008316 859 165366198404744071433650 860 171198618579911321808493 861 177233283887132473326340 862 183477089533365245127240 863 189937161859202804098869 864 196620865937229090051976 865 203535813486319115420662 866 210689870962955959454256 867 218091167921993905373357 868 225748105723128669479912 869 233669366435195567823098 870 241863922034685197888619 871 250341043982154310031644 872 259110313019820621322193 873 268181629290171283366396 874 277565222867915547585700 875 287271664538649775072863 876 297311876928187603941870 877 307697146083592594066530 878 318439133329502259205125 879 329549887507226433421103 880 341041857707758218131224 881 352927906311316779888049 882 365221322445169391853787 883 377935835981062144927088 884 391085631874077987450276 885 404685364958258490318272 886 418750175332081337795490 887 433295704123512117962734 888 448338109754344388434011 889 463894084848816367386239 890 479980873564325541869081 891 496616289467564244142730 892 513818734114731015973038 893 531607216100325940609353 894 550001370702307948072278 895 569021480296120951083605 896 588688495289027800984647 897 609024055706111692140995 898 630050513616296735227962 899 651790956135218011010745 900 674269229140788724978987 901 697509961905907920869093 902 721538592370824225051717 903 746381393194500026618078 904 772065498807753584423023 905 798618933174709347273858 906 826070638406367889362904 907 854450504467726098317866 908 883789399669346979289644 909 914119202090533962778610 910 945472832196715133828361 911 977884286324497656533189 912 1011388671185928384875671 913 1046022239676144753155524 914 1081822427640864340342757 915 1118827891758358472742634 916 1157078548844506935767113 917 1196615616218417776359343 918 1237481653287475774370213 919 1279720604685332689143490 920 1323377844581873891834312 921 1368500222326805727422661 922 1415136109788476908204160 923 1463335449986416362489967 924 1513149807183196851292408 925 1564632418825956542654585 926 1617838248916129310727514 927 1672824042975335689990150 928 1729648385030061079878133 929 1788371756171482187392286 930 1849056594862000369620215 931 1911767359444156058851587 932 1976570592386842397241407 933 2043534986442155261090632 934 2112731453205614633045142 935 2184233193590815340890446 936 2258115770394971952300080 937 2334457183486062804172345 938 2413337947099669078665374 939 2494841169423044434568734 940 2579052635039592743251173 941 2666060889696309132555339 942 2755957327574230362273296 943 2848836281678634633228884 944 2944795116787083532854056 945 3043934325135552356768751 946 3146357625508001082326685 947 3252172065140276052765583 948 3361488124620325894795017 949 3474419826499995056135721 950 3591084847003375084263079 951 3711604631012844051718720 952 3836104511103629761038070 953 3964713829983067628339178 954 4097566066516472506762617 955 4234798966167572485574673 956 4376554675182413861244525 957 4522979878696546232066158 958 4674225943656892797618711 959 4830449065856900565216611 960 4991810421264424968012164 961 5158476322599029294877397 962 5330618380428828798219285 963 5508413668962741001278857 964 5692044897567206530620610 965 5881700587245848843109705 966 6077575252256221824296708 967 6279869587967232101568510 968 6488790664166250222967925 969 6704552123984736757905594 970 6927374389628455215382040 971 7157484874088505729725453 972 7395118198998700487792411 973 7640516419910345039799138 974 7893929258130509103273352 975 8155614339281986346522342 976 8425837439949916652611956 977 8704872741527569360933701 978 8993003091414336223932209 979 9290520273027747997536262 980 9597725283711556463129282 981 9914928620683321751586856 982 10242450576590143673847256 983 10580621543720606375190061 984 10929782327009109790159436 985 11290284467511469593140220 986 11662490575369598196585387 987 12046774672389237196091032 988 12443522546031043805199608 989 12853132113799026791461735 990 13276013798140636417910716 991 13712590913784209635554290 992 14163300066468355585848432 993 14628591563162467202242209 994 15108929835841971734803139 995 15604793877739937031442517 996 16116677692161860635462388 997 16645090756069786732573059 998 17190558497329617767819670 999 17753622785690082423293688 1000 18334842439856043905686098