0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 29 10 42 11 55 12 76 13 99 14 133 15 172 16 227 17 290 18 376 19 477 20 612 21 769 22 975 23 1217 24 1528 25 1895 26 2359 27 2907 28 3592 29 4400 30 5403 31 6584 32 8034 33 9742 34 11823 35 14272 36 17234 37 20713 38 24897 39 29803 40 35674 41 42542 42 50719 43 60272 44 71592 45 84794 46 100373 47 118506 48 139827 49 164595 50 193622 51 227275 52 266587 53 312083 54 365072 55 426289 56 497388 57 579378 58 674360 59 783701 60 910069 61 1055284 62 1222726 63 1414832 64 1635859 65 1889035 66 2179730 67 2512182 68 2893162 69 3328200 70 3825830 71 4393215 72 5041088 73 5778715 74 6619558 75 7575552 76 8663559 77 9898866 78 11302596 79 12894252 80 14700248 81 16745367 82 19062582 83 21683326 84 24648678 85 27998366 86 31783501 87 36054144 88 40873811 89 46305391 90 52427722 91 59319579 92 67078642 93 75803408 94 85614702 95 96635375 96 109014669 97 122905428 98 138491780 99 155963474 100 175547339 101 197478413 102 222035732 103 249509931 104 280243733 105 314595821 106 352986572 107 395857793 108 443724465 109 497129778 110 556703765 111 623113092 112 697127472 113 779563832 114 871361283 115 973519239 116 1087181982 117 1213570226 118 1354076561 119 1510189690 120 1683602275 121 1876127084 122 2089818931 123 2326882172 124 2589808127 125 2881273525 126 3204295337 127 3562119391 128 3958394978 129 4397052753 130 4882501740 131 5419495655 132 6013355283 133 6669822612 134 7395311425 135 8196748851 136 9081857615 137 10058984387 138 11137418003 139 12327203639 140 13639501816 141 15086387798 142 16681256732 143 18438608037 144 20374502090 145 22506329775 146 24853327324 147 27436331018 148 30278357898 149 33404345584 150 36841807814 151 40620559649 152 44773457802 153 49336112615 154 54347723558 155 59850780046 156 65892004517 157 72522044348 158 79796537140 159 87775796259 160 96526014840 161 106118948763 162 116633278195 163 128154293321 164 140775433608 165 154597983631 166 169732813705 167 186300094027 168 204431264297 169 224268775751 170 245968321331 171 269698617832 172 295643932136 173 324003919351 174 354996484475 175 388857695802 176 425845027663 177 466237371867 178 510338714297 179 558478270602 180 611014657065 181 668336182567 182 730865582337 183 799060505414 184 873418887619 185 954479681705 186 1042828958117 187 1139100932311 188 1243984895187 189 1358226601318 190 1482636145495 191 1618089787366 192 1765538906728 193 1926012354859 194 2100626637792 195 2290588900922 196 2497208511798 197 2721900801686 198 2966200245450 199 3231765102878 200 3520392421118 201 3834023744092 202 4174762194360 203 4544879448061 204 4946835186928 205 5383285569590 206 5857105387393 207 6371398298773 208 6929522071093 209 7535100886262 210 8192054105508 211 8904611004393 212 9677343558202 213 10515184024015 214 11423462311306 215 12407926894872 216 13474787417197 217 14630739489786 218 15883013266969 219 17239402777330 220 18708321312579 221 20298836031295 222 22020731124681 223 23884548550282 224 25901660066746 225 28084315087481 226 30445722832238 227 33000108436958 228 35762806647107 229 38750327487929 230 41980463123732 231 45472364589137 232 49246663663046 233 53325562387530 234 57732972057897 235 62494617511087 236 67638195627649 237 73193496660370 238 79192584978791 239 85669940035757 240 92662662463160 241 100210637654017 242 108356770745224 243 117147176226685 244 126631445826561 245 136862868051455 246 147898733545807 247 159800589021164 248 172634585290602 249 186471770676900 250 201388487634309 251 217466711448843 252 234794502164011 253 253466395212215 254 273583916266884 255 295256031378836 256 318599733415663 257 343740560332692 258 370813263038425 259 399962401625485 260 431343105829280 261 465121760413030 262 501476870888349 263 540599850799979 264 582696007070018 265 627985443685620 266 676704182958987 267 729105202104468 268 785459708888964 269 846058329830577 270 911212561179387 271 981256130021891 272 1056546644312792 273 1137467151063863 274 1224428012282528 275 1317868687691178 276 1418259866988784 277 1526105508234771 278 1641945260870493 279 1766356795068439 280 1899958554482924 281 2043412416588996 282 2197426819245019 283 2362759797382515 284 2540222533220229 285 2730682820692254 286 2935069095670430 287 3154374386305068 288 3389660886961942 289 3642064460309178 290 3912799826952621 291 4203165693758741 292 4514550640492982 293 4848438958634953 294 5206417326816895 295 5590181455388091 296 6001543654291930 297 6442440391024728 298 6914940867923805 299 7421255615113582 300 7963746209178307 301 8544935038419796 302 9167516311760968 303 9834367151353385 304 10548560059522979 305 11313375513695509 306 12132316080561194 307 13009120710689109 308 13947780713104522 309 14952555972162242 310 16027993022717482 311 17178943440180377 312 18410584286776468 313 19728438957582578 314 21138400302410660 315 22646754246435269 316 24260205930496885 317 25985906465140473 318 27831482475096927 319 29805066390697357 320 31915329830496242 321 34171517884747579 322 36583486824214147 323 39161742887316677 324 41917484863822164 325 44862647961141780 326 48009951879653527 327 51372950405235067 328 54966085669283723 329 58804744194867443 330 62905318120028029 331 67285268514981836 332 71963194443107313 333 76958904467562726 334 82293494531677763 335 87989428686423986 336 94070626892182080 337 100562556125126803 338 107492329336985789 339 114888808240185974 340 122782714812919920 341 131206747221676494 342 140195705427569639 343 149786621882577864 344 160018902981732595 345 170934476368216169 346 182577950187077963 347 194996779056701651 348 208241443315749158 349 222365635967171108 350 237426464373932600 351 253484660759800927 352 270604809104287661 353 288855582095254422 354 308309996302982594 355 329045678826917697 356 351145154196917439 357 374696144344392299 358 399791891089944370 359 426531493502411287 360 455020270291180875 361 485370139100480150 362 517700023637091407 363 552136279987346289 364 588813153882830156 365 627873259730314193 366 669468094056206070 367 713758573612147826 368 760915611750846502 369 811120722720227740 370 864566668517169157 371 921458137319760269 372 982012469250603056 373 1046460417829590746 374 1115046964065078989 375 1188032170849418051 376 1265692095895974472 377 1348319750158407379 378 1436226121356797601 379 1529741248792675016 380 1629215370572363144 381 1735020128627949372 382 1847549854265947370 383 1967222918806035529 384 2094483173775515849 385 2229801464360876011 386 2373677242452595634 387 2526640262089506342 388 2689252385655357840 389 2862109482704930533 390 3045843451946919347 391 3241124347298652591 392 3448662640885304888 393 3669211602904265762 394 3903569833757318895 395 4152583927346465840 396 4417151303665695569 397 4698223188531035019 398 4996807781527156681 399 5313973588932878092 400 5650852965884272949 401 6008645843434194927 402 6388623688201195547 403 6792133669143439551 404 7220603082859583359 405 7675544010814192207 406 8158558263896233274 407 8671342586560612898 408 9215694180290752966 409 9793516517481079871 410 10406825510157289795 411 11057756003486126695 412 11748568663552346225 413 12481657228220474106 414 13259556196030726447 415 14084948920836194709 416 14960676193049302603 417 15889745274129484259 418 16875339471584227123 419 17920828220088998404 420 19029777762929929979 421 20205962398412711735 422 21453376392946233371 423 22776246524565015906 424 24179045366725762152 425 25666505275366401117 426 27243633197865766692 427 28915726266243603967 428 30688388302777215230 429 32567547199879028973 430 34559473312749608951 431 36670798826338381370 432 38908538246334869537 433 41280109975628627645 434 43793359138115115072 435 46456581611448722056 436 49278549443804215054 437 52268537616711331511 438 55436352343329015884 439 58792360865036616293 440 62347522951235090390 441 66113424066452265562 442 70102310426501623871 443 74327125909471851406 444 78801551061601213737 445 83540044166033753064 446 88557884634393694948 447 93871218692008937305 448 99497107638322318922 449 105453578656856104038 450 111759678479746132981 451 118435529885543458728 452 125502391360822222381 453 132982719909530942779 454 140900237368377145587 455 149280000218450849696 456 158148473281558899417 457 167533607298907843823 458 177464920813441905065 459 187973586362219681982 460 199092521435865496271 461 210856484221706173487 462 223302174626517265110 463 236468340607384689277 464 250395890348940852153 465 265128010329252485714 466 280710289858716830505 467 297190852150120454934 468 314620492554423580558 469 333052824038661650829 470 352544430595220522148 471 373155028679757920616 472 394947637426621216947 473 417988757762873261321 474 442348561234721242474 475 468101088694606577714 476 495324459733541047561 477 524101093037785669563 478 554517938631634529065 479 586666722220356561158 480 620644202679213744900 481 656552442942155000387 482 694499095427886401967 483 734597702301575850247 484 776968011810007699221 485 821736311038795206378 486 869035776438687835348 487 919006842526258959079 488 971797590225187225584 489 1027564155317126029975 490 1086471158598432937385 491 1148692158283270858138 492 1214410126391307127395 493 1283817949740706992249 494 1357118957439605509211 495 1434527475586554401539 496 1516269411242302021437 497 1602582866483861806057 498 1693718784787945957249 499 1789941630666986940989 500 1891530105006539722329 501 1998777897152630902498 502 2111994476418148953663 503 2231505924196659900039 504 2357655809593364922571 505 2490806109917417430357 506 2631338179208159053956 507 2779653766313033884833 508 2936176085976883751984 509 3101350944653497671988 510 3275647924812836743929 511 3459561629669544840308 512 3653612992448945928916 513 3858350652354757280501 514 4074352401729277670696 515 4302226706835264463247 516 4542614307159569130294 517 4796189895961823581764 518 5063663887415563120765 519 5345784273391248528893 520 5643338575717453305366 521 5957155897331235871521 522 6288109078688294988955 523 6637116963244494680210 524 7005146778963391475876 525 7393216640104904826908 526 7802398176888148531240 527 8233819297774472309174 528 8688667092661551131560 529 9168190882277625003413 530 9673705422829539548117 531 10206594271794149324382 532 10768313324740612875409 533 11360394529736780691813 534 11984449790138786430095 535 12642175063050197061536 536 13335354665246371978998 537 14065865794660001375997 538 14835683280312904101310 539 15646884569683744480339 540 16501654967587738032055 541 17402293136544118924680 542 18351216874009457791774 543 19350969177540294966716 544 20404224614686570870978 545 21513796009878623294286 546 22682641466665305779440 547 23913871738887902957148 548 25210757970848502835458 549 26576739821514046428610 550 28015433994674349243464 551 29530643191699683596890 552 31126365510849117020802 553 32806804311541830111677 554 34576378569764870805626 555 36439733744974281272107 556 38401753187092256782145 557 40467570106097368510611 558 42642580135465853846065 559 44932454514315422089233 560 47343153922412032390708 561 49880942995480552887252 562 52552405558152207982696 563 55364460604836906969770 564 58324379069320793994274 565 61439801416506828265212 566 64718756100888428822889 567 68169678928613367156316 568 71801433371869677430208 569 75623331876229463378727 570 79645158214208651833286 571 83877190929829023011077 572 88330227932386860167440 573 93015612288772215039393 574 97945259277948138016546 575 103131684761937509748628 576 108588034942832775164744 577 114328117565668180423142 578 120366434643122793059680 579 126718216767920464556316 580 133399459095945294896970 581 140426959072550465967512 582 147818355992781415540615 583 155592172475243300397178 584 163767857948748071067424 585 172365834239423878729093 586 181407543366613654286862 587 190915497643964899384962 588 200913332204077352558837 589 211425860052668338916577 590 222479129781588166486046 591 234100486057120093008214 592 246318633024873372079517 593 259163700759181250994653 594 272667314911391214992588 595 286862669697532848039278 596 301784604394032535100331 597 317469683495732059820197 598 333956280720474951397009 599 351284667029598829221842 600 369497102865624328542777 601 388637934792991009960241 602 408753696761719778119776 603 429893216197927803016651 604 452107725161368398802882 605 475450976793705362803674 606 499979367319845621947252 607 525752063847688658707433 608 552831138252794719187404 609 581281707417016472128051 610 611172080133984375747300 611 642573910976401105507489 612 675562361466833338201220 613 710216268875295543324637 614 746618323016739376598128 615 784855251402733714753783 616 825018013154738326262456 617 867202002067140127536665 618 911507259264866422337609 619 958038695880785658441781 620 1006906326238524309719464 621 1058225512006397468148225 622 1112117217852604466159542 623 1168708279111633139586099 624 1228131682040588033009336 625 1290526857223732635227012 626 1356039986756928407862404 627 1424824325823079500388008 628 1497040539348031079502084 629 1572857054405726243692426 630 1652450429125061333350478 631 1736005738830258864737488 632 1823716980235883311972127 633 1915787494497131414341593 634 2012430410011409079158712 635 2113869105846959710913581 636 2220337696776196878381418 637 2332081540871528699227784 638 2449357770730322785873306 639 2572435849376329965568654 640 2701598152001220455948398 641 2837140574691263279236238 642 2979373171408527409731468 643 3128620820478262486257851 644 3285223921967055647864076 645 3449539127319761002909102 646 3621940102765350452046099 647 3802818327986599785025998 648 3992583931700559276124548 649 4191666565783161934492500 650 4400516319733961413103105 651 4619604677265339442901521 652 4849425516974540291927635 653 5090496159047521603049493 654 5343358460129841701237929 655 5608579958493097636403526 656 5886755071824770109873726 657 6178506349965708209510146 658 6484485785132906713137621 659 6805376182165154349023865 660 7141892591557670189802938 661 7494783808055836462623065 662 7864833937822914811841635 663 8252864037205261460668557 664 8659733826380782756459592 665 9086343481190270559042389 666 9533635506732230702315838 667 10002596696321683644977431 668 10494260179714538912694113 669 11009707564525749322167511 670 11550071175092231662167110 671 12116536393065732969957524 672 12710344104366886970008519 673 13332793257174421687728753 674 13985243535994582287517180 675 14669118156908103829415086 676 15385906789490098494022583 677 16137168610961179813600996 678 16924535498555139548074851 679 17749715366163383624714538 680 18614495651774485257170968 681 19520746962315404912415769 682 20470426882992603953838861 683 21465583958334272775796481 684 22508361852662648864989750 685 23601003697844844064464462 686 24745856636737184262351844 687 25945376570875764659101150 688 27202133121574304736459182 689 28518814813748322323200457 690 29898234492438024873170511 691 31343334982182654391026886 692 32857195000100851195659442 693 34443035333736716052710000 694 36104225295485252845933624 695 37844289465643360766182734 696 39666914736942738593399930 697 41575957673683762524852341 698 43575452199460117295387396 699 45669617627759975406763461 700 47862867050665437940156144 701 50159816101204673561269621 702 52565292105917356170650407 703 55084343644567137692884406 704 57722250535016744916271665 705 60484534261698883366860910 706 63376968867279545951359119 707 66405592327576791148902048 708 69576718431049371148141015 709 72896949184689747122936382 710 76373187769502085726985282 711 80012652069324930807838291 712 83822888798206424758349970 713 87811788252183724641925453 714 91987599712876529475927475 715 96358947531019319359090286 716 100934847919733868230134393 717 105724726488135991939430525 718 110738436547675425476423553 719 115986278224485247714469492 720 121479018412960193070721333 721 127227911606753906487265920 722 133244721645476921145480027 723 139541744416449830683373894 724 146131831553118324388081648 725 153028415172920980141784998 726 160245533699825979103982898 727 167797858818059066355090264 728 175700723606157023281599498 729 183970151901920324106227779 730 192622888951651943524300536 731 201676433398654237291306550 732 211149070668986312624719445 733 221059907814228183086402820 734 231428909874262805189505886 735 242276937825004432248564282 736 253625788179519298130198291 737 265498234313091240112481674 738 277918069586575156948731203 739 290910152344694216432470313 740 304500452870021243554369604 741 318716102375922803110877366 742 333585444126146468351976035 743 349138086771515160366598916 744 365404959998936959343546511 745 382418372590989474178786054 746 400212072999451983262892503 747 418821312539500398744096922 748 438282911316793065851788198 749 458635327003334299975445111 750 479918726583945901960154605 751 502175061199180936211180314 752 525448144216921824636120937 753 549783732669284493724815916 754 575229612198359268613450790 755 601835685659107601724882356 756 629654065535183545250841788 757 658739170328681843619565293 758 689147825092848036770940093 759 720939366282502392226818804 760 754175751105592919723503874 761 788921671565534767922231480 762 825244673393336556697224864 763 863215280075327559828153613 764 902907122192376581131127006 765 944397072293927568525178230 766 987765385541045740613617584 767 1033095846360776705832411865 768 1080475921365844322801442707 769 1129996918802554399814528073 770 1181754154802416847711177669 771 1235847126722635872801996942 772 1292379693874258634261851312 773 1351460265947273597291946202 774 1413201999456664833267364496 775 1477723002544867026389193572 776 1545146548491940251853940658 777 1615601298297239779847434388 778 1689221532713481588115885660 779 1766147394127664721551883739 780 1846525138701787289447957183 781 1930507399201051336680468354 782 2018253458957184635842299949 783 2109929537430565319018410686 784 2205709087856340620849956546 785 2305773107477198070670947279 786 2410310460888649862038644000 787 2519518217041686157458991406 788 2633602000472686835851259687 789 2752776357351132673293781442 790 2877265136962666974168602114 791 3007301889267505595388431777 792 3143130279203335952696358372 793 3285004518426238292785664022 794 3433189815214606442720592335 795 3587962843287546280568942536 796 3749612230323157323634194962 797 3918439066990887985909601994 798 4094757437348761695980644251 799 4278894971487530397427002342 800 4471193421343309779398651246 801 4672009260634189545094092570 802 4881714309918929376350764518 803 5100696387812691918027770322 804 5329359989440747256291618049 805 5568126993251065751195561123 806 5817437397356330641997779506 807 6077750086619285324127051578 808 6349543631748862606670039801 809 6633317121721608094268156572 810 6929591030900668999597358172 811 7238908122275668677335750030 812 7561834388309106185361184542 813 7898960030930280419001243876 814 8250900482284976409195679169 815 8618297467909176199878553258 816 9001820114067601072001642657 817 9402166101062962903305731822 818 9820062864400070665200493046 819 10256268845759467393376972251 820 10711574795819715213847485761 821 11186805131043878665756866527 822 11682819346636858154859365997 823 12200513487963041836237800032 824 12740821682812028336726484835 825 13304717736989891721042811733 826 13893216795819490688602014306 827 14507377074230505463536374301 828 15148301658234270772068755247 829 15817140380683721656808064354 830 16515091774342163346659350613 831 17243405105398543941138105798 832 18003382490700018817476061756 833 18796381102095986333048466907 834 19623815461431361242889955479 835 20487159829860425626767934499 836 21387950695307480774752390970 837 22327789362045099117981585235 838 23308344646527839493840243552 839 24331355683775751102670978987 840 25398634848782188518615486436 841 26512070797589762400214248127 842 27673631632872606376393007486 843 28885368199046311869190431418 844 30149417512136502707687603986 845 31468006329835171260297886753 846 32843454867399973102473663364 847 34278180665266002311587308110 848 35774702614483382934038754452 849 37335645146325802799538352083 850 38963742592678049504904817706 851 40661843724061255882556670556 852 42432916472438104766366081466 853 44280052846211247248978028505 854 46206474045133943384773673707 855 48215535783144912656837676101 856 50310733827469075461702190949 857 52495709762642562356557940871 858 54774256988475860739346266236 859 57150326961311260103269410461 860 59628035688314051748807881543 861 62211670484906851239266524467 862 64905697005869665146176040388 863 67714766561028039187192058765 864 70643723726897158900786319368 865 73697614266081644215745061147 866 76881693366711094476971839354 867 80201434214657999061929670505 868 83662536911802417084799786321 869 87270937754111806402307124202 870 91032818883862541780161348235 871 94954618330873997735978810220 872 99043040458227722342922892071 873 103305066828532090729677337241 874 107747967507441327220384057037 875 112379312821772586465558068514 876 117206985590263748361751545548 877 122239193845699996928228508704 878 127484484067890572626733885295 879 132951754947717074720719898454 880 138650271703286551715841531094 881 144589680970021438731786163460 882 150780026287393310446664006948 883 157231764205869661910388421736 884 163955781038585736837788234326 885 170963410283184030557362676980 886 178266450740280017546266042715 887 185877185356016944497040663096 888 193808400817267182407442119581 889 202073407929121332203934596977 890 210686062805485701276964099994 891 219660788904778043557287243563 892 229012599943982147610702724609 893 238757123725583341546300427878 894 248910626913275935461634003780 895 259490040793694456349319027049 896 270512988062895262788218292968 897 281997810677782995619762645355 898 293963598814264922931331992576 899 306430220975499410796933248016 900 319418355295315923675252188976 901 332949522083591333922812857197 902 347046117662210420240309071722 903 361731449542079586698007803134 904 377029772993647925798589226603 905 392966329065374977166725885490 906 409567384106722438808951122830 907 426860270854387472799149414215 908 444873431142797603234029012193 909 463636460302194665165487079560 910 483180153310114582538398438104 911 503536552764557110370194668994 912 524738998749809412413333339297 913 546822180668568387842144275732 914 569822191116881277013861112149 915 593776581881313632902348871474 916 618724422140848791037520624190 917 644706358959136988484229032963 918 671764680156044473396541634917 919 699943379650808573194539898795 920 729288225372691992337122632973 921 759846829838645283482455554545 922 791668723501348162549259738993 923 824805430974895880251070760595 924 859310550249553769135873076903 925 895239835011199807417788378248 926 932651280185549433706577515710 927 971605210831777658235817844109 928 1012164374514969367036721094018 929 1054394037291698241474216663092 930 1098362083448217783847225854513 931 1144139119135992648323439598421 932 1191798580054876440977229057741 933 1241416843339890490806395039422 934 1293073343813560693631247994346 935 1346850694771852069990124951505 936 1402834813478199864992443937054 937 1461115051546685610995292375011 938 1521784330402356673313333047972 939 1584939282013739747141057178904 940 1650680395100076659955267619999 941 1719112167023403066767777576610 942 1790343261583635908043352006222 943 1864486672943008770054694354770 944 1941659895914849511525354478456 945 2021985102860492607518484505184 946 2105589327447429522967581412874 947 2192604655531270363254525151750 948 2283168423434105624499865523725 949 2377423423902049168262926161571 950 2475518120035516538532124323706 951 2577606867496761670520005995272 952 2683850145310782048321553791266 953 2794414795587506209248579109401 954 2909474272505639287091321005830 955 3029208900911243626079445317592 956 3153806144897533331451189121953 957 3283460886746027674892406813437 958 3418375716623620206059972700667 959 3558761233444823361966472189858 960 3704836357323945612662897674859 961 3856828654057775508219679314550 962 4014974672096010297571504865638 963 4179520292473681709587460786505 964 4350721092197747528091193526864 965 4528842721598319437038322644547 966 4714161296174259427947392345156 967 4906963803482561731029980061825 968 5107548525641644683370712165046 969 5316225478039847386958341026382 970 5533316864862686275428319089701 971 5759157552075193418617120435490 972 5994095558519586498197286095437 973 6238492565813001971710862796376 974 6492724447755742321312517108683 975 6757181819986812032665419557711 976 7032270610651160060105653249476 977 7318412652871349055654737970157 978 7616046299846080609464978575265 979 7925627063428433638762066361542 980 8247628277068600387123269181750 981 8582541784038615057891952640947 982 8930878651890879394852026959657 983 9293169914137451542581098337334 984 9669967340173931296518213291526 985 10061844234509569421091324208944 986 10469396266404841274276011733393 987 10893242331058346377934305851276 988 11334025443527455897370742376826 989 11792413666610786650765857863341 990 12269101073966305008670538783360 991 12764808749785779535874137525394 992 13280285826395422755757030372777 993 13816310561202976565087286615715 994 14373691454464263363774484488932 995 14953268409396394994630650844205 996 15555913936221512407423231886081 997 16182534401783130754161911678910 998 16834071326438045342837796410165 999 17511502729989283297865561125551 1000 18215844528490973741703797362218