-1 1 0 0 1 3 2 4 3 5 4 10 5 15 6 22 7 29 8 36 9 53 10 72 11 99 12 128 13 160 14 212 15 272 16 354 17 448 18 556 19 703 20 874 21 1096 22 1356 23 1662 24 2050 25 2501 26 3060 27 3716 28 4492 29 5444 30 6550 31 7882 32 9436 33 11262 34 13460 35 16013 36 19034 37 22536 38 26616 39 31450 40 37048 41 43602 42 51164 43 59905 44 70124 45 81905 46 95584 47 111302 48 129368 49 150271 50 174240 51 201861 52 233472 53 269636 54 311158 55 358531 56 412756 57 474544 58 544924 59 625259 60 716516 61 820374 62 938200 63 1071841 64 1223626 65 1395388 66 1589940 67 1809770 68 2058088 69 2338854 70 2655452 71 3012610 72 3414724 73 3867262 74 4376844 75 4949519 76 5593232 77 6315632 78 7125920 79 8035010 80 9053394 81 10194299 82 11470840 83 12898396 84 14494828 85 16277892 86 18269320 87 20491221 88 22969084 89 25732014 90 28809568 91 32237039 92 36051040 93 40293328 94 45011080 95 50252917 96 56075674 97 62539062 98 69710644 99 77666250 100 86484998 101 96257816 102 107080968 103 119062547 104 132323268 105 146990404 106 163208436 107 181131122 108 200929856 109 222795078 110 246929172 111 273559897 112 302930700 113 335311300 114 370999856 115 410314875 116 453612376 117 501274360 118 553722156 119 611419479 120 674863210 121 744605443 122 821240256 123 905420778 124 997863496 125 1099337657 126 1210693412 127 1332847057 128 1466803284 129 1613661622 130 1774604420 131 1950932471 132 2144048724 133 2355487548 134 2586924720 135 2840164619 136 3117185284 137 3420120580 138 3751298472 139 4113256337 140 4508728708 141 4940704866 142 5412409976 143 5927354748 144 6489358034 145 7102536908 146 7771381264 147 8500735608 148 9295863640 149 10162480600 150 11106747706 151 12135369394 152 13255578904 153 14475223332 154 15802809728 155 17247506554 156 18819270292 157 20528839140 158 22387846584 159 24408887913 160 26605533344 161 28992492500 162 31585621588 163 34402075987 164 37460407124 165 40780595406 166 44384264640 167 48294710096 168 52537103156 169 57138631745 170 62128565684 171 67538538817 172 73402609632 173 79757535060 174 86642971320 175 94101588877 176 102179447244 177 110926106934 178 120394996624 179 130643697017 180 141734127866 181 153733048446 182 166712248616 183 180749044582 184 195926678352 185 212334607500 186 230069173736 187 249233911175 188 269940220104 189 292307929636 190 316465734776 191 342552089323 192 370715682080 193 401116354550 194 433925893896 195 469328682787 196 507522894442 197 548721206076 198 593152047084 199 641060712728 200 692710319440 201 748383411154 202 808383008396 203 873034302722 204 942686211012 205 1017712762154 206 1098515264644 207 1185523831788 208 1279199681872 209 1380037294796 210 1488566398388 211 1605354897674 212 1731011072016 213 1866186702432 214 2011580053760 215 2167938688423 216 2336063422450 217 2516811459724 218 2711100648976 219 2919913601113 220 3144301644852 221 3385390163672 222 3644383022216 223 3922568358063 224 4221324257268 225 4542124287059 226 4886544694476 227 5256270603958 228 5653103881816 229 6078970937530 230 6535930427776 231 7026182971665 232 7552079773356 233 8116133278264 234 8721027855908 235 9369630473246 236 10065003810188 237 10810418200936 238 11609366052504 239 12465576420340 240 13383029715020 241 14365975395654 242 15418948439364 243 16546788834371 244 17754661411732 245 19048076009059 246 20432911302684 247 21915437422546 248 23502342280920 249 25200758499438 250 27018290945668 251 28963048779021 252 31043676361708 253 33269388764412 254 35650008252564 255 38196001774107 256 40918523990834 257 43829459350148 258 46941469866680 259 50268044441350 260 53823549748104 261 57623287954008 262 61683553780228 263 66021698667148 264 70656197257380 265 75606716257164 266 80894191768656 267 86540906453391 268 92570575539976 269 99008436205932 270 105881340462358 271 113217858603994 272 121048383270744 273 129405244549952 274 138322829864556 275 147837708878503 276 157988771632752 277 168817368483912 278 180367463895696 279 192685796916859 280 205822048694108 281 219829026579994 282 234762851773872 283 250683164434870 284 267653338063992 285 285740703624604 286 305016794501224 287 325557597410164 288 347443825419004 289 370761203735693 290 395600768884924 291 422059194115558 292 450239124080860 293 480249537528932 294 512206127445894 295 546231699499417 296 582456603629436 297 621019179460470 298 662066237227604 299 705753562337874 300 752246444773604 301 801720250541504 302 854361013174256 303 910366070338497 304 969944732194736 305 1033318983210006 306 1100724237429828 307 1172410122280827 308 1248641319821760 309 1329698450420464 310 1415879001161736 311 1507498322288891 312 1604890663568360 313 1708410284012318 314 1818432618103076 315 1935355501538062 316 2059600483602920 317 2191614194595868 318 2331869807059536 319 2480868572046728 320 2639141434341130 321 2807250758103906 322 2985792127533760 323 3175396267519918 324 3376731063586346 325 3590503686287636 326 3817462856599040 327 4058401212627274 328 4314157829808280 329 4585620871952780 330 4873730380020396 331 5179481241185635 332 5503926293880696 333 5848179629247664 334 6213420064362784 335 6600894796384574 336 7011923287404556 337 7447901330798822 338 7910305369117052 339 8400697036810422 340 8920727939791824 341 9472144730188140 342 10056794422078424 343 10676630029584466 344 11333716498637496 345 12030236947917906 346 12768499287399060 347 13550943155194448 348 14380147267538604 349 15258837151613822 350 16189893281161364 351 17176359695091751 352 18221453034568700 353 19328572109321792 354 20501307961944036 355 21743454455942351 356 23059019481705532 357 24452236710563220 358 25927578026364652 359 27489766603215887 360 29143790662835512 361 30894918022484311 362 32748711358567072 363 34711044337200368 364 36788118581228120 365 38986481517073750 366 41313045232746716 367 43775106267787823 368 46380366512281824 369 49136955186505434 370 52053451957099948 371 55138911345661646 372 58402888347565288 373 61855465469058284 374 65507281158173944 375 69369559700977946 376 73454142768459064 377 77773522530722844 378 82340876583732188 379 87170104671027302 380 92275867291703168 381 97673626415135728 382 103379688220210472 383 109411248148967670 384 115786438268018674 385 122524377054382720 386 129645221868676736 387 137170224037515190 388 145121786888392404 389 153523526746421804 390 162400337042223128 391 171778455845671000 392 181685536755878516 393 192150723554425950 394 203204728653448260 395 214879915529427608 396 227210385520896396 397 240232068935413180 398 253982820949491600 399 268502522363207699 400 283833185452594430 401 300019065375665046 402 317106777101281760 403 335145418437590067 404 354186699262369208 405 374285077263877343 406 395497900742516808 407 417885558477729866 408 441511637350236432 409 466443087876767394 410 492750398048290816 411 520507776137017413 412 549793342525934780 413 580689331388986768 414 613282302452346672 415 647663363332193714 416 683928403254909876 417 722178338280825244 418 762519369027112592 419 805063251216750879 420 849927579681320548 421 897236086796703258 422 947118955563956688 423 999713148534300738 424 1055162753030221572 425 1113619343457324876 426 1175242361899787448 427 1240199517334277557 428 1308667204909232264 429 1380830945902451268 430 1456885849360705160 431 1537037096877669394 432 1621500451008331928 433 1710502789070698706 434 1804282663154678176 435 1903090887603151671 436 2007191155745327268 437 2116860686594959416 438 2232390903637713572 439 2354088146793686124 440 2482274419147283428 441 2617288170622367613 442 2759485119593320672 443 2909239115014762318 444 3066943040497206652 445 3233009762331587878 446 3407873124130649252 447 3591988989435774141 448 3785836335433820716 449 3989918399646130162 450 4204763882108129320 451 4430928206313233159 452 4668994840729146992 453 4919576684719683112 454 5183317521284900376 455 5460893539782991721 456 5753014932657067904 457 6060427568564017078 458 6383914746584319496 459 6724299034620329220 460 7082444195950684672 461 7459257208890089512 462 7855690382704224192 463 8272743575500233865 464 8711466518076109352 465 9172961248697766052 466 9658384664895359972 467 10168951196384828886 468 10705935606119088448 469 11270675924556145280 470 11864576523359703256 471 12489111336032090554 472 13145827230793973564 473 13836347544296840248 474 14562375782644769624 475 15325699497494922792 476 16128194346474637352 477 16971828344751681324 478 17858666318289314968 479 18790874567005380748 480 19770725747540448754 481 20800603987020711648 482 21883010236566541784 483 23020567877471295423 484 24216028590448400306 485 25472278500058242606 486 26792344608355216486 487 28179401528911296505 488 29636778537086253184 489 31167966949660950742 490 32776627848930781368 491 34466600168577307693 492 36241909155491471568 493 38106775227047892532 494 40065623240335718400 495 42123092192142455874 496 44284045371050484552 497 46553580979593040432 498 48937043250441967776 499 51440034077355791932 500 54068425184267433062 501 56828370858851718078 502 59726321273225645044 503 62769036421261518160 504 65963600698497844532 505 69317438153704571496 506 72838328444581172832 507 76534423526098490811 508 80414265107740002044 509 84486802912157234152 510 88761413771324283072 511 93247921600237517142 512 97956618283955325068 513 102898285522564430896 514 108084217674683206492 515 113526245644276267565 516 119236761860153399224 517 125228746392997316748 518 131515794264750768040 519 138112144000996403226 520 145032707481830862420 521 152293101152091072090 522 159909678647006689836 523 167899564900707652741 524 176280691800619903396 525 185071835456480405572 526 194292655158956882672 527 203963734097856568642 528 214106621922842711988 529 224743879225022389579 530 235899124024444709028 531 247597080355860777528 532 259863629039931006512 533 272725860741828692992 534 286212131414539663716 535 300352120231991807326 536 315176890125706700384 537 330718951033401411558 538 347012325984848806476 539 364092620145655407133 540 381997092948834287108 541 400764733454085076158 542 420436339069419175872 543 441054597789094329856 544 462664174097293961492 545 485311798697865196062 546 509046362242225951672 547 533919013222393649906 548 559983260218241986176 549 587295078683833230070 550 615913022470537937948 551 645898340298560110263 552 677315097383622440448 553 710230302451003744212 554 744714040365321779356 555 780839610619685542888 556 818683671944268528360 557 858326393290023292028 558 899851611472528307000 559 943346995757872745002 560 988904219690534428164 561 1036619140482636818724 562 1086591986280471028688 563 1138927551657928442760 564 1193735401684456062312 565 1251130084936566956008 566 1311231355844945316656 567 1374164406766884678241 568 1440060110212815097464 569 1509055271655129502542 570 1581292893372990160832 571 1656922449814077878500 572 1736100174953604503656 573 1818989362176079583316 574 1905760677206804881288 575 1996592484650418144213 576 2091671188726220702714 577 2191191588791630585066 578 2295357250297480830380 579 2404380891823054171870 580 2518484788874955799632 581 2637901195172510763104 582 2762872782146988328172 583 2893653097442804873410 584 3030507043216533013040 585 3173711375072786236492 586 3323555222522046219140 587 3480340631854081598004 588 3644383132391451543696 589 3816012327099795507048 590 3995572508583281044596 591 4183423301548465196670 592 4379940332833549506792 593 4585515930182674012132 594 4800559850962932534804 595 5025500042083588504490 596 5260783432442502266992 597 5506876759245081594760 598 5764267429637715345568 599 6033464419123129893464 600 6314999208299102655574 601 6609426759540283777154 602 6917326535271511855376 603 7239303559594192630690 604 7575989525062204048864 605 7928043946492492270279 606 8296155363789227091192 607 8681042595799535709215 608 9083456047351583700216 609 9504179071672473786048 610 9944029390489845700072 611 10403860574233298936804 612 10884563584804138709352 613 11387068383537901109444 614 11912345607045540696904 615 12461408313746873358732 616 13035313804044410409600 617 13635165517154666447528 618 14262115007797568680892 619 14917364006024339257591 620 15602166563617529037784 621 16317831290658228815658 622 17065723685945061588968 623 17847268565165952442762 624 18663952590826158597604 625 19517326908120145672363 626 20409009891128444226144 627 21340690003835746531863 628 22314128780722008780336 629 23331163931808966582376 630 24393712577265673566668 631 25503774616908937735120 632 26663436240081175875096 633 27874873581690270087760 634 29140356530361373167140 635 30462252694916513931241 636 31843031535676722060852 637 33285268667266850548312 638 34791650339960780956648 639 36364978106812703351637 640 38008173684139886328456 641 39724284013257331615822 642 41516486531597894402592 643 43388094661775061803171 644 45342563527405823713440 645 47383495904895516654742 646 49514648420789005711712 647 51739938004584327041680 648 54063448607407446200932 649 56489438197270924034668 650 59022346042101527420924 651 61666800292205439338297 652 64427625874203151766360 653 67309852709062946854780 654 70318724267264085802700 655 73459706474676617683545 656 76738496983325806367940 657 80161034821660057462738 658 83733510439650687866432 659 87462376164549355569387 660 91354357083797295096780 661 95416462372278714284198 662 99655997081668090517720 663 104080574410465080981456 664 108698128473924209940816 665 113516927593890190156548 666 118545588129388743620348 667 123793088869509710887859 668 129268786011123864936800 669 134982428744729174162884 670 140944175472688668038880 671 147164610685130306926106 672 153654762519623612835860 673 160426121031944408653650 674 167490657206164206447488 675 174860842733462616327017 676 182549670590272689335094 677 190570676447404551449012 678 198937960943218794431520 679 207666212855053319536496 680 216770733204503749511716 681 226267460333613074278362 682 236172995990293193484096 683 246504632463001602584956 684 257280380806079381326480 685 268519000198834652822864 686 280240028483203969732968 687 292463813926371199627894 688 305211548256752220931072 689 318505301023439870752068 690 332368055331219612848280 691 346823745005365853465150 692 361897293242314383896992 693 377614652804727353298168 694 394002847821519570567800 695 411090017255836604780867 696 428905460106495875540880 697 447479682410696033855872 698 466844446118689488125728 699 487032819913607138104554 700 508079232052532550359564 701 530019525307948733897712 702 552891014091467654993984 703 576732543845202214069708 704 601584552789166990682892 705 627489136116585300341550 706 654490112732611547081508 707 682633094635358899224452 708 711965559042241246700436 709 742536923368306018990738 710 774398623167424137698312 711 807604193151560084276497 712 842209351407441345219056 713 878272086934865361061496 714 915852750635321128344744 715 955014149884628773593109 716 995821646828525408698044 717 1038343260545082024846792 718 1082649773223710711704768 719 1128814840515888078363869 720 1176915106218748485806786 721 1227030321458964920226404 722 1279243468550325309283924 723 1333640889705427848837709 724 1390312420788399784519812 725 1449351530302770622865708 726 1510855463816138520391918 727 1574925394030499572501431 728 1641666576715487922214824 729 1711188512729592791030513 730 1783605116363079138735176 731 1859034890245333938581368 732 1937601107068080278797144 733 2019431998385905964168344 734 2104660950764975156821620 735 2193426709561166698890519 736 2285873590619656397760016 737 2382151700198466710518384 738 2482417163430452669395560 739 2586832361649536708641830 740 2695566178919428922972656 741 2808794258115967781063324 742 2926699266926862443799048 743 3049471174146879170848946 744 3177307536660160242162296 745 3310413797516235045258928 746 3449003595521719130594276 747 3593299086784905247853589 748 3743531278667473979726712 749 3899940376613953295035528 750 4062776144347350126551482 751 4232298277937842819054970 752 4408776794269696805147528 753 4592492434451882664239274 754 4783737082737573813174880 755 4982814201538983475423876 756 5190039283146082014728332 757 5405740318779674494489024 758 5630258285633559847967360 759 5863947652584131311014714 760 6107176905271222341976344 761 6360329091280397138379946 762 6623802386183203978273292 763 6898010681220827199007398 764 7183384193444918557541880 765 7480370099159796411530568 766 7789433191541739314173224 767 8111056563342651621530436 768 8445742315619866043126696 769 8794012293467812241624962 770 9156408849763603703795456 771 9533495637976262797433400 772 9925858435127099843691612 773 10334105996029881378581412 774 10758870939980092341360344 775 11200810671105967733251236 776 11660608333638938539949128 777 12138973803406381826866064 778 12636644716898577854306308 779 13154387539310443733233634 780 13692998673010377504865492 781 14253305607942210045443848 782 14836168115520387824844256 783 15442479487636913537938479 784 16073167822456770242549506 785 16729197358740311234416944 786 17411569860495110145378492 787 18121326053824472801593410 788 18859547117909384525979680 789 19627356232130219674589190 790 20425920181408186503666024 791 21256451021922805608038536 792 22120207809439029210188316 793 23018498392560457692591648 794 23952681273308180947996300 795 24924167537512559001537969 796 25934422857596224442870912 797 26984969570418898906995300 798 28077388832953243614441328 799 29213322858660121212942590 800 30394477237536242992548872 801 31622623342915549188235122 802 32899600828215825826392672 803 34227320216939434062503542 804 35607765589355318059286128 805 37042997369414029419208444 806 38535155215576559986175472 807 40086461019369149972241849 808 41699222015615869883558044 809 43375834008441810417657902 810 45118784717288013422139256 811 46930657247332891693676838 812 48814133688871477960236408 813 50771998850369895766277416 814 52807144130080507076268936 815 54922571531279661962183245 816 57121397826372748797436404 817 59406858875297790574758656 818 61782314103856233488999880 819 64251251147799732132995306 820 66817290668711640037259444 821 69484191347939289356381484 822 72255855065055256272449040 823 75136332267560389630388139 824 78129827538779636652072100 825 81240705371151264813991410 826 84473496152368497742614912 827 87832902372096903452319708 828 91323805057269535766666400 829 94951270444245288045039094 830 98720556896412510851703888 831 102637122076127026700228572 832 106706630380188061265694560 833 110934960648386516377621240 834 115328214154997075055751448 835 119892722893437960660512125 836 124635058164686925109489424 837 129562039480415785208446744 838 134680743792198623011750068 839 139998515058549376398064198 840 145522974161962916863358012 841 151262029188566784612500337 842 157223886083434836817856328 843 163417059695080151277396690 844 169850385223120429264204504 845 176533030083605721984553373 846 183474506207012281393705464 847 190684682784433743334907923 848 198173799478053689836149408 849 205952480112548705642550418 850 214031746864660208762793196 851 222423034968783075928102066 852 231138207957045144992649384 853 240189573453007164506704092 854 249589899538783380691642136 855 259352431716081669908151313 856 269490910482385174288159088 857 280019589544240216213753696 858 290953254690392168832208728 859 302307243348306474095065787 860 314097464848440296302979664 861 326340421421487357970905132 862 339053229954699442908293568 863 352253644534308504509303846 864 365960079802016551079565130 865 380191635154501980186022788 866 394968119815906519758403392 867 410310078814311191169503117 868 426238819894299821238717088 869 442776441398826506079229684 870 459945861154765994995668768 871 477770846397728668097878280 872 496276044772959071935414544 873 515487016450427522153992978 874 535430267393548540546559936 875 556133283822336367417173691 876 577624567913231654888400376 877 599933674779298795799092228 878 623091250776020584208101632 879 647129073179484948248358936 880 672080091285387575649638484 881 697978468978959265223401934 882 724859628827661515792269116 883 752760297750300520637381032 884 781718554318065629124440776 885 811773877744925600033294574 886 842967198626809227975489480 887 875340951491049540650449684 888 908939129219707140834029744 889 943807339412583898390135364 890 979992862758017304702246664 891 1017544713481902745309879911 892 1056513701947818727456885644 893 1096952499483655407705657248 894 1138915705512743216929939824 895 1182459917070172488869466579 896 1227643800787780874531090644 897 1274528167434155614116614628 898 1323176049098981647967229264 899 1373652779114135696956017544 900 1426026074807109861280259702 901 1480366123185639853137867276 902 1536745669655804998554284856 903 1595240109879391594488971582 904 1655927584879937593001885468 905 1718889079510636703942187798 906 1784208524401167532358844848 907 1851972901504520280251360172 908 1922272353369054872296402528 909 1995200296265307383200523316 910 2070853537301501201363737272 911 2149332395666308959956599625 912 2230740828142142591652022264 913 2315186559037160301449897920 914 2402781214689235722840692376 915 2493640462700374245460612306 916 2587884156065477860414074044 917 2685636482364944299110299368 918 2787026118196380822172683624 919 2892186389026680191755212224 920 3001255434651888071758463184 921 3114376380458680682553789574 922 3231697514687860234405063588 923 3353372471907109630755739388 924 3479560422907287017094445824 925 3610426271243830996347415124 926 3746140856652382114976258604 927 3886881165575496679120381603 928 4032830549045385743743797724 929 4184178948175912366039458410 930 4341123127525674503808238904 931 4503866916602882792373990682 932 4672621459791902974188809608 933 4847605474990827623164279080 934 5029045521259225323113852672 935 5217176275785343218465083273 936 5412240820492504650087853604 937 5614490938615238656210524158 938 5824187421586863614556588048 939 6041600386591774647471048466 940 6267009605147614759971853720 941 6500704843094837259111268588 942 6742986212383883310097504400 943 6994164535063370785626506466 944 7254561719886267303623492716 945 7524511151965068853931823160 946 7804358095921520551408789104 947 8094460112991389770985123738 948 8395187492560308253669741864 949 8706923698622684127598481976 950 9030065831672221356058093256 951 9365025106549668658528005087 952 9712227346791045092113538136 953 10072113496037836777017750844 954 10445140147089471031594377060 955 10831780089197832267457956883 956 11232522874223685325113714760 957 11647875402295610134085654112 958 12078362527633516564565922840 959 12524527685220939353716884861 960 12986933539033200339211329188 961 13466162652552167399199747387 962 13962818182322731452083943904 963 14477524595331363830000699568 964 15010928411013142531582647940 965 15563698968720547035308806478 966 16136529221515117960929842448 967 16730136557171756634427194771 968 17345263647315110144019637796 969 17982679325638083072089502060 970 18643179496184148059649240336 971 19327588072707796624278226041 972 20036757950161178201517134912 973 20771572009389840397909233588 974 21532944156156437473898899180 975 22321820395648439233136915593 976 23139179943664254789527621156 977 23986036375711786972700323784 978 24863438815294387532266498112 979 25772473162701418828637840386 980 26714263365664279686948677098 981 27689972733283831379293757542 982 28700805294681669747128104276 983 29748007203875779859406541070 984 30832868192430706137112057188 985 31956723071483623697106001860 986 33120953284800620319195309712 987 34326988514572102857383649342 988 35576308341712691888519649584 989 36870443962489187971446719736 990 38210979963360348806995501428 991 39599556155974329109331696632 992 41037869474333719576535041304 993 42527675936204360967646931308 994 44070792670912426836203279104 995 45669100015744849300545806930 996 47324543683241033540578834176 997 49039137001738990686268939264 998 50814963231616718831810318840 999 52654177959749800543479272758 1000 54559011574788968759767591172