0 1 1 1 2 2 3 4 4 7 5 11 6 19 7 28 8 41 9 62 10 87 11 120 12 170 13 228 14 303 15 408 16 534 17 689 18 899 19 1145 20 1449 21 1842 22 2306 23 2863 24 3571 25 4398 26 5386 27 6610 28 8039 29 9716 30 11775 31 14157 32 16938 33 20293 34 24166 35 28643 36 33995 37 40134 38 47199 39 55540 40 65088 41 75994 42 88776 43 103328 44 119886 45 139126 46 160967 47 185681 48 214228 49 246488 50 282878 51 324627 52 371675 53 424509 54 484824 55 552552 56 628391 57 714498 58 810937 59 918531 60 1040198 61 1176033 62 1327191 63 1497358 64 1686880 65 1897160 66 2133058 67 2395056 68 2685084 69 3009229 70 3368458 71 3765104 72 4207071 73 4695669 74 5234039 75 5832054 76 6491840 77 7217212 78 8020817 79 8905478 80 9876289 81 10948908 82 12127533 83 13418385 84 14841273 85 16401742 86 18107938 87 19984225 88 22038425 89 24280491 90 26740987 91 29430058 92 32360555 93 35569879 94 39071817 95 42882150 96 47047331 97 51584995 98 56515313 99 61894796 100 67746898 101 74096326 102 81012662 103 88525623 104 96666459 105 105519494 106 115123401 107 125516343 108 136801441 109 149027169 110 162241524 111 176568856 112 192071169 113 208806968 114 226927320 115 246509430 116 267626261 117 290459093 118 315105419 119 341653868 120 370323550 121 401234919 122 434497605 123 470373490 124 509012923 125 550548875 126 595296182 127 643439165 128 695141282 129 750777292 130 810575247 131 874732815 132 943698186 133 1017749211 134 1097127302 135 1182364280 136 1273801040 137 1371728334 138 1476779441 139 1589367134 140 1709844789 141 1838961341 142 1977219266 143 2125042757 144 2283319853 145 2452655977 146 2633564110 147 2827090790 148 3033968237 149 3254809966 150 3490852518 151 3742973779 152 4011911813 153 4299119438 154 4605651927 155 4932389352 156 5281042443 157 5652870127 158 6048926372 159 6471215102 160 6921241861 161 7400259444 162 7910619330 163 8454109923 164 9032224891 165 9647711516 166 10302698301 167 10998954487 168 11739693860 169 12527434332 170 13364277295 171 14253967976 172 15199489002 173 16203321661 174 17269834073 175 18402541614 176 19604380673 177 20880428378 178 22234831590 179 23671046468 180 25194978843 181 26811499325 182 28524682678 183 30341376834 184 32267304851 185 34307248950 186 36469154740 187 38759720805 188 41184566246 189 43752882445 190 46472512713 191 49350033503 192 52396082397 193 55619810436 194 59028919679 195 62635688991 196 66450798102 197 70483235366 198 74747178218 199 79255049136 200 84017343313 201 89050392155 202 94368646613 203 99984321654 204 105916230984 205 112181136787 206 118793261497 207 125774232041 208 133143489795 209 140917544197 210 149121256614 211 157777118627 212 166904298581 213 176531319049 214 186684192889 215 197385116025 216 208666811307 217 220559294469 218 233088267875 219 246291201456 220 260202719291 221 274852513629 222 290283486729 223 306535492843 224 323642827148 225 341654526722 226 360616452103 227 380568128948 228 401565597257 229 423661521414 230 446901444915 231 471349310775 232 497065574947 233 524102609250 234 552533354394 235 582427082248 236 613844001838 237 646867196989 238 681576007742 239 718039520051 240 756352343774 241 796605199142 242 838877332789 243 883276332627 244 929905879229 245 978856714875 246 1030251150136 247 1084207494916 248 1140829614849 249 1200256374498 250 1262622708510 251 1328047315610 252 1396687804249 253 1468697847722 254 1544213032192 255 1623412020623 256 1706469740824 257 1793540841195 258 1884827780138 259 1980529403927 260 2080822016903 261 2185934783963 262 2296093626355 263 2411499258767 264 2532410970303 265 2659085112770 266 2791750081394 267 2930698938851 268 3076222415298 269 3228580057913 270 3388102964075 271 3555120461825 272 3729927353627 273 3912897331608 274 4104403239944 275 4304779508239 276 4514447731249 277 4733829549813 278 4963304152578 279 5203346713329 280 5454433792517 281 5716994834425 282 5991565179288 283 6278682893500 284 6578834070532 285 6892621277319 286 7220651700164 287 7563474960236 288 7921769004711 289 8296218323829 290 8687444024879 291 9096208206120 292 9523282095616 293 9969366865322 294 10435318825296 295 10922006097160 296 11430219813002 297 11960921351831 298 12515087385230 299 13093609663399 300 13697567037426 301 14328057313804 302 14986085121087 303 15672860185565 304 16389615807087 305 17137482713605 306 17917816783896 307 18732002353170 308 19581311396186 309 20467262439368 310 21391408518140 311 22355179232521 312 23360274520050 313 24408435257179 314 25501267325924 315 26640672348357 316 27828600750164 317 29066854918012 318 30357561149932 319 31702902922694 320 33104902073689 321 34565934467600 322 36088443235253 323 37674694563309 324 39327341983187 325 41049117091322 326 42842558612559 327 44710628222332 328 46656378507647 329 48682651294343 330 50792750700955 331 52990085582782 332 55277835403423 333 57659683953644 334 60139436021741 335 62720646160736 336 65407419659210 337 68204000320730 338 71114360001545 339 74143070850901 340 77294863987349 341 80574174404600 342 83986092002513 343 87535887704841 344 91228511108082 345 95069625054228 346 99065099022786 347 103220453162670 348 107541985049745 349 112036226516319 350 116709330906994 351 121568297608328 352 126620392113059 353 131872469099075 354 137332304627919 355 143007975267984 356 148907113191852 357 155038352483831 358 161410667159329 359 168032549664070 360 174913582678400 361 182063731492991 362 189492441224775 363 197210341606436 364 205228493597668 365 213557395379682 366 222208833207218 367 231195077196788 368 240527790458592 369 250220034681567 370 260285415126342 371 270736881435221 372 281588902797012 373 292856556612015 374 304554214198457 375 316697895644280 376 329304302371053 377 342389374368814 378 355970841662177 379 370067194728392 380 384696105238974 381 399877185896142 382 415630899003018 383 431976825250370 384 448936651178158 385 466533009417888 386 484787586072231 387 503724349244098 388 523368321444499 389 543743507692393 390 564876387096278 391 586794610531444 392 609524738124425 393 633096009346121 394 657538966691389 395 682882982027990 396 709160330293818 397 736404731640127 398 764648653224980 399 793927704245404 400 824279097708895 401 855738704169554 402 888345796426716 403 922141422827358 404 957165197103581 405 993460413166127 406 1031072331683943 407 1070044678845214 408 1110425163323169 409 1152263667464414 410 1195608436467387 411 1240512021069750 412 1287029375491894 413 1335213705777512 414 1385122874477221 415 1436817396263010 416 1490355923918876 417 1545802141768995 418 1603222661732246 419 1662682111062134 420 1724250555643907 421 1788001287126414 422 1854005487078443 423 1922340210622952 424 1993086068178077 425 2066321425013975 426 2142130991882761 427 2220603391408233 428 2301824863443680 429 2385888497359439 430 2472891687707298 431 2562929298680345 432 2656103590494607 433 2752521553926216 434 2852287499382308 435 2955513716939739 436 3062317695840118 437 3172814084569247 438 3287126143559705 439 3405382838893400 440 3527710133479605 441 3654243277655058 442 3785123784429579 443 3920489990461661 444 4060490250902331 445 4205279785388014 446 4355010462899859 447 4509844951919075 448 4669953446123971 449 4835502603148618 450 5006670724787114 451 5183644351921528 452 5366606303840298 453 5555751946215461 454 5751285666180292 455 5953407932623168 456 6162332736273371 457 6378283934392219 458 6601481270343894 459 6832159050998527 460 7070562374527816 461 7316932019098197 462 7571524451949480 463 7834607930005595 464 8106446186521323 465 8387319845648217 466 8677522412694649 467 8977342655951759 468 9287087532331265 469 9607078057538337 470 9937630301406064 471 10279079908376375 472 10631777867568791 473 10996070004721866 474 11372323215630520 475 11760921127509899 476 12162241994333261 477 12576686737310355 478 13004674521324025 479 13446618920919007 480 13902957900114548 481 14374149297305922 482 14860645154737167 483 15362923743279835 484 15881484984127584 485 16416822791480317 486 16969459290773260 487 17539940172174737 488 18128804923582714 489 18736623360866294 490 19363990947125357 491 20011496746575019 492 20679762432235815 493 21369437568142843 494 22081165143542298 495 22815623191297530 496 23573520074142729 497 24355557407211082 498 25162474471365078 499 25995043503623805 500 26854029847808531 501 27740239313053697 502 28654513516653766 503 29597687045535063 504 30570637965022766 505 31574283218315896 506 32609532617137440 507 33677342668664410 508 34778712088151135 509 35914632373267567 510 37086145177663942 511 38294337946757577 512 39540290868707380 513 40825137982008781 514 42150063000714794 515 43516242365370347 516 44924910339807820 517 46377355041450806 518 47874857356473420 519 49418760234956812 520 51010465004229479 521 52651365837621763 522 54342923531178987 523 56086662122407461 524 57884098644849548 525 59736821619987990 526 61646488073880127 527 63614748227463445 528 65643329017507868 529 67734031541858013 530 69888650382168132 531 72109062415705927 532 74397224796749531 533 76755088517392409 534 79184692858031524 535 81688163946072358 536 84267622212900175 537 86925282774283383 538 89663454690944560 539 92484441878216409 540 95390649802030040 541 98384585496241178 542 101468751537997421 543 104645759382646482 544 107918330282220187 545 111289181828739010 546 114761148356750873 547 118337182832108346 548 122020235525387586 549 125813381841046186 550 129719825344152780 551 133742768007285395 552 137885545940281635 553 142151633640314461 554 146544505317975465 555 151067778926357727 556 155725221830451362 557 160520602588165611 558 165457843801808350 559 170541029311628657 560 175774245874940216 561 181161745284364752 562 186707953311551503 563 192417300584285342 564 198294394548758448 565 204344030291569524 566 210571009990206434 567 216980325211530013 568 223577169871617223 569 230366747475635791 570 237354464389698698 571 244545945095941937 572 251946826519181156 573 259562962815913074 574 267400443222854120 575 275465372593904363 576 283764088411387746 577 292303181416675625 578 301089261566994017 579 310129187869764593 580 319430092138103146 581 328999129390951344 582 338843721287268969 583 348971583230005680 584 359390458321841430 585 370108375063271773 586 381133678201264319 587 392474745150320261 588 404140258808229091 589 416139242413975404 590 428480757438929604 591 441174192256458021 592 454229301462865205 593 467655884020995047 594 481464088722123021 595 495664458282288297 596 510267586627001996 597 525284441957472458 598 540726416139706260 599 556604959772197698 600 572931923887952419 601 589719615006994385 602 606980406743613250 603 624727101037432082 604 642972989459361862 605 661731439845623257 606 681016278194512438 607 700841856659690314 608 721222613819035546 609 742173478219711159 610 763709943731723453 611 785847601771888009 612 808602567744948177 613 831991564261379803 614 856031423760743776 615 880739538929636496 616 906133954554566809 617 932232838676976094 618 959054958354298299 619 986619780732624104 620 1014946910997088654 621 1044056594668522066 622 1073969828773176142 623 1104707764510568660 624 1136292237581783628 625 1168745890133660794 626 1202091536212959489 627 1236352721436617019 628 1271553856704674668 629 1307719544131809950 630 1344875167697415494 631 1383047039515369378 632 1422261684092319713 633 1462546461392897890 634 1503929726793255566 635 1546440071103260260 636 1590106977844371958 637 1634960997796235981 638 1681032942386279540 639 1728354576752436002 640 1776958810159599257 641 1826878839920211045 642 1878148882208394880 643 1930804379388875139 644 1984881091801622089 645 2040415868049162790 646 2097446870689615100 647 2156012612743236661 648 2216152769598639528 649 2277908424264468744 650 2341321045633393986 651 2406433343898377745 652 2473289537006083332 653 2541934267195185565 654 2612413502263557416 655 2684774824590418435 656 2759066282664046318 657 2835337340270042528 658 2913639189934829591 659 2994023535585924701 660 3076543592214249398 661 3161254425308423208 662 3248211661004825616 663 3337472538482810794 664 3429096277478181409 665 3523142711656348724 666 3619673396531487185 667 3718752006851365726 668 3820442889151016023 669 3924812227660261573 670 4031928473912991341 671 4141860813773514760 672 4254680394375873177 673 4370460787993904887 674 4489276369059154950 675 4611203604819626007 676 4736321556129307178 677 4864710159260416618 678 4996451583590760878 679 5131630771624742025 680 5270333620637680801 681 5412648410331075064 682 5558666385079389776 683 5708479829665039694 684 5862183570498913859 685 6019875602715122655 686 6181655054516802388 687 6347623765167846359 688 6517886960296270345 689 6692551098514110412 690 6871725530089489135 691 7055523223440156149 692 7244058487973758536 693 7437448716925446360 694 7635815168812223537 695 7839280559505446821 696 8047970893491469335 697 8262016303664900787 698 8481548505940723209 699 8706702722725619182 700 8937618585278350169 701 9174437443173322522 702 9417304384609842349 703 9666369205150941762 704 9921783564646779634 705 10183703108496241295 706 10452288507515670266 707 10727702453862104967 708 11010111888261877878 709 11299689115306092542 710 11596608630216877296 711 11901049456524201340 712 12213196342115577495 713 12533236407529433515 714 12861361599512806263 715 13197769972665010469 716 13542662150279099599 717 13896243898650706802 718 14258727500270808481 719 14630328016965227942 720 15011265990837093997 721 15401768914470624719 722 15802067286484169216 723 16212397444381600433 724 16633003138420630686 725 17064131368309572730 726 17506035354350945667 727 17958976221123252178 728 18423218604432274262 729 18899033766458750157 730 19386701396682847223 731 19886504976725344335 732 20398735046414810038 733 20923691128852918043 734 21461676841159325196 735 22013003317639335198 736 22577991267299646974 737 23156965816931835515 738 23750260098850285854 739 24358217448591200663 740 24981185967150721540 741 25619522279998107704 742 26273593884237435102 743 26943773415108544208 744 27630442584340315480 745 28333994685435845940 746 29054828549966930847 747 29793352672529008035 748 30549987884484166580 749 31325160983712156048 750 32119309054869520534 751 32932882321305125888 752 33766337432390609630 753 34620141986921655258 754 35494777574709026552 755 36390732703577013256 756 37308507535316440958 757 38248617127829985967 758 39211583984364870832 759 40197943010472886622 760 41208244969505917377 761 42243048634483295913 762 43302925976219938172 763 44388465844318243528 764 45500265702540682572 765 46638937057221220116 766 47805109378006309018 767 48999421395291546232 768 50222526779856504288 769 51475098316905373170 770 52757818744591172499 771 54071386694723440722 772 55416521135965965935 773 56793951729978160130 774 58204425044967737962 775 59648709283150663537 776 61127584131552987896 777 62641847259038506025 778 64192319345632291805 779 65779833402306407832 780 67405241564141611536 781 69069420438372035313 782 70773259868040373902 783 72517670032726989708 784 74303587134841125598 785 76131961579071315809 786 78003765394320454008 787 79919998277034893010 788 81881675158958368826 789 83889833962561883366 790 85945542023056740971 791 88049883013809792857 792 90203965049948670622 793 92408927509952693328 794 94665927288652976737 795 96976147262211774888 796 99340803533312559219 797 101761130978313522911 798 104238392089356052404 799 106773884666368203104 800 109368926625486136954 801 112024865232498075842 802 114743085268297555954 803 117524993062077943743 804 120372026133007551538 805 123285661854905370716 806 126267400678315923201 807 129318776195693428281 808 132441364334774928381 809 135636765729716815834 810 138906616227893926636 811 142252596640607671068 812 145676414224129266077 813 149179813644488747892 814 152764587318113389374 815 156432555959354136763 816 160185580022701890974 817 164025570665151863117 818 167954469317475727103 819 171974259621400913087 820 176086979049725404682 821 180294697454055654156 822 184599529517802389187 823 189003647069271741798 824 193509256559244559041 825 198118612048551488405 826 202834028253985364707 827 207657856904270786091 828 212592500284524331724 829 217640425053984614250 830 222804137429533856299 831 228086197307159164279 832 233489232895546247700 833 239015914671135318353 834 244668970100422515444 835 250451199132557200199 836 256365446870587435972 837 262414618916157339623 838 268601697769710264291 839 274929714156960187438 840 281401763021442160087 841 288021020880076101847 842 294790715744650453377 843 301714143785246006920 844 308794687694756037781 845 316035785139066439056 846 323440946118582347102 847 331013772394538787295 848 338757924402335639697 849 346677139335725729860 850 354775251693983261261 851 363056158586359696922 852 371523838568047937658 853 380182373366553628285 854 389035911505961214647 855 398088687920849948181 856 407345046927002239504 857 416809404087283368628 858 426486266634546751159 859 436380257751062560719 860 446496076598459322606 861 456838519577569594377 862 467412505988376605341 863 478223036139095539353 864 489275213476012888923 865 500574271694950830600 866 512125530845270962314 867 523934420359546829353 868 536006507695564756991 869 548347452343058278065 870 560963029788381834424 871 573859161765380327574 872 587041868073462841995 873 600517291509024684436 874 614291729812094908159 875 628371585195708164656 876 642763390281550624184 877 657473841828774880992 878 672509747875453135140 879 687878054712182903111 880 703585882488603230639 881 719640469858511559661 882 736049202031358822687 883 752819648351590993050 884 769959504339756238050 885 787476620857700444204 886 805379043765792152883 887 823674953242606188083 888 842372694106235002663 889 861480817654063743334 890 881008018144230433720 891 900963164311131841542 892 921355343503250804849 893 942193795199192639131 894 963487943762387900526 895 985247444992066784236 896 1007482116547337757630 897 1030201971981578545825 898 1053417269833367979024 899 1077138440820848020504 900 1101376123203502253291 901 1126141214539647976202 902 1151444795514105441648 903 1177298166670272583746 904 1203712902973315142450 905 1230700774122007807994 906 1258273782701733434515 907 1286444221692597886347 908 1315224591117114554888 909 1344627637659532347083 910 1374666415271456525395 911 1405354197994118789238 912 1436704521097775435223 913 1468731244937732999635 914 1501448463790633173836 915 1534870548561908281246 916 1569012214059582029138 917 1603888423670334136783 918 1639514433691885332110 919 1675905864192370521067 920 1713078599352428941946 921 1751048833473315877106 922 1789833145605410419141 923 1829448395368021058017 924 1869911770693326175846 925 1911240866408057698196 926 1953453575343226193349 927 1996568137867674980553 928 2040603224624020897997 929 2085577822724833929350 930 2131511287139246334415 931 2178423427785050957263 932 2226334390608526645402 933 2275264710880849608328 934 2325235404866484533783 935 2376267845566898501690 936 2428383817993826041826 937 2481605615635407069226 938 2535955910644712112227 939 2591457811149632876128 940 2648134962757637249250 941 2706011412952011607414 942 2765111670509264560590 943 2825460812285112531883 944 2887084341581852668367 945 2950008249736149680933 946 3014259128449859091621 947 3079864021872933189181 948 3146850490436299358150 949 3215246728993141353585 950 3285081412361939274294 951 3356383761470660538543 952 3429183667596958385815 953 3503511531095744075278 954 3579398329933297242965 955 3656875750317031501465 956 3735976018332194353901 957 3816731970935679919474 958 3899177193290686956466 959 3983345843015449381711 960 4069272723719350950966 961 4156993429360551494375 962 4246544160810019203607 963 4337961802003215652432 964 4431284071665177507300 965 4526549331869693438690 966 4623796666893453168371 967 4723066042656636058308 968 4824398106957469153207 969 4927834271105612118189 970 5033416877454415516636 971 5141188990966202637651 972 5251194483716342032858 973 5363478210897637132284 974 5478085793371831559273 975 5595063705124678210761 976 5714459458153252111349 977 5836321375632952708038 978 5960698682419505547932 979 6087641699234826170615 980 6217201606078502000904 981 6349430535860840310423 982 6484381778335860634380 983 6622109533358431725752 984 6762669007748814553044 985 6906116629426594905491 986 7052509790114302933782 987 7201906945521607099993 988 7354367840169583137478 989 7509953239111861187232 990 7668725031543479555194 991 7830746466811019692159 992 7996081874722188045905 993 8164796772671361867302 994 8336958113369213186170 995 8512633993279521776518 996 8691893763371293975003 997 8874808289108917663946 998 9061449646554899112765 999 9251891236844398285291 1000 9446208059017489020969