0 0 1 0 2 1 3 1 4 2 5 2 6 5 7 5 8 8 9 11 10 17 11 20 12 29 13 37 14 51 15 65 16 85 17 106 18 141 19 175 20 223 21 277 22 351 23 432 24 540 25 663 26 820 27 999 28 1226 29 1489 30 1817 31 2192 32 2654 33 3191 34 3847 35 4603 36 5517 37 6578 38 7853 39 9327 40 11084 41 13120 42 15533 43 18328 44 21621 45 25430 46 29905 47 35071 48 41111 49 48080 50 56206 51 65554 52 76420 53 88918 54 103394 55 120015 56 139214 57 161222 58 186593 59 215632 60 249006 61 287165 62 330938 63 380888 64 438075 65 503255 66 577713 67 662459 68 759105 69 868933 70 993978 71 1135894 72 1297168 73 1479984 74 1687435 75 1922241 76 2188293 77 2489083 78 2829378 79 3213635 80 3647768 81 4137365 82 4689803 83 5312116 84 6013337 85 6802385 86 7690431 87 8688516 88 9810514 89 11070228 90 12484640 91 14071005 92 15850240 93 17843669 94 20077094 95 22576927 96 25374695 97 28503186 98 32001080 99 35908619 100 40273283 101 45144668 102 50580648 103 56642270 104 63400231 105 70929216 106 79315619 107 88650853 108 99039931 109 110594774 110 123443160 111 137721350 112 153584795 113 171199561 114 190753998 115 212450250 116 236516666 117 263198449 118 292772299 119 325535550 120 361822429 121 401993316 122 446451934 123 495633663 124 550025840 125 610154372 126 676606082 127 750015577 128 831089270 129 920591187 130 1019371045 131 1128348125 132 1248542423 133 1381059141 134 1527122100 135 1688057247 136 1865331777 137 2060535596 138 2275424679 139 2511903551 140 2772072495 141 3058209321 142 3372824045 143 3718638809 144 4098648894 145 4516104668 146 4974578101 147 5477944593 148 6030460255 149 6636742400 150 7301855797 151 8031296730 152 8831087917 153 9707763942 154 10668480745 155 11721001164 156 12873817897 157 14136145223 158 15518054911 159 17030471643 160 18685330103 161 20495573194 162 22475328518 163 24639917142 164 27006050107 165 29591845505 166 32417054687 167 35503086910 168 38873264870 169 42552866915 170 46569412655 171 50952720875 172 55735238452 173 60952114308 174 66641571311 175 72845009171 176 79607422605 177 86977532152 178 95008264938 179 103756915160 180 113285689813 181 123661916131 182 134958656795 183 147254965187 184 160636592702 185 175196296388 186 191034642730 187 208260390264 188 226991399642 189 247355095419 190 269489511233 191 293543839622 192 319679622444 193 348071419900 194 378908160751 195 412393939923 196 448749569251 197 488213519387 198 531043687657 199 577518526684 200 627939054875 201 682630190260 202 741943057191 203 806256552017 204 875979975917 205 951554891653 206 1033458121099 207 1122203924799 208 1218347440610 209 1322487229567 210 1435269202175 211 1557389613700 212 1689599539892 213 1832708375363 214 1987588963327 215 2155181665755 216 2336500223508 217 2532636516035 218 2744767244870 219 2974159468687 220 3222178260009 221 3490293123551 222 3780086741751 223 4093262444403 224 4431654187026 225 4797235207405 226 5192129447054 227 5618621559464 228 6079169955544 229 6576418404902 230 7113210919405 231 7692605157053 232 8317889446196 233 8992598243611 234 9720531570269 235 10505772870641 236 11352711184206 237 12266061725776 238 13250891223448 239 14312641598083 240 15457158878385 241 16690720481439 242 18020068183045 243 19452439481893 244 20995605247445 245 22657905733687 246 24448293513521 247 26376374866047 248 28452458709655 249 30687604085530 250 33093675980735 251 35683399747798 252 38470424723682 253 41469386633741 254 44695980050476 255 48167029854351 256 51900573820853 257 55915944377849 258 60233862651570 259 64876532034553 260 69867745225675 261 75232991192798 262 80999577056361 263 87196750266866 264 93855837287491 265 101010383173862 266 108696309291749 267 116952072621737 268 125818845180016 269 135340695708772 270 145564793647812 271 156541616364673 272 168325180933532 273 180973280298545 274 194547746689148 275 209114720587305 276 224744949924092 277 241514096392250 278 259503075136705 279 278798403343185 280 299492585926389 281 321684512006862 282 345479892588424 283 370991711448792 284 398340721617979 285 427655957821514 286 459075299640597 287 492746053609373 288 528825591707248 289 567482012468885 290 608894864604243 291 653255897414695 292 700769880820620 293 751655456744167 294 806146067969703 295 864490923882087 296 926956052223231 297 993825393976364 298 1065401994113482 299 1142009242346922 300 1223992220679515 301 1311719109139181 302 1405582710237211 303 1506002040865519 304 1613424056598938 305 1728325453663831 306 1851214618517154 307 1982633667106660 308 2123160648414342 309 2273411851243480 310 2434044294315139 311 2605758334660034 312 2789300480498514 313 2985466339914788 314 3195103797310260 315 3419116345387259 316 3658466671403198 317 3914180420898713 318 4187350245195029 319 4479140051684202 320 4790789570439023 321 5123619152126218 322 5479034919121209 323 5858534179690728 324 6263711236481944 325 6696263494489314 326 7157998008772197 327 7650838372607680 328 8176832096763729 329 8738158374872415 330 9337136397175470 331 9976234102461767 332 10658077541798476 333 11385460738976566 334 12161356234247738 335 12988926190075558 336 13871534259897616 337 14812758093066634 338 15816402691211666 339 16886514484018100 340 18027396355913036 341 19243623485061612 342 20540060244170545 343 21921878018762930 344 23394574210387344 345 24963992275188945 346 26636343085699981 347 28418227459568538 348 30316660165674558 349 32339095245690778 350 34493452984282866 351 36788148361091307 352 39232121343408554 353 41834868846245774 354 44606478747140144 355 47557665777348903 356 50699809705678223 357 54044995632544658 358 57606056843075793 359 61396620031324294 360 65431153380376589 361 69725017306700457 362 74294518390360017 363 79156966297172553 364 84330734255822680 365 89835322892352395 366 95691428030722178 367 101921012260619057 368 108547380928385662 369 115595262352991832 370 123090892975757667 371 131062107245423006 372 139538433005549750 373 148551192188700820 374 158133607644992998 375 168320915915159299 376 179150486843442327 377 190661949845498013 378 202897327801288536 379 215901178397489159 380 229720743967578175 381 244406109667392314 382 260010371121472592 383 276589811391427728 384 294204088497680455 385 312916433365002786 386 332793859524401242 387 353907384466439236 388 376332264091174259 389 400148240175792548 390 425439802429163087 391 452296465088197879 392 480813059756685400 393 511090044482867623 394 543233830922441549 395 577357129627793018 396 613579315470954922 397 652026813296113456 398 692833505980419779 399 736141165064492311 400 782099906321372401 401 830868670496551131 402 882615731797023249 403 937519234447497894 404 995767760115525600 405 1057560926623646619 406 1123110020998297078 407 1192638667382974029 408 1266383533138415882 409 1344595073785931297 410 1427538320409872708 411 1515493710323985682 412 1608757964942216744 413 1707645015821868246 414 1812486983176974442 415 1923635208019086171 416 2041461342608459828 417 2166358500589383408 418 2298742471918537636 419 2439053004198559372 420 2587755155994512419 421 2745340724019134907 422 2912329750271391605 423 3089272111325242591 424 3276749196413220881 425 3475375676844620578 426 3685801374019301143 427 3908713228967563632 428 4144837381345298066 429 4394941361256241811 430 4659836402568409311 431 4940379881583670225 432 5237477890539580339 433 5552087950353963404 434 5885221872973531692 435 6237948778357604998 436 6611398277431821913 437 7006763826727957612 438 7425306267116125560 439 7868357553117439163 440 8337324686369581791 441 8833693860598735132 442 9359034832956587428 443 9915005530031511830 444 10503356904807949658 445 11125938053955594268 446 11784701613265355518 447 12481709441812582921 448 13219138614365595454 449 13999287733943705284 450 14824583585914242202 451 15697588147013708920 452 16621005972725504233 453 17597691978050560061 454 18630659637354526321 455 19723089620150835318 456 20878338890979656824 457 22099950292275888615 458 23391662641092364091 459 24757421360834453330 460 26201389681853056684 461 27727960434549725965 462 29341768472119284436 463 31047703749363916350 464 32850925098289804944 465 34756874730008075712 466 36771293507599083836 467 38900237022868543295 468 41150092525995859607 469 43527596744787820876 470 46039854647289524468 471 48694359188662579993 472 51499012101311972467 473 54462145773799966813 474 57592546283277723943 475 60899477632106285375 476 64392707259693472717 477 68082532885902592309 478 71979810763986039091 479 76095985405665706668 480 80443120863926638575 481 85033933643084908462 482 89881827330036479074 483 95000929023922665288 484 100406127667291303765 485 106113114364445228621 486 112138424800136458852 487 118499483853649935908 488 125214652532480068312 489 132303277330975770121 490 139785742150299383446 491 147683522896453699044 492 156019244906061740704 493 164816743329223185332 494 174101126633751624773 495 183898843373989206726 496 194237752404568970282 497 205147196697591718005 498 216658080961232962972 499 228802953235098218215 500 241616090679682707123 501 255133589753834803795 502 269393461018825621351 503 284435728783367434461 504 300302535851511234776 505 317038253610304543506 506 334689597744709283025 507 353305749841492085725 508 372938485197665784597 509 393642307122500769155 510 415474588079505475978 511 438495717987473681474 512 462769260060778497553 513 488362114541123710213 514 515344690738014602714 515 543791087766555080239 516 573779284440523532386 517 605391338749393807436 518 638713597421847684846 519 673836916048514101500 520 710856890315416154284 521 749874098869275835457 522 790994358419836104659 523 834328991653599260168 524 879995108622961261272 525 928115902243679583906 526 978820958629176063305 527 1032246582958893472735 528 1088536141679961094459 529 1147840421810038886281 530 1210318008218112464272 531 1276135679728728961958 532 1345468825011446101889 533 1418501879186179135693 534 1495428782199396799569 535 1576453459995427924219 536 1661790329639894312992 537 1751664829522277814542 538 1846313975906513622155 539 1945986947069338338142 540 2050945696417884604655 541 2161465595949986839738 542 2277836111582949532166 543 2400361511850026630359 544 2529361611637476559836 545 2665172552610338917202 546 2808147622160955950915 547 2958658112691740057038 548 3117094223242651478478 549 3283866005454050770378 550 3459404356068652514388 551 3644162058159624138929 552 3838614873500197188192 553 4043262688477164587280 554 4258630716195278928564 555 4485270757410971256276 556 4723762523196045481377 557 4974715022228381823467 558 5238768015887968310922 559 5516593544338716934665 560 5808897527078209244680 561 6116421441446363586102 562 6439944082907718861580 563 6780283410938406910475 564 7138298484696429572575 565 7514891492678830833230 566 7911009880942472592172 567 8327648584499963404721 568 8765852366903020878564 569 9226718273071399793891 570 9711398200856161928867 571 10221101596884366251237 572 10757098282695033867458 573 11320721417248682386720 574 11913370602390216217561 575 12536515137933113149734 576 13191697433567955060550 577 13880536584904147934291 578 14604732121529243179214 579 15366067935095946478076 580 16166416396066205776801 581 17007742667889465436217 582 17892109228058882116781 583 18821680605661587758278 584 19798728345756839083175 585 20825636211115723275283 586 21904905632629056390718 587 23039161419920375042558 588 24231157744533740172760 589 25483784408330181116223 590 26800073410623944666694 591 28183205827891544862294 592 29636519020853763895155 593 31163514184074180090214 594 32767864254260652738700 595 34453422193845720631565 596 36224229667546401624506 597 38084526130044592227328 598 40038758344142221225469 599 42091590349242361718573 600 44247913901316349860573 601 46512859406076276772623 602 48891807368484609570073 603 51390400382360934727493 604 54014555685370347328282 605 56770478305381986806418 606 59664674825832376193395 607 62703967798515715565854 608 65895510834000867329871 609 69246804400754460481494 610 72765712365969514723403 611 76460479312079858634034 612 80339748665015038128747 613 84412581671342636159920 614 88688477263686348012213 615 93177392855023036332779 616 97889766104884383909996 617 102836537701838091348488 618 108029175209242280795867 619 113479698022763805740971 620 119200703490982267273195 621 125205394252060973750474 622 131507606842527384311764 623 138121841636042837950782 624 145063294173352417789107 625 152347887946638135197494 626 159992308705079968403757 627 168014040350675751049130 628 176431402497245283711030 629 185263589768024741090084 630 194530712911449741293840 631 204253841817462773009521 632 214455050521217178874496 633 225157464284068517367477 634 236385308846653825944696 635 248163961952185381988199 636 260520007243400159584036 637 273481290640268705818886 638 287076979311320279036863 639 301337623355471949617401 640 316295220317477974559068 641 331983282664548872320694 642 348436908358434116447107 643 365692854662135237283138 644 383789615327719451953930 645 402767501317057706722736 646 422668725215220340504242 647 443537489502142143526880 648 465420078856735355921248 649 488364956674080911441661 650 512422865985607319387890 651 537646934979244539489134 652 564092787326591731144229 653 591818657531898631266150 654 620885511528549820579140 655 651357172757247279677136 656 683300453971884169944578 657 716785295028422380065217 658 751884906924868575462780 659 788675922370649669141614 660 827238553177538958514920 661 867656754775457149943353 662 910018398171480328763014 663 954415449682614328794521 664 1000944158789157945866123 665 1049705254468853343920104 666 1100804150389646417970690 667 1154351159353507345563635 668 1210461717402861378117210 669 1269256618017171385784677 670 1330862256847913261112220 671 1395410887457661639415068 672 1463040888551438013897205 673 1533897043207566769399780 674 1608130830639599571235563 675 1685900731041723174199316 676 1767372544096419251355899 677 1852719721745915753691094 678 1942123715857533554116757 679 2035774341437888700558325 680 2133870156081870573651110 681 2236618856369442908505709 682 2344237691956871809087460 683 2456953898138580348068868 684 2575005147692202556070880 685 2698640022851690596041180 686 2828118508292753685199098 687 2963712506050109651383812 688 3105706373328762559983413 689 3254397484209897733273843 690 3410096816298303994145515 691 3573129563400063402558671 692 3743835775369452814146125 693 3922571026309585720692570 694 4109707112365738133774988 695 4305632780399964956521298 696 4510754488894593244110534 697 4725497202486273585501012 698 4950305221596196304515640 699 5185643048680990335541615 700 5431996292698107344654545 701 5689872613443635754645813 702 5959802707495582055533210 703 6242341337565480697498523 704 6538068407142578431799612 705 6847590082390834294548353 706 7171539963347178126308034 707 7510580306552165807765733 708 7865403301339757713853187 709 8236732402102916488208137 710 8625323718955309444105307 711 9031967469307268102358437 712 9457489492986413945775850 713 9902752833639797322881846 714 10368659389276042659532431 715 10856151634921732510793390 716 11366214420498078164640241 717 11899876847149758126449949 718 12458214225400635053088600 719 13042350118647845715542904 720 13653458475660517390970808 721 14292765855898027593584685 722 14961553751630400461622401 723 15661161011004983377891255 724 16392986366385212301604145 725 17158491072462799248702460 726 17959201658841488473576335 727 18796712801981207537729362 728 19672690321604652516914469 729 20588874306875459536559824 730 21547082377888083994386317 731 22549213088234436222187972 732 23597249474662515727485736 733 24693262760086525163396249 734 25839416216478947551182467 735 27037969194440242560860709 736 28291281326535345248198185 737 29601816911774007879944724 738 30972149488929935607644752 739 32404966606706106813546946 740 33903074799097966617915353 741 35469404774645259793663158 742 37107016828636124998843258 743 38819106487695007250304684 744 40609010396589707370435541 745 42480212457492083092872144 746 44436350232364119369866160 747 46481221619574143852727954 748 48618791816321350475166814 749 50853200578916524836616175 750 53188769793479402859744857 751 55630011370122538952105567 752 58181635474246451103417644 753 60848559109123259903958010 754 63635915064546747448741507 755 66549061246925770482369865 756 69593590406848234617906424 757 72775340280792249323844068 758 76100404164364962713904947 759 79575141935153551738260450 760 83206191544034701910390688 761 87000480994551942390595840 762 90965240830794766081963432 763 95108017155040409281488125 764 99436685197311535826284309 765 103959463459899181250160785 766 108684928460866003951314369 767 113622030101515837913956720 768 118780107683860513151433783 769 124168906605166826558694922 770 129798595757797229103985403 771 135679785663697308549940879 772 141823547374106492085776551 773 148241432166302658416819742 774 154945492070514864572230825 775 161948301261475143552247187 776 169262978350512118090837279 777 176903209615536768832634158 778 184883273207819511821240421 779 193218064376025195419072432 780 201923121749647925422585494 781 211014654725684690803531886 782 220509572004198744873842689 783 230425511320260896634394021 784 240780870421716551367388648 785 251594839344215037727718823 786 262887434037057041766222049 787 274679531395568437572889734 788 286992905758000521461035608 789 299850266927286150166617334 790 313275299780459293447858475 791 327292705531066330078757413 792 341928244712576678897540949 793 357208781953527942774731693 794 373162332618037396212504330 795 389818111388262672624778980 796 407206582868525969808549167 797 425359514294008542521272527 798 444310030430307322375327296 799 464092670753598796998923739 800 484743449004814235948499417 801 506299915214965439744713878 802 528801220302714908550428674 803 552288183349323816793468881 804 576803361660385272498346538 805 602391123728118625148082583 806 629097725212619507834758106 807 656971388065183701488899897 808 686062382921814125593628493 809 716423114900127164898275844 810 748108212938267679229957208 811 781174622819963078082617146 812 815681704035673841825530956 813 851691330635766072959902443 814 889267996237926976050038471 815 928478923357495155222993210 816 969394177236178402848953844 817 1012086784351603854677349920 818 1056632855797491691839521893 819 1103111715731778420365370582 820 1151606035097950772915721243 821 1202201970832993445638272195 822 1254989310783924170802110214 823 1310061624563687281405423376 824 1367516420586432670837201206 825 1427455309531712129148501641 826 1489984174497120347409581419 827 1555213348109176358507531811 828 1623257796873034375670468617 829 1694237313052705211215845951 830 1768276714385123376784682821 831 1845506051943375980293364975 832 1926060826476991912838588917 833 2010082213570129719543464126 834 2097717297972086380495801055 835 2189119317468523563552912518 836 2284447916676471837860026945 837 2383869411161263523157645447 838 2487557062289373612887534921 839 2595691363247441958955371731 840 2708460336674834807788911961 841 2826059844374695605795004426 842 2948693909586874378769557286 843 3076575052325116728754506040 844 3209924638300793313082077760 845 3348973241975952005539600124 846 3493961024309949324717982617 847 3645138125786046809594802830 848 3802765075327529880051627932 849 3967113215736790856488329150 850 4138465146315819525020436745 851 4317115183352320883062358747 852 4503369839182653837210445475 853 4697548320570600615633707040 854 4899983047170076726466398490 855 5111020190869906011843538921 856 5331020236850176651058732272 857 5560358567212078590001382269 858 5799426068076983397453453712 859 6048629761085466400648252914 860 6308393460263492296856111929 861 6579158455260676973889052616 862 6861384222004926715546301462 863 7155549161858413819489813206 864 7462151370402325253272220719 865 7781709437021675124939082762 866 8114763276507277494984991521 867 8461874993939274070243055513 868 8823629784166002470621595572 869 9200636867242999075791233924 870 9593530461250183875257519050 871 10002970793960280134398904116 872 10429645154888935300573646087 873 10874268989316320659309225425 874 11337587035931881668622293462 875 11820374509817859769361096121 876 12323438332553926682727771346 877 12847618411294216209210920955 878 13393788968739955712799836911 879 13962859926005223108664419164 880 14555778340450868632091638362 881 15173529900641757577885104919 882 15817140480666029555650544443 883 16487677756141425010753592938 884 17186252884323757120918580225 885 17914022250825679398423642512 886 18672189285550911770368076087 887 19462006350549392054718366558 888 20284776702603351925153628640 889 21141856533462406368964165733 890 22034657090758372535189618823 891 22964646882747005212249517082 892 23933353970145176154229161936 893 24942368348457517810773270043 894 25993344424317270055187541038 895 27088003589501272683891894076 896 28228136896419857558176968120 897 29415607839028049994572017673 898 30652355243256161955265260158 899 31940396271214763268464632278 900 33281829543592378461759951874 901 34678838384833264653015457726 902 36133694195858564273502187610 903 37648759959276158961048298847 904 39226493882214021491208634096 905 40869453182107909387732749506 906 42580298020978273381249149136 907 44361795593942378526137150625 908 46216824377927327923172488588 909 48148378546777024778473117247 910 50159572559182649435213521023 911 52253645926111023656278281287 912 54433968164659898892082781300 913 56704043945532771290142907958 914 59067518441599984092803386839 915 61528182885296633551494715818 916 64089980342902917860785398635 917 66757011714058038392507769936 918 69533541965176433092152774090 919 72424006605763944407091424877 920 75433018416973441300179187909 921 78565374442093350508270935710 922 81826063249030541768070400530 923 85220272475229951627935685999 924 88753396665869353821729272894 925 92431045416577660047164151370 926 96259051832351299076132562554 927 100243481314784416407988229054 928 104390640690187204668475994537 929 108707087691641431842465830824 930 113199640808535637167196317517 931 117875389517633301827741597928 932 122741704910258149768982161971 933 127806250730730355824172593314 934 133076994841758535713053106552 935 138562221133083702903733964800 936 144270541890285734738564034193 937 150210910641299007705965485795 938 156392635498844712221952645159 939 162825393017671630404234886773 940 169519242586207975314263225158 941 176484641372962914282463066494 942 183732459848780905609389230225 943 191273997906843613303315117150 944 199121001603136364300108748303 945 207285680540947503461466119735 946 215780725923853190220680499504 947 224619329302555775917470915314 948 233815202041894689490999651824 949 243382595535333334306843809620 950 253336322195247837219621752822 951 263691777248402172056857606349 952 274464961367093380360861263650 953 285672504167588901040816946590 954 297331688608659785416676803120 955 309460476324237375428616118607 956 322077533925491470917055623198 957 335202260308943662483307743751 958 348854815008595204514234955296 959 363056147631463102899847491158 960 377828028417386086415154585492 961 393193079965482376767148167370 962 409174810171219023823469015308 963 425797646419686593886806566991 964 443086971082368819610383651304 965 461069158366453016777339954414 966 479771612567549566354812715892 967 499222807778576144011028425622 968 519452329109520881661481897955 969 540490915474826884271771842867 970 562370504007245052572754713346 971 585124276159181626473477981280 972 608786705554828160141224101529 973 633393607658703453309968615542 974 658982191328666551946374906594 975 685591112323976025839957690192 976 713260528841580971202449604823 977 742032159156532358121695156498 978 771949341445207490500775756524 979 803057095872944318812682761956 980 835402189030694616058327756283 981 869033200808424517965432674225 982 904000593796226564213963956332 983 940356785307458167307212330008 984 978156222121696782371259975157 985 1017455458048901061743337166150 986 1058313234419899861278980611548 987 1100790563612196339797300463317 988 1144950815724083002591075881878 989 1190859808514214729993206257049 990 1238585900728091612522956800828 991 1288200088937361273240757279154 992 1339776108022472904862007882731 993 1393390535434002132252074158793 994 1449122899372929273678936150945 995 1507055791035293444161646292141 996 1567274981071974136698206270420 997 1629869540419870459266944534818 998 1694931965666469723856887333806 999 1762558309115721827769859285423 1000 1832848313729278216858958831133