0 0 1 0 2 0 3 1 4 1 5 2 6 4 7 5 8 7 9 11 10 16 11 20 12 28 13 37 14 50 15 65 16 84 17 106 18 140 19 175 20 222 21 277 22 350 23 432 24 539 25 663 26 819 27 999 28 1225 29 1489 30 1816 31 2192 32 2653 33 3191 34 3846 35 4603 36 5516 37 6578 38 7852 39 9327 40 11083 41 13120 42 15532 43 18328 44 21620 45 25430 46 29904 47 35071 48 41110 49 48080 50 56205 51 65554 52 76419 53 88918 54 103393 55 120015 56 139213 57 161222 58 186592 59 215632 60 249005 61 287165 62 330937 63 380888 64 438074 65 503255 66 577712 67 662459 68 759104 69 868933 70 993977 71 1135894 72 1297167 73 1479984 74 1687434 75 1922241 76 2188292 77 2489083 78 2829377 79 3213635 80 3647767 81 4137365 82 4689802 83 5312116 84 6013336 85 6802385 86 7690430 87 8688516 88 9810513 89 11070228 90 12484639 91 14071005 92 15850239 93 17843669 94 20077093 95 22576927 96 25374694 97 28503186 98 32001079 99 35908619 100 40273282 101 45144668 102 50580647 103 56642270 104 63400230 105 70929216 106 79315618 107 88650853 108 99039930 109 110594774 110 123443159 111 137721350 112 153584794 113 171199561 114 190753997 115 212450250 116 236516665 117 263198449 118 292772298 119 325535550 120 361822428 121 401993316 122 446451933 123 495633663 124 550025839 125 610154372 126 676606081 127 750015577 128 831089269 129 920591187 130 1019371044 131 1128348125 132 1248542422 133 1381059141 134 1527122099 135 1688057247 136 1865331776 137 2060535596 138 2275424678 139 2511903551 140 2772072494 141 3058209321 142 3372824044 143 3718638809 144 4098648893 145 4516104668 146 4974578100 147 5477944593 148 6030460254 149 6636742400 150 7301855796 151 8031296730 152 8831087916 153 9707763942 154 10668480744 155 11721001164 156 12873817896 157 14136145223 158 15518054910 159 17030471643 160 18685330102 161 20495573194 162 22475328517 163 24639917142 164 27006050106 165 29591845505 166 32417054686 167 35503086910 168 38873264869 169 42552866915 170 46569412654 171 50952720875 172 55735238451 173 60952114308 174 66641571310 175 72845009171 176 79607422604 177 86977532152 178 95008264937 179 103756915160 180 113285689812 181 123661916131 182 134958656794 183 147254965187 184 160636592701 185 175196296388 186 191034642729 187 208260390264 188 226991399641 189 247355095419 190 269489511232 191 293543839622 192 319679622443 193 348071419900 194 378908160750 195 412393939923 196 448749569250 197 488213519387 198 531043687656 199 577518526684 200 627939054874 201 682630190260 202 741943057190 203 806256552017 204 875979975916 205 951554891653 206 1033458121098 207 1122203924799 208 1218347440609 209 1322487229567 210 1435269202174 211 1557389613700 212 1689599539891 213 1832708375363 214 1987588963326 215 2155181665755 216 2336500223507 217 2532636516035 218 2744767244869 219 2974159468687 220 3222178260008 221 3490293123551 222 3780086741750 223 4093262444403 224 4431654187025 225 4797235207405 226 5192129447053 227 5618621559464 228 6079169955543 229 6576418404902 230 7113210919404 231 7692605157053 232 8317889446195 233 8992598243611 234 9720531570268 235 10505772870641 236 11352711184205 237 12266061725776 238 13250891223447 239 14312641598083 240 15457158878384 241 16690720481439 242 18020068183044 243 19452439481893 244 20995605247444 245 22657905733687 246 24448293513520 247 26376374866047 248 28452458709654 249 30687604085530 250 33093675980734 251 35683399747798 252 38470424723681 253 41469386633741 254 44695980050475 255 48167029854351 256 51900573820852 257 55915944377849 258 60233862651569 259 64876532034553 260 69867745225674 261 75232991192798 262 80999577056360 263 87196750266866 264 93855837287490 265 101010383173862 266 108696309291748 267 116952072621737 268 125818845180015 269 135340695708772 270 145564793647811 271 156541616364673 272 168325180933531 273 180973280298545 274 194547746689147 275 209114720587305 276 224744949924091 277 241514096392250 278 259503075136704 279 278798403343185 280 299492585926388 281 321684512006862 282 345479892588423 283 370991711448792 284 398340721617978 285 427655957821514 286 459075299640596 287 492746053609373 288 528825591707247 289 567482012468885 290 608894864604242 291 653255897414695 292 700769880820619 293 751655456744167 294 806146067969702 295 864490923882087 296 926956052223230 297 993825393976364 298 1065401994113481 299 1142009242346922 300 1223992220679514 301 1311719109139181 302 1405582710237210 303 1506002040865519 304 1613424056598937 305 1728325453663831 306 1851214618517153 307 1982633667106660 308 2123160648414341 309 2273411851243480 310 2434044294315138 311 2605758334660034 312 2789300480498513 313 2985466339914788 314 3195103797310259 315 3419116345387259 316 3658466671403197 317 3914180420898713 318 4187350245195028 319 4479140051684202 320 4790789570439022 321 5123619152126218 322 5479034919121208 323 5858534179690728 324 6263711236481943 325 6696263494489314 326 7157998008772196 327 7650838372607680 328 8176832096763728 329 8738158374872415 330 9337136397175469 331 9976234102461767 332 10658077541798475 333 11385460738976566 334 12161356234247737 335 12988926190075558 336 13871534259897615 337 14812758093066634 338 15816402691211665 339 16886514484018100 340 18027396355913035 341 19243623485061612 342 20540060244170544 343 21921878018762930 344 23394574210387343 345 24963992275188945 346 26636343085699980 347 28418227459568538 348 30316660165674557 349 32339095245690778 350 34493452984282865 351 36788148361091307 352 39232121343408553 353 41834868846245774 354 44606478747140143 355 47557665777348903 356 50699809705678222 357 54044995632544658 358 57606056843075792 359 61396620031324294 360 65431153380376588 361 69725017306700457 362 74294518390360016 363 79156966297172553 364 84330734255822679 365 89835322892352395 366 95691428030722177 367 101921012260619057 368 108547380928385661 369 115595262352991832 370 123090892975757666 371 131062107245423006 372 139538433005549749 373 148551192188700820 374 158133607644992997 375 168320915915159299 376 179150486843442326 377 190661949845498013 378 202897327801288535 379 215901178397489159 380 229720743967578174 381 244406109667392314 382 260010371121472591 383 276589811391427728 384 294204088497680454 385 312916433365002786 386 332793859524401241 387 353907384466439236 388 376332264091174258 389 400148240175792548 390 425439802429163086 391 452296465088197879 392 480813059756685399 393 511090044482867623 394 543233830922441548 395 577357129627793018 396 613579315470954921 397 652026813296113456 398 692833505980419778 399 736141165064492311 400 782099906321372400 401 830868670496551131 402 882615731797023248 403 937519234447497894 404 995767760115525599 405 1057560926623646619 406 1123110020998297077 407 1192638667382974029 408 1266383533138415881 409 1344595073785931297 410 1427538320409872707 411 1515493710323985682 412 1608757964942216743 413 1707645015821868246 414 1812486983176974441 415 1923635208019086171 416 2041461342608459827 417 2166358500589383408 418 2298742471918537635 419 2439053004198559372 420 2587755155994512418 421 2745340724019134907 422 2912329750271391604 423 3089272111325242591 424 3276749196413220880 425 3475375676844620578 426 3685801374019301142 427 3908713228967563632 428 4144837381345298065 429 4394941361256241811 430 4659836402568409310 431 4940379881583670225 432 5237477890539580338 433 5552087950353963404 434 5885221872973531691 435 6237948778357604998 436 6611398277431821912 437 7006763826727957612 438 7425306267116125559 439 7868357553117439163 440 8337324686369581790 441 8833693860598735132 442 9359034832956587427 443 9915005530031511830 444 10503356904807949657 445 11125938053955594268 446 11784701613265355517 447 12481709441812582921 448 13219138614365595453 449 13999287733943705284 450 14824583585914242201 451 15697588147013708920 452 16621005972725504232 453 17597691978050560061 454 18630659637354526320 455 19723089620150835318 456 20878338890979656823 457 22099950292275888615 458 23391662641092364090 459 24757421360834453330 460 26201389681853056683 461 27727960434549725965 462 29341768472119284435 463 31047703749363916350 464 32850925098289804943 465 34756874730008075712 466 36771293507599083835 467 38900237022868543295 468 41150092525995859606 469 43527596744787820876 470 46039854647289524467 471 48694359188662579993 472 51499012101311972466 473 54462145773799966813 474 57592546283277723942 475 60899477632106285375 476 64392707259693472716 477 68082532885902592309 478 71979810763986039090 479 76095985405665706668 480 80443120863926638574 481 85033933643084908462 482 89881827330036479073 483 95000929023922665288 484 100406127667291303764 485 106113114364445228621 486 112138424800136458851 487 118499483853649935908 488 125214652532480068311 489 132303277330975770121 490 139785742150299383445 491 147683522896453699044 492 156019244906061740703 493 164816743329223185332 494 174101126633751624772 495 183898843373989206726 496 194237752404568970281 497 205147196697591718005 498 216658080961232962971 499 228802953235098218215 500 241616090679682707122 501 255133589753834803795 502 269393461018825621350 503 284435728783367434461 504 300302535851511234775 505 317038253610304543506 506 334689597744709283024 507 353305749841492085725 508 372938485197665784596 509 393642307122500769155 510 415474588079505475977 511 438495717987473681474 512 462769260060778497552 513 488362114541123710213 514 515344690738014602713 515 543791087766555080239 516 573779284440523532385 517 605391338749393807436 518 638713597421847684845 519 673836916048514101500 520 710856890315416154283 521 749874098869275835457 522 790994358419836104658 523 834328991653599260168 524 879995108622961261271 525 928115902243679583906 526 978820958629176063304 527 1032246582958893472735 528 1088536141679961094458 529 1147840421810038886281 530 1210318008218112464271 531 1276135679728728961958 532 1345468825011446101888 533 1418501879186179135693 534 1495428782199396799568 535 1576453459995427924219 536 1661790329639894312991 537 1751664829522277814542 538 1846313975906513622154 539 1945986947069338338142 540 2050945696417884604654 541 2161465595949986839738 542 2277836111582949532165 543 2400361511850026630359 544 2529361611637476559835 545 2665172552610338917202 546 2808147622160955950914 547 2958658112691740057038 548 3117094223242651478477 549 3283866005454050770378 550 3459404356068652514387 551 3644162058159624138929 552 3838614873500197188191 553 4043262688477164587280 554 4258630716195278928563 555 4485270757410971256276 556 4723762523196045481376 557 4974715022228381823467 558 5238768015887968310921 559 5516593544338716934665 560 5808897527078209244679 561 6116421441446363586102 562 6439944082907718861579 563 6780283410938406910475 564 7138298484696429572574 565 7514891492678830833230 566 7911009880942472592171 567 8327648584499963404721 568 8765852366903020878563 569 9226718273071399793891 570 9711398200856161928866 571 10221101596884366251237 572 10757098282695033867457 573 11320721417248682386720 574 11913370602390216217560 575 12536515137933113149734 576 13191697433567955060549 577 13880536584904147934291 578 14604732121529243179213 579 15366067935095946478076 580 16166416396066205776800 581 17007742667889465436217 582 17892109228058882116780 583 18821680605661587758278 584 19798728345756839083174 585 20825636211115723275283 586 21904905632629056390717 587 23039161419920375042558 588 24231157744533740172759 589 25483784408330181116223 590 26800073410623944666693 591 28183205827891544862294 592 29636519020853763895154 593 31163514184074180090214 594 32767864254260652738699 595 34453422193845720631565 596 36224229667546401624505 597 38084526130044592227328 598 40038758344142221225468 599 42091590349242361718573 600 44247913901316349860572 601 46512859406076276772623 602 48891807368484609570072 603 51390400382360934727493 604 54014555685370347328281 605 56770478305381986806418 606 59664674825832376193394 607 62703967798515715565854 608 65895510834000867329870 609 69246804400754460481494 610 72765712365969514723402 611 76460479312079858634034 612 80339748665015038128746 613 84412581671342636159920 614 88688477263686348012212 615 93177392855023036332779 616 97889766104884383909995 617 102836537701838091348488 618 108029175209242280795866 619 113479698022763805740971 620 119200703490982267273194 621 125205394252060973750474 622 131507606842527384311763 623 138121841636042837950782 624 145063294173352417789106 625 152347887946638135197494 626 159992308705079968403756 627 168014040350675751049130 628 176431402497245283711029 629 185263589768024741090084 630 194530712911449741293839 631 204253841817462773009521 632 214455050521217178874495 633 225157464284068517367477 634 236385308846653825944695 635 248163961952185381988199 636 260520007243400159584035 637 273481290640268705818886 638 287076979311320279036862 639 301337623355471949617401 640 316295220317477974559067 641 331983282664548872320694 642 348436908358434116447106 643 365692854662135237283138 644 383789615327719451953929 645 402767501317057706722736 646 422668725215220340504241 647 443537489502142143526880 648 465420078856735355921247 649 488364956674080911441661 650 512422865985607319387889 651 537646934979244539489134 652 564092787326591731144228 653 591818657531898631266150 654 620885511528549820579139 655 651357172757247279677136 656 683300453971884169944577 657 716785295028422380065217 658 751884906924868575462779 659 788675922370649669141614 660 827238553177538958514919 661 867656754775457149943353 662 910018398171480328763013 663 954415449682614328794521 664 1000944158789157945866122 665 1049705254468853343920104 666 1100804150389646417970689 667 1154351159353507345563635 668 1210461717402861378117209 669 1269256618017171385784677 670 1330862256847913261112219 671 1395410887457661639415068 672 1463040888551438013897204 673 1533897043207566769399780 674 1608130830639599571235562 675 1685900731041723174199316 676 1767372544096419251355898 677 1852719721745915753691094 678 1942123715857533554116756 679 2035774341437888700558325 680 2133870156081870573651109 681 2236618856369442908505709 682 2344237691956871809087459 683 2456953898138580348068868 684 2575005147692202556070879 685 2698640022851690596041180 686 2828118508292753685199097 687 2963712506050109651383812 688 3105706373328762559983412 689 3254397484209897733273843 690 3410096816298303994145514 691 3573129563400063402558671 692 3743835775369452814146124 693 3922571026309585720692570 694 4109707112365738133774987 695 4305632780399964956521298 696 4510754488894593244110533 697 4725497202486273585501012 698 4950305221596196304515639 699 5185643048680990335541615 700 5431996292698107344654544 701 5689872613443635754645813 702 5959802707495582055533209 703 6242341337565480697498523 704 6538068407142578431799611 705 6847590082390834294548353 706 7171539963347178126308033 707 7510580306552165807765733 708 7865403301339757713853186 709 8236732402102916488208137 710 8625323718955309444105306 711 9031967469307268102358437 712 9457489492986413945775849 713 9902752833639797322881846 714 10368659389276042659532430 715 10856151634921732510793390 716 11366214420498078164640240 717 11899876847149758126449949 718 12458214225400635053088599 719 13042350118647845715542904 720 13653458475660517390970807 721 14292765855898027593584685 722 14961553751630400461622400 723 15661161011004983377891255 724 16392986366385212301604144 725 17158491072462799248702460 726 17959201658841488473576334 727 18796712801981207537729362 728 19672690321604652516914468 729 20588874306875459536559824 730 21547082377888083994386316 731 22549213088234436222187972 732 23597249474662515727485735 733 24693262760086525163396249 734 25839416216478947551182466 735 27037969194440242560860709 736 28291281326535345248198184 737 29601816911774007879944724 738 30972149488929935607644751 739 32404966606706106813546946 740 33903074799097966617915352 741 35469404774645259793663158 742 37107016828636124998843257 743 38819106487695007250304684 744 40609010396589707370435540 745 42480212457492083092872144 746 44436350232364119369866159 747 46481221619574143852727954 748 48618791816321350475166813 749 50853200578916524836616175 750 53188769793479402859744856 751 55630011370122538952105567 752 58181635474246451103417643 753 60848559109123259903958010 754 63635915064546747448741506 755 66549061246925770482369865 756 69593590406848234617906423 757 72775340280792249323844068 758 76100404164364962713904946 759 79575141935153551738260450 760 83206191544034701910390687 761 87000480994551942390595840 762 90965240830794766081963431 763 95108017155040409281488125 764 99436685197311535826284308 765 103959463459899181250160785 766 108684928460866003951314368 767 113622030101515837913956720 768 118780107683860513151433782 769 124168906605166826558694922 770 129798595757797229103985402 771 135679785663697308549940879 772 141823547374106492085776550 773 148241432166302658416819742 774 154945492070514864572230824 775 161948301261475143552247187 776 169262978350512118090837278 777 176903209615536768832634158 778 184883273207819511821240420 779 193218064376025195419072432 780 201923121749647925422585493 781 211014654725684690803531886 782 220509572004198744873842688 783 230425511320260896634394021 784 240780870421716551367388647 785 251594839344215037727718823 786 262887434037057041766222048 787 274679531395568437572889734 788 286992905758000521461035607 789 299850266927286150166617334 790 313275299780459293447858474 791 327292705531066330078757413 792 341928244712576678897540948 793 357208781953527942774731693 794 373162332618037396212504329 795 389818111388262672624778980 796 407206582868525969808549166 797 425359514294008542521272527 798 444310030430307322375327295 799 464092670753598796998923739 800 484743449004814235948499416 801 506299915214965439744713878 802 528801220302714908550428673 803 552288183349323816793468881 804 576803361660385272498346537 805 602391123728118625148082583 806 629097725212619507834758105 807 656971388065183701488899897 808 686062382921814125593628492 809 716423114900127164898275844 810 748108212938267679229957207 811 781174622819963078082617146 812 815681704035673841825530955 813 851691330635766072959902443 814 889267996237926976050038470 815 928478923357495155222993210 816 969394177236178402848953843 817 1012086784351603854677349920 818 1056632855797491691839521892 819 1103111715731778420365370582 820 1151606035097950772915721242 821 1202201970832993445638272195 822 1254989310783924170802110213 823 1310061624563687281405423376 824 1367516420586432670837201205 825 1427455309531712129148501641 826 1489984174497120347409581418 827 1555213348109176358507531811 828 1623257796873034375670468616 829 1694237313052705211215845951 830 1768276714385123376784682820 831 1845506051943375980293364975 832 1926060826476991912838588916 833 2010082213570129719543464126 834 2097717297972086380495801054 835 2189119317468523563552912518 836 2284447916676471837860026944 837 2383869411161263523157645447 838 2487557062289373612887534920 839 2595691363247441958955371731 840 2708460336674834807788911960 841 2826059844374695605795004426 842 2948693909586874378769557285 843 3076575052325116728754506040 844 3209924638300793313082077759 845 3348973241975952005539600124 846 3493961024309949324717982616 847 3645138125786046809594802830 848 3802765075327529880051627931 849 3967113215736790856488329150 850 4138465146315819525020436744 851 4317115183352320883062358747 852 4503369839182653837210445474 853 4697548320570600615633707040 854 4899983047170076726466398489 855 5111020190869906011843538921 856 5331020236850176651058732271 857 5560358567212078590001382269 858 5799426068076983397453453711 859 6048629761085466400648252914 860 6308393460263492296856111928 861 6579158455260676973889052616 862 6861384222004926715546301461 863 7155549161858413819489813206 864 7462151370402325253272220718 865 7781709437021675124939082762 866 8114763276507277494984991520 867 8461874993939274070243055513 868 8823629784166002470621595571 869 9200636867242999075791233924 870 9593530461250183875257519049 871 10002970793960280134398904116 872 10429645154888935300573646086 873 10874268989316320659309225425 874 11337587035931881668622293461 875 11820374509817859769361096121 876 12323438332553926682727771345 877 12847618411294216209210920955 878 13393788968739955712799836910 879 13962859926005223108664419164 880 14555778340450868632091638361 881 15173529900641757577885104919 882 15817140480666029555650544442 883 16487677756141425010753592938 884 17186252884323757120918580224 885 17914022250825679398423642512 886 18672189285550911770368076086 887 19462006350549392054718366558 888 20284776702603351925153628639 889 21141856533462406368964165733 890 22034657090758372535189618822 891 22964646882747005212249517082 892 23933353970145176154229161935 893 24942368348457517810773270043 894 25993344424317270055187541037 895 27088003589501272683891894076 896 28228136896419857558176968119 897 29415607839028049994572017673 898 30652355243256161955265260157 899 31940396271214763268464632278 900 33281829543592378461759951873 901 34678838384833264653015457726 902 36133694195858564273502187609 903 37648759959276158961048298847 904 39226493882214021491208634095 905 40869453182107909387732749506 906 42580298020978273381249149135 907 44361795593942378526137150625 908 46216824377927327923172488587 909 48148378546777024778473117247 910 50159572559182649435213521022 911 52253645926111023656278281287 912 54433968164659898892082781299 913 56704043945532771290142907958 914 59067518441599984092803386838 915 61528182885296633551494715818 916 64089980342902917860785398634 917 66757011714058038392507769936 918 69533541965176433092152774089 919 72424006605763944407091424877 920 75433018416973441300179187908 921 78565374442093350508270935710 922 81826063249030541768070400529 923 85220272475229951627935685999 924 88753396665869353821729272893 925 92431045416577660047164151370 926 96259051832351299076132562553 927 100243481314784416407988229054 928 104390640690187204668475994536 929 108707087691641431842465830824 930 113199640808535637167196317516 931 117875389517633301827741597928 932 122741704910258149768982161970 933 127806250730730355824172593314 934 133076994841758535713053106551 935 138562221133083702903733964800 936 144270541890285734738564034192 937 150210910641299007705965485795 938 156392635498844712221952645158 939 162825393017671630404234886773 940 169519242586207975314263225157 941 176484641372962914282463066494 942 183732459848780905609389230224 943 191273997906843613303315117150 944 199121001603136364300108748302 945 207285680540947503461466119735 946 215780725923853190220680499503 947 224619329302555775917470915314 948 233815202041894689490999651823 949 243382595535333334306843809620 950 253336322195247837219621752821 951 263691777248402172056857606349 952 274464961367093380360861263649 953 285672504167588901040816946590 954 297331688608659785416676803119 955 309460476324237375428616118607 956 322077533925491470917055623197 957 335202260308943662483307743751 958 348854815008595204514234955295 959 363056147631463102899847491158 960 377828028417386086415154585491 961 393193079965482376767148167370 962 409174810171219023823469015307 963 425797646419686593886806566991 964 443086971082368819610383651303 965 461069158366453016777339954414 966 479771612567549566354812715891 967 499222807778576144011028425622 968 519452329109520881661481897954 969 540490915474826884271771842867 970 562370504007245052572754713345 971 585124276159181626473477981280 972 608786705554828160141224101528 973 633393607658703453309968615542 974 658982191328666551946374906593 975 685591112323976025839957690192 976 713260528841580971202449604822 977 742032159156532358121695156498 978 771949341445207490500775756523 979 803057095872944318812682761956 980 835402189030694616058327756282 981 869033200808424517965432674225 982 904000593796226564213963956331 983 940356785307458167307212330008 984 978156222121696782371259975156 985 1017455458048901061743337166150 986 1058313234419899861278980611547 987 1100790563612196339797300463317 988 1144950815724083002591075881877 989 1190859808514214729993206257049 990 1238585900728091612522956800827 991 1288200088937361273240757279154 992 1339776108022472904862007882730 993 1393390535434002132252074158793 994 1449122899372929273678936150944 995 1507055791035293444161646292141 996 1567274981071974136698206270419 997 1629869540419870459266944534818 998 1694931965666469723856887333805 999 1762558309115721827769859285423 1000 1832848313729278216858958831132