0 1 1 1 2 1 3 2 4 4 5 5 6 7 7 10 8 15 9 21 10 28 11 37 12 50 13 67 14 88 15 115 16 150 17 193 18 248 19 317 20 402 21 508 22 640 23 802 24 1002 25 1248 26 1545 27 1908 28 2351 29 2887 30 3532 31 4313 32 5251 33 6377 34 7724 35 9334 36 11254 37 13541 38 16253 39 19473 40 23286 41 27791 42 33100 43 39362 44 46723 45 55370 46 65504 47 77377 48 91257 49 107477 50 126380 51 148406 52 174030 53 203813 54 238365 55 278435 56 324825 57 378500 58 440510 59 512099 60 594635 61 689739 62 799164 63 924995 64 1069524 65 1235409 66 1425581 67 1643477 68 1892858 69 2178085 70 2503985 71 2876118 72 3300638 73 3784626 74 4335885 75 4963383 76 5677068 77 6488267 78 7409527 79 8455185 80 9641091 81 10985259 82 12507673 83 14230971 84 16180254 85 18383930 86 20873444 87 23684322 88 26855984 89 30432768 90 34463817 91 39004460 92 44115971 93 49867115 94 56334116 95 63602369 96 71766479 97 80932339 98 91217142 99 102751863 100 115681548 101 130167965 102 146390120 103 164547584 104 184861038 105 207576094 106 232964369 107 261327805 108 293000078 109 328351826 110 367792340 111 411775753 112 460803531 113 515431368 114 576272409 115 644005755 116 719380299 117 803224517 118 896451737 119 1000071467 120 1115195925 121 1243053581 122 1384997056 123 1542519073 124 1717262655 125 1911039414 126 2125842087 127 2363866654 128 2627527328 129 2919482282 130 3242652609 131 3600252369 132 3995811497 133 4433211538 134 4916713163 135 5450998194 136 6041203570 137 6692970178 138 7412483716 139 8206533012 140 9082558819 141 10048721996 142 11113962981 143 12288081720 144 13581808690 145 15006899543 146 16576219729 147 18303855687 148 20205216828 149 22297165481 150 24598138290 151 27128300222 152 29909688556 153 32966393057 154 36324728434 155 40013445721 156 44063936529 157 48510482074 158 53390494877 159 58744810796 160 64617976575 161 71058591494 162 78119646902 163 85858928594 164 94339417293 165 103629759203 166 113804740234 167 124945836986 168 137141774916 169 150489174772 170 165093209267 171 181068359230 172 198539187866 173 217641224085 174 238521871471 175 261341443566 176 286274230346 177 313509706396 178 343253784038 179 375730224255 180 411182104084 181 449873465401 182 492091032486 183 538146134842 184 588376719145 185 643149590116 186 702862761120 187 767948069041 188 838873919171 189 916148328714 190 1000322133649 191 1091992531815 192 1191806821220 193 1300466524882 194 1418731747015 195 1547425968509 196 1687441123701 197 1839743172333 198 2005378005682 199 2185477923497 200 2381268502310 201 2594076111723 202 2825335900820 203 3076600519867 204 3349549393642 205 3645998839503 206 3967912830425 207 4317414720872 208 4696799736174 209 5108548555095 210 5555341785089 211 6040075694979 212 6565878984668 213 7136130987141 214 7754481090524 215 8424869792004 216 9151551168679 217 9939117221088 218 10792523860133 219 11717119031675 220 12718672759218 221 13803409622022 222 14978043455235 223 16249814845686 224 17626531194556 225 19116609969209 226 20729124938677 227 22473856048541 228 24361342738556 229 26402941430455 230 28610886985969 231 30998358926071 232 33579552243034 233 36369753643249 234 39385423079339 235 42644281503231 236 46165404701397 237 49969324226999 238 54078135348265 239 58515613096215 240 63307336370309 241 68480821307267 242 74065663900935 243 80093693191044 244 86599135089671 245 93618788260166 246 101192212192729 247 109361929055204 248 118173639516745 249 127676454274558 250 137923141613165 251 148970392867421 252 160879106230307 253 173714690995749 254 187547392786915 255 202452642070556 256 218511426694247 257 235810690948668 258 254443762077634 259 274510807038072 260 296119320604522 261 319384647910176 262 344430542807020 263 371389765430569 264 400404720623503 265 431628141012772 266 465223816683495 267 501367375653177 268 540247117498721 269 582064904760447 270 627037114898479 271 675395657994529 272 727389063408168 273 783283641154495 274 843364721822952 275 907937981413590 276 977330855523909 277 1051894050051200 278 1132003153517976 279 1218060359001726 280 1310496301644460 281 1409772020596182 282 1516381052287972 283 1630851664996921 284 1753749242587873 285 1885678828547672 286 2027287839464804 287 2179268960330730 288 2342363232141376 289 2517363345725559 290 2705117153755547 291 2906531416511958 292 3122575795158268 293 3354287109899769 294 3602773878725869 295 3869221156298521 296 4154895690818996 297 4461151420769686 298 4789435331959685 299 5141293699357817 300 5518378736920943 301 5922455682978283 302 6355410347492788 303 6819257152086105 304 7316147692823704 305 7848379860333447 306 8418407551266059 307 9028851010019968 308 9682507839191861 309 10382364722390475 310 11131609903122677 311 11933646468651331 312 12792106488237567 313 13710866060791701 314 14694061327745309 315 15746105512866383 316 16871707052234348 317 18075888883565194 318 19364008966249355 319 20741782109938273 320 22215303192124264 321 23791071852020842 322 25476018751682274 323 27277533502271901 324 29203494357932015 325 31262299787326985 326 33462902038228162 327 35814842818612141 328 38328291224395032 329 41014084052254516 330 43883768643968671 331 46949648417843728 332 50224831251874973 333 53723280893096916 334 57459871578548939 335 61450446063460612 336 65711877265014697 337 70262133741319279 338 75120349239646787 339 80306896560165105 340 85843465998324147 341 91753148641864064 342 98060524817869399 343 104791757999542034 344 111974694504162793 345 119638969329235176 346 127816118499061176 347 136539698310515580 348 145845411895422461 349 155771243535446685 350 166357601197434970 351 177647467777429607 352 189686561578184652 353 202523506566883080 354 216210013001046352 355 230801069035210457 356 246355143966887297 357 262934403807482092 358 280604939916024968 359 299437011463110430 360 319505302550907614 361 340889194848434846 362 363673056666296803 363 387946549432056921 364 413804952600707344 365 441349508075286199 366 470687785294587977 367 501934068190760217 368 535209765310370165 369 570643844443614021 370 608373293208334365 371 648543607091919593 372 691309306567686992 373 736834484966141065 374 785293388907305244 375 836871033171560077 376 891763852027119897 377 950180389111335054 378 1012342028119392222 379 1078483766643324618 380 1148855035677236879 381 1223720567404616973 382 1303361314076661331 383 1388075420901792143 384 1478179256080614199 385 1574008501246218848 386 1675919305806495615 387 1784289508825796201 388 1899519932346757963 389 2022035750210008012 390 2152287936721363788 391 2290754799693124897 392 2437943602708522935 393 2594392281656612270 394 2760671260943237631 395 2937385375004993194 396 3125175901149530752 397 3324722709994833463 398 3536746540217990425 399 3762011404603060192 400 4001327134863360573 401 4255552073025217647 402 4525595917697319122 403 4812422733900334918 404 5117054135724340757 405 5440572651473815580 406 5784125281617011582 407 6148927260294546542 408 6536266031867883392 409 6947505454480230961 410 7384090243403497662 411 7847550667494866138 412 8339507512973250911 413 8861677329339887250 414 9415877973246507777 415 10004034466802838671 416 10628185187895387004 417 11290488410858377951 418 11993229217032604513 419 12738826795605818469 420 13529842156447033989 421 14368986277607347702 422 15259128711614569516 423 16203306675760557988 424 17204734653187876406 425 18266814532777146080 426 19393146317610409639 427 20587539433121122175 428 21854024667997484326 429 23196866782394541237 430 24620577820171334735 431 26129931163527768490 432 27729976370799042183 433 29426054840016407903 434 31223816343470658965 435 33129236480576136961 436 35148635099233956307 437 37288695738187469638 438 39556486146061765448 439 41959479935336205554 440 44505579433024846054 441 47203139792684778708 442 50060994436263474908 443 53088481897460006561 444 56295474142564073263 445 59692406448258708138 446 63290308920599526924 447 67100839743298022836 448 71136320248650493794 449 75409771908803275357 450 79934955350791275962 451 84726411503622466938 452 89799504992012335702 453 95170469896742034305 454 100856458008595440760 455 106875589708790605199 456 113247007616512853402 457 119990933150776604875 458 127128726162316469263 459 134682947798552221724 460 142677426774012042814 461 151137329226743005693 462 160089232351525728242 463 169561202009746456635 464 179582874527110318530 465 190185542900395596451 466 201402247646933866872 467 213267872541599299267 468 225819245499838889049 469 239095244877576972266 470 253136911473966015336 471 267987566536579344660 472 283692936085316571299 473 300301281886375928529 474 317863539426006158152 475 336433463250453639323 476 356067780058729646413 477 376826349953305737595 478 398772336276098750872 479 421972384477554194138 480 446496810491129675835 481 472419799108103145174 482 499819612874586437905 483 528778812057639045518 484 559384486257049135546 485 591728498267000457616 486 625907740824493532430 487 662024406911958248517 488 700186274317417495927 489 740507005189336023002 490 783106461362818915598 491 828111036271131952260 492 875654004300000279453 493 925875888483353271920 494 978924847487013683785 495 1034957082872329794390 496 1094137267684365054422 497 1156638997459484940047 498 1222645264805043295949 499 1292348958759309498518 500 1365953390203404131502 501 1443672844658177711823 502 1525733163868936992431 503 1612372357648395742692 504 1703841247525150312302 505 1800404143819404273746 506 1902339557852227698321 507 2009940951076695534286 508 2123517523012209718035 509 2243395039953768807723 510 2369916706530116618557 511 2503444082284413109418 512 2644358045563347135913 513 2793059807110481705327 514 2949971975883009652251 515 3115539679732140007211 516 3290231743722900117286 517 3474541929002475759567 518 3668990235275142942692 519 3874124270088677629557 520 4090520688300742540675 521 4318786705255414458171 522 4559561687379718965033 523 4813518824088014853082 524 5081366885079427386210 525 5363852067309402724155 526 5661759936133194464621 527 5975917465334626088152 528 6307195180991447593614 529 6656509414365742909033 530 7024824669269111503687 531 7413156109613185090581 532 7822572173142864425830 533 8254197317636517307627 534 8709214906172201754834 535 9188870238374409691769 536 9694473734901345767846 537 10227404282779520419699 538 10789112749571623191037 539 11381125674744789273621 540 12005049147022431697394 541 12662572876921696448553 542 13355474474135070285103 543 14085623939874920960237 544 14854988384800523385851 545 15665636983652743560609 546 16519746178270834970185 547 17419605141221187996585 548 18367621512870299934442 549 19366327425344149610945 550 20418385827476822106087 551 21526597125520925037495 552 22693906155116744456032 553 23923409500752324766811 554 25218363179740876936982 555 26582190708548941888458 556 28018491570179419679601 557 29531050102199257193263 558 31123844825955949706389 559 32801058238498889175566 560 34567087089767561994221 561 36426553168674850309810 562 38384314622859956481494 563 40445477838055084642167 564 42615409904266001943977 565 44899751697249425838205 566 47304431605146250718304 567 49835679931536355760663 568 52500044007688212265447 569 55304404048318883615926 570 58255989786831209054425 571 61362397927685835152997 572 64631610455374180474968 573 68072013841311757156395 574 71692419191951690204557 575 75502083383449398286421 576 79510731230377863897409 577 83728578738218583132346 578 88166357491727391551849 579 92835340233712783306422 580 97747367691363317984483 581 102914876709931851268613 582 108350929756429086419479 583 114069245858904626108803 584 120084233050007143505683 585 126411022386719248912641 586 133065503621569761825558 587 140064362604134315237811 588 147425120495363251333763 589 155166174881116628719308 590 163306842875364862615584 591 171867406307717907114542 592 180869159094407759330247 593 190334456896450763512186 594 200286769173596595075961 595 210750733747706698818852 596 221752213994542547030368 597 233318358788454309500230 598 245477665330297502586757 599 258260044994933619558540 600 271696892341053005910298 601 285821157432652766933977 602 300667421628480203480904 603 316271977002964987607873 604 332672909569791157053584 605 349910186487147836459622 606 368025747432035154149964 607 387063600339626852561674 608 407069921712803350507767 609 428093161716398807272389 610 450184154280663583041551 611 473396232448751810578544 612 497785349213924342478566 613 523410204103424611102241 614 550332375777872365105988 615 578616460927333984902161 616 608330219758214118053377 617 639544728378569072442395 618 672334538403626867233996 619 706777844118000567494256 620 742956657546573279799715 621 780956991802094172407400 622 820869053094442539333841 623 862787441804060666960265 624 906811363040528852200386 625 953044847126416943432332 626 1001596980466714980606036 627 1052582147285070171406892 628 1106120282730074465282466 629 1162337137877694821451247 630 1221364557179970763083958 631 1283340768935048549500253 632 1348410689379850860189128 633 1416726241033911498917389 634 1488446685951528962200287 635 1563738974569115098676071 636 1642778110865849203813586 637 1725747534588186173342148 638 1812839521322845438327991 639 1904255601238305326281036 640 2000206997352004447018240 641 2100915084219074717988388 642 2206611867978983595628928 643 2317540488738600054568224 644 2433955746314429537272864 645 2556124650402728111176417 646 2684326996294442754683527 647 2818855967302059654353974 648 2960018765118041947838898 649 3108137269379215185692634 650 3263548727768809592793005 651 3426606478047491239890111 652 3597680703467238690998436 653 3777159223086930863742621 654 3965448318576669042950896 655 4162973599168729729371212 656 4370180906487334391182942 657 4587537261066680455876148 658 4815531852447642457584408 659 5054677074827760623667733 660 5305509610327363993361534 661 5568591562026448457938957 662 5844511639023066810555018 663 6133886395863994161920903 664 6437361528803173060857610 665 6755613231452408263145555 666 7089349612502883999836062 667 7439312178314790918500693 668 7806277383296638296042506 669 8191058251125147645773517 670 8594506069991992663593952 671 9017512165204509193464749 672 9461009752614920029703358 673 9925975876506028862113252 674 10413433435721867297632063 675 10924453301998838757485423 676 11460156534627688379556870 677 12021716695758533061248024 678 12610362270851472500020951 679 13227379198973349841064853 680 13874113517848371835995651 681 14551974128785897746959252 682 15262435686834171503580976 683 16007041621743452734497581 684 16787407295567386642339939 685 17605223302986876998684144 686 18462258920707762147415688 687 19360365712561564759284412 688 20301481297229153331763321 689 21287633285809628881018945 690 22320943396772889882285267 691 23403631756163433879845659 692 24538021391266881510305749 693 25726542926308750230377011 694 26971739489129124275865316 695 28276271838166348413060468 696 29642923719489792681598328 697 31074607464045372181104161 698 32574369835720056839560915 699 34145398141292345607914428 700 35791026613816932885947973 701 37514743081492834709498530 702 39320195934587529417073602 703 41211201403534476132275846 704 43191751161890309572034748 705 45266020268430349204593714 706 47438375463279563911642664 707 49713383833620084551137664 708 52095821865188678717967514 709 54590684896477590516506068 710 57203196993282899135248225 711 59938821262005374326433627 712 62803270620902985891972920 713 65802519049321087980989582 714 68942813335789325483342966 715 72230685346772854462671168 716 75672964838803218505981920 717 79276792837690563853567700 718 83049635609537719130795186 719 86999299249337432460415900 720 91133944914040898214973524 721 95462104728138084202569995 722 99992698390992688951844660 723 104735050516426335903676119 724 109698908736352518730449337 725 114894462601620427138378126 726 120332363314647065086465416 727 126023744329892671079853235 728 131980242859774629161656112 729 138214022325218546877917098 730 144737795791717567174184114 731 151564850433512092998578594 732 158709073070317879904725942 733 166184976822920815937945924 734 174007728935927975370193911 735 182193179818016743589662457 736 190757893352163679407924864 737 199719178530562480413691903 738 209095122471263086406593223 739 218904624875981917696070666 740 229167433991054092071036243 741 239904184136122685973501087 742 251136434867895780728412592 743 262886711849149839434696219 744 275178549496126491222405599 745 288036535480559942673777810 746 301486357165793141394327035 747 315554850059793601843576044 748 330270048371374211915638339 749 345661237759561745767897280 750 361759010369846590315105839 751 378595322254993012557737823 752 396203553282201205226430969 753 414618569632692328966032839 754 433876789004247598824337410 755 454016248631874470896220300 756 475076676246609724860758705 757 497099564097503428008536808 758 520128246167072788213083808 759 544207978715973901939766196 760 569386024298326650105619804 761 595711739395047103528440345 762 623236665818707992530632635 763 652014626049865204660235893 764 682101822671473139306609881 765 713556942074968768942612275 766 746441262618850764412387649 767 780818767428121359873393887 768 816756262030813259888886557 769 854323497035997836391767926 770 893593296066183875418590788 771 934641689165874971867798832 772 977548051917279426119961876 773 1022395250503766748660325824 774 1069269792971662155614666279 775 1118261986951373218944047466 776 1169466104109675187122031468 777 1222980551616252876998915823 778 1278908050919333175564640621 779 1337355824137453615303750324 780 1398435788387126689365381349 781 1462264758379388260437422578 782 1528964657631990978414423408 783 1598662738658333042609270890 784 1671491812509130351187364262 785 1747590488058360453236483664 786 1827103421441163368266605009 787 1910181576068193165567111576 788 1996982493658411154999196619 789 2087670576750514188597208255 790 2182417383172138378533805097 791 2281401932965688860711115361 792 2384811028290161241716827610 793 2492839586839661383868493974 794 2605690989341541270115873978 795 2723577441720173305593846657 796 2846720352536430727015090246 797 2975350726337953582884235229 798 3109709573581308523131199912 799 3250048337814224699535338183 800 3396629340834261514185210877 801 3549726246569567806033296319 802 3709624544457884267980039270 803 3876622053131655458431724521 804 4051029445250116771245180688 805 4233170794353542410559972876 806 4423384144650549272118964703 807 4622022104686489421256974179 808 4829452465879601831455906828 809 5046058846951776771251375913 810 5272241365322590063110892065 811 5508417336578738080569973575 812 5755022003176229648877318043 813 6012509293579721138341739570 814 6281352613092303736499293279 815 6562045667679925172288019398 816 6855103322147546122371404851 817 7161062494079157432007167570 818 7480483085011019011175271651 819 7813948950366993788208060597 820 8162068909746748609336943660 821 8525477799221953594065172304 822 8904837567362548233988540059 823 9300838416784738265284544346 824 9714199993084766526031506167 825 10145672623097752661175922310 826 10596038604499154198822082690 827 11066113548847762040508926408 828 11556747780253750058646434909 829 12068827791943256587240543574 830 12603277763082438860324909952 831 13161061138319024354702739826 832 13743182272598250506834067453 833 14350688143912860748447629902 834 14984670136753687295980675902 835 15646265899138434686120255261 836 16336661276211772705053980560 837 17057092323529899724355764229 838 17808847403267551514431033806 839 18593269366715165462673716698 840 19411757826568784746868949734 841 20265771522655474016233028845 842 21156830784882752586118945932 843 22086520097352020253224127725 844 23056490767733406972224367753 845 24068463706163123749566238405 846 25124232318094499190775285988 847 26225665515710674148726984177 848 27374710852690686834408365690 849 28573397787311650900492566103 850 29823841079068221850934197588 851 31128244324196820825981451787 852 32488903635706474905267304237 853 33908211473740919129132359686 854 35388660632328147812052394984 855 36932848388814204074536663563 856 38543480822528043871309845813 857 40223377309484131726467085259 858 41975475200199435572813927782 859 43802834687982042007211746454 860 45708643875340157380045685530 861 47696224046463177908965231815 862 49769035154041283006714793135 863 51930681529017044990501404223 864 54184917822202370418580941200 865 56535655187047141964100693874 866 58986967713212768324518884938 867 61543099120984958027106370702 868 64208469726956005540383032374 869 66987683691818238890883133997 870 69885536561537665558700407502 871 72907023113620834102788572466 872 76057345520649188715408964751 873 79341921843734344586603820998 874 82766394869045490510351017036 875 86336641301077192524987617777 876 90058781326863020246405876308 877 93939188565898359755506332704 878 97984500421115363976491914551 879 102201628846854994233839672304 880 106597771550406438872083688295 881 111180423644333688639956870240 882 115957389767483685680500526025 883 120936796693271141720901954101 884 126127106444562896112458139506 885 131537129935240525212215454130 886 137176041159304954349523347249 887 143053391949202108424553949440 888 149179127325895384424364939893 889 155563601464090067510906996847 890 162217594296928049739953609597 891 169152328785419564470905015207 892 176379488878863525292674426432 893 183911238193530769043745789622 894 191760239437946557888485745001 895 199939674614211511629814213670 896 208463266025945340368699747894 897 217345298124626856285149991839 898 226600640227338504169031596820 899 236244770140205709651049866911 900 246293798723152573838307085544 901 256764495432977617860985459335 902 267674314883188411762794333664 903 279041424460523921899485734626 904 290884733039640440057061956662 905 303223920839043077080509303754 906 316079470463012334912048032890 907 329472699176006434584392290512 908 343425792457817367265040096331 909 357961838889624443769959083121 910 373104866423026123559737404402 911 388879880086141684801921000108 912 405312901182961729937274026918 913 422431008044293382815770803099 914 440262378390895414677715019009 915 458836333371733427275657791205 916 478183383342708942353158159603 917 498335275453732017560832307311 918 519325043114618395974194685220 919 541187057413002666815861095053 920 563957080560272299399562787899 921 587672321444447443445484973757 922 612371493371962181237394061123 923 638094874083448488848894585652 924 664884368131888934069521714326 925 692783571714892432843802702287 926 721837840056363950384476668562 927 752094357436488522565659869922 928 783602209972737485392155836431 929 816412461258535344625780731708 930 850578230970304768743813219417 931 886154776557840136513121666127 932 923199578137352795073818645206 933 961772426711089484935439796728 934 1001935515842155578693055498505 935 1043753536918083099595471375707 936 1087293778141776714703880214651 937 1132626227393755746596357977326 938 1179823679115093998324267183442 939 1228961845366149057263908731334 940 1280119471222076552808503942428 941 1333378454672250354091786558982 942 1388823971197065301867473699768 943 1446544603202193122154980645346 944 1506632474497203681794712905991 945 1569183390012561695040775819510 946 1634296980956373053257152661893 947 1702076855619894779047423774085 948 1772630756048748591730427174639 949 1846070720805000590133989794277 950 1922513254053799765717797107246 951 2002079501217117109386377923740 952 2084895431446306943816737187596 953 2171092027174734790498984316303 954 2260805481021594421841534877149 955 2354177400328283641345888990904 956 2451355019619337578055309135241 957 2552491421290943725726214519030 958 2657745764841499414428813387972 959 2767283524970534756485490130586 960 2881276738884628258329813639022 961 2999904263161704228153709626236 962 3123352040538337900166820970140 963 3251813376998423023450331578650 964 3385489229555795841008164828049 965 3524588505138177373703619909404 966 3669328370995112379463941100459 967 3819934577068468112283307675544 968 3976641790780530151418769938186 969 4139693944711817411467233015090 970 4309344597658456614337206976674 971 4485857309577330885332108092413 972 4669506030946272017206808319269 973 4860575507086325902109168661296 974 5059361698013611724957340408236 975 5266172214409544133281969039871 976 5481326770320221712915712300021 977 5705157653218633044726836091041 978 5938010212087023399081233633949 979 6180243364201331170325049156164 980 6432230121325075653875918609303 981 6694358136046489393382777363978 982 6967030269020073609482676393461 983 7250665177902149238746906011183 984 7545697928799415909001802181928 985 7852580631080054407135453052102 986 8171783096428554599149488861404 987 8503793523058260755831952033736 988 8849119206029642450093747070247 989 9208287274657565004206522933068 990 9581845458027394601212714435779 991 9970362879677676193399523904021 992 10374430882546416283813668335707 993 10794663885318737490552406963300 994 11231700271355900125582708036078 995 11686203311429461449328335262875 996 12158862121529722207458462028788 997 12650392657064650052437733724363 998 13161538744814230991415484753568 999 13693073154055744816763405133157 1000 14245798708327853434128305235369