0 1 1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 7 10 9 11 11 12 15 13 19 14 24 15 30 16 39 17 48 18 60 19 75 20 93 21 115 22 142 23 173 24 213 25 260 26 316 27 383 28 465 29 560 30 676 31 812 32 974 33 1165 34 1393 35 1658 36 1975 37 2345 38 2779 39 3288 40 3887 41 4582 42 5398 43 6346 44 7452 45 8735 46 10230 47 11956 48 13964 49 16283 50 18964 51 22057 52 25632 53 29739 54 34477 55 39917 56 46171 57 53342 58 61572 59 70985 60 81773 61 94097 62 108181 63 124250 64 142592 65 163473 66 187269 67 214329 68 245104 69 280055 70 319750 71 364753 72 415797 73 473597 74 539042 75 613060 76 696767 77 791298 78 898064 79 1018504 80 1154338 81 1307391 82 1479805 83 1673825 84 1892141 85 2137552 86 2413343 87 2723033 88 3070691 89 3460636 90 3897918 91 4387900 92 4936755 93 5551143 94 6238668 95 7007491 96 7866997 97 8827239 98 9899658 99 11096666 100 12432288 101 13921671 102 15582017 103 17431896 104 19492241 105 21785807 106 24338130 107 27176913 108 30333318 109 33841122 110 37738123 111 42065508 112 46869206 113 52199158 114 58111151 115 64665818 116 71930631 117 79979150 118 88893023 119 98761172 120 109682356 121 121764069 122 135125371 123 149896139 124 166219942 125 184253206 126 204168917 127 226155488 128 250420823 129 277191661 130 306717807 131 339271500 132 375152679 133 414688056 134 458237012 135 506191334 136 558981445 137 617076245 138 680990805 139 751286045 140 828577295 141 913534936 142 1006893645 143 1109453378 144 1222090596 145 1345759226 146 1481503333 147 1630459526 148 1793870730 149 1973089326 150 2169593733 151 2384991977 152 2621040398 153 2879649341 154 3162903847 155 3473070735 156 3812623255 157 4184249238 158 4590879117 159 5035697374 160 5522173671 161 6054076802 162 6635511597 163 7270935172 164 7965198928 165 8723569770 166 9551777298 167 10456039341 168 11443117454 169 12520346704 170 13695699071 171 14977821003 172 16376104932 173 17900733965 174 19562765767 175 21374184713 176 23347997837 177 25498298885 178 27840377171 179 30390793411 180 33167506686 181 36189962848 182 39479240096 183 43058155799 184 46951432125 185 51185821655 186 55790300192 187 60796213045 188 66237496105 189 72150850482 190 78575994761 191 85555869621 192 93136930465 193 101369385192 194 110307530151 195 120010031488 196 130540309023 197 141966864510 198 154363726128 199 167810829383 200 182394527177 201 198208037440 202 215352026749 203 233935131022 204 254074629718 205 275897048712 206 299538934204 207 325147557447 208 352881800481 209 382912973504 210 415425836370 211 450619543461 212 488708815500 213 529925039072 214 574517608320 215 622755197016 216 674927303141 217 731345716580 218 792346290263 219 858290642121 220 929568182246 221 1006598077440 222 1089831581571 223 1179754298420 224 1276888851766 225 1381797501039 226 1495085196655 227 1617402593078 228 1749449555622 229 1891978625167 230 2045799033195 231 2211780696377 232 2390858807851 233 2584038429745 234 2792399756050 235 3017103385171 236 3259396339941 237 3520618132073 238 3802207641742 239 4105710077730 240 4432784852302 241 4785213559636 242 5164908975508 243 5573924215132 244 6014463009240 245 6488890196738 246 6999743473076 247 7549745400431 248 8141816820442 249 8779090613777 250 9464927002127 251 10202929289194 252 10996961332836 253 11851165536860 254 12769982778979 255 13758172987895 256 14820837856890 257 15963444349121 258 17191850601898 259 18512332756895 260 19931614474399 261 21456897570067 262 23095895623216 263 24856868924725 264 26748662761239 265 28780747253878 266 30963260933659 267 33307056165264 268 35823748717870 269 38525769511768 270 41426421022297 271 44539936194367 272 47881542575035 273 51467529393764 274 55315320447754 275 59443550422530 276 63872147731706 277 68622421303338 278 73717154675004 279 79180704679936 280 85039108277370 281 91320194695629 282 98053706722424 283 105271428076588 284 113007321037442 285 121297671100175 286 130181243079742 287 139699445299134 288 149896506634458 289 160819662787416 290 172519356979471 291 185049451249821 292 198467453865660 293 212834758880258 294 228216903785249 295 244683840991913 296 262310229610382 297 281175743052972 298 301365399335457 299 322969909441020 300 346086051167836 301 370817063494713 302 397273069535166 303 425571522887244 304 455837685969453 305 488205134982097 306 522816300774381 307 559823039895644 308 599387245921251 309 641681495096594 310 686889737060478 311 735208024524497 312 786845293538824 313 842024187843667 314 900981939953825 315 963971302241295 316 1031261541530069 317 1103139490321394 318 1179910669267366 319 1261900473629046 320 1349455439616226 321 1442944583138870 322 1542760827990582 323 1649322515890702 324 1763075016809901 325 1884492431649536 326 2014079407321742 327 2152373056149130 328 2299945001090186 329 2457403538693809 330 2625395943086363 331 2804610902602881 332 2995781114426850 333 3199686028811690 334 3417154770151918 335 3649069226602958 336 3896367337827427 337 4160046572406032 338 4441167627129132 339 4740858339850761 340 5060317850607482 341 5400821003046700 342 5763723023848917 343 6150464472248796 344 6562576500728729 345 7001686419431255 346 7469523608627902 347 7967925772508095 348 8498845582491574 349 9064357703752532 350 9666666257537170 351 10308112713856298 352 10991184271424040 353 11718522720685800 354 12492933851842873 355 13317397404694320 356 14195077627884425 357 15129334445952460 358 16123735307433321 359 17182067714459643 360 18308352513694912 361 19506857950869405 362 20782114576152897 363 22138931005208101 364 23582410630641283 365 25117969291907137 366 26751354007024365 367 28488662777206864 368 30336365577455508 369 32301326548239100 370 34390827511228232 371 36612592829079744 372 38974815743606215 373 41486186217167558 374 44155920424347708 375 46993791924840746 376 50010164677783409 377 53216027935687569 378 56623033193229675 379 60243533236439132 380 64090623484312675 381 68178185677424564 382 72520934123090807 383 77134464562203506 384 82035305887178292 385 87240974787140952 386 92770033571966540 387 98642151264440468 388 104878168235518262 389 111500164487155403 390 118531531884074274 391 125997050455026357 392 133922969094286748 393 142337090802847948 394 151268862831233259 395 160749471885059074 396 170811944790354839 397 181491254802948567 398 192824433997929863 399 204850691950394674 400 217611541185136921 401 231150929637117242 402 245515380647102684 403 260754140767308747 404 276919335953312874 405 294066136455016067 406 312252931038619546 407 331541510895346108 408 351997263931177589 409 373689379839908096 410 396691066722883234 411 421079779710852168 412 446937462425805045 413 474350801798116773 414 503411497160027816 415 534216544195968971 416 566868534762894639 417 601475973235069558 418 638153610486180349 419 677022796246252758 420 718211851057297918 421 761856458655850570 422 808100080129267786 423 857094390776279594 424 908999741152103654 425 963985643343208906 426 1022231284100422691 427 1083926066000876798 428 1149270178431622481 429 1218475199706389701 430 1291764732286918630 431 1369375072577791871 432 1451555917464472131 433 1538571109236108584 434 1630699421282009392 435 1728235386396730064 436 1831490170321652657 437 1940792492573548096 438 2056489597452963490 439 2178948277519519457 440 2308555952719671537 441 2445721807718345701 442 2590877990939665826 443 2744480878162208084 444 2907012404528003017 445 3078981468133766391 446 3260925409454437065 447 3453411570127524158 448 3657038935775724070 449 3872439866796170754 450 4100281922266588328 451 4341269781336266277 452 4596147267773847787 453 4865699482528756335 454 5150755050549329323 455 5452188487256672842 456 5770922691548481607 457 6107931571328105124 458 6464242809129218719 459 6840940774493393104 460 7239169591433465233 461 7660136368373280140 462 8105114599738800821 463 8575447747397681889 464 9072553012050552673 465 9597925303665223921 466 10153141422074516477 467 10739864457818126987 468 11359848425471936105 469 12014943140633303627 470 12707099354042730471 471 13438374155215073440 472 14210936660417092744 473 15027073998695941852 474 15889197612291064807 475 16799849886598564833 476 17761711127667621591 477 18777606904017388904 478 19850515772560621550 479 20983577407210553950 480 22180101151948132690 481 23443575018892675564 482 24777675155344473861 483 26186275802514604781 484 27673459772314568488 485 29243529467317531374 486 30901018472911376475 487 32650703749390470511 488 34497618455919305203 489 36447065437022857718 490 38504631406732754840 491 40676201864249745082 492 42967976779769109069 493 45386487087853539516 494 47938612030868545846 495 50631597393750285639 496 53473074676865053342 497 56471081252510420895 498 59634081556486001960 499 62970989364987612981 500 66491191213384970478 501 70204571012318676039 502 74121535923306934009 503 78253043555002202649 504 82610630548478490277 505 87206442618956719137 506 92053266129150695652 507 97164561268540261507 508 102554496921215229384 509 108237987304186627678 510 114230730467007859506 511 120549248742938167182 512 127210931251496155238 513 134234078551805856062 514 141637949556459402082 515 149442810815380842316 516 157669988290263008959 517 166341921740131017617 518 175482221850513767624 519 185115730238945865105 520 195268582482340191535 521 205968274312324923886 522 217243731138421991931 523 229125381059835704246 524 241645231541461800011 525 254836949931008881880 526 268735948010090176571 527 283379470773884269817 528 298806689651149601516 529 315058800378617052350 530 332179125762307382152 531 350213223561128298290 532 369208999748052381310 533 389216827407643685343 534 410289671550192955322 535 432483220126905396144 536 455856021553768506390 537 480469629056722297691 538 506388752175745044409 539 533681415771390679326 540 562419126904267054279 541 592677049964880138210 542 624534190460368033622 543 658073587872721896572 544 693382518034487767342 545 730552705477307014826 546 769680546242545958586 547 810867341654038423905 548 854219543589585399017 549 899849011800204230800 550 947873283865667556860 551 998415858388995049824 552 1051606492075289010895 553 1107581511356367265586 554 1166484139268848085554 555 1228464838311562895403 556 1293681670058108517995 557 1362300672320990581117 558 1434496254717803856049 559 1510451613513179382429 560 1590359166668652393965 561 1674421010058822789055 562 1762849395875375106761 563 1855867234270015114451 564 1953708619355760637136 565 2056619380719092190465 566 2164857661669507401700 567 2278694525490049722777 568 2398414591032522463484 569 2524316699042525463298 570 2656714610686225081357 571 2795937739797004328979 572 2942331920454147862259 573 3096260211557262754430 574 3258103740161955766997 575 3428262585399717644183 576 3607156704915277239653 577 3795226905818549223515 578 3992935862267870836790 579 4200769181872170242098 580 4419236523229289536716 581 4648872766996464237031 582 4890239243029423158792 583 5143925016213909545964 584 5410548233765746885406 585 5690757536872324254798 586 5985233539713530140510 587 6294690379007297057541 588 6619877337404024677317 589 6961580544172624654350 590 7320624756815237151997 591 7697875227378603314506 592 8094239657440842890306 593 8510670245897034124529 594 8948165833895652734258 595 9407774151437551346102 596 9890594170397313156423 597 10397778568902868771373 598 10930536312278534439061 599 11490135355950741093710 600 12077905476007952890697 601 12695241233320097430097 602 13343605077440062269562 603 14024530596745237326717 604 14739625921621415227001 605 15490577287750491686601 606 16279152766937204784354 607 17107206173195151651139 608 17976681152218195586365 609 18889615462676697143718 610 19848145458218658771367 611 20854510779400232843894 612 21911059265248512758570 613 23020252094537748615628 614 24184669167379755734244 615 25407014738144542296818 616 26690123311291449168730 617 28036965812146900192339 618 29450656045277655540484 619 30934457453608482070224 620 32491790192098753241309 621 34126238530340834794661 622 35841558599165997385183 623 37641686496944791581357 624 39530746772053974532122 625 41513061298640882643971 626 43593158563669037954996 627 45775783383950494326350 628 48065907072796824461387 629 50468738076711115587514 630 52989733103549620848850 631 55634608764447091559911 632 58409353752892975416444 633 61320241585292794271552 634 64373843928536456106630 635 67577044541131644484182 636 70937053855750323938459 637 74461424232170013370437 638 78158065910992773855609 639 82035263699764504339776 640 86101694424639327986953 641 90366445182089188573512 642 94839032426812320082098 643 99529421933475553725008 644 104448049671721757600587 645 109605843635492301347093 646 115014246669665729536932 647 120685240338782122705267 648 126631369884742255149629 649 132865770322301886652656 650 139402193723484100109813 651 146255037744141316871979 652 153439375448399732912617 653 160970986489021043947544 654 168866389704433076747812 655 177142877195693494905697 656 185818549949601785346048 657 194912355076916393563923 658 204444124737839155275301 659 214434616829920341894340 660 224905557517019005427145 661 235879685681215846500492 662 247380799383357089952714 663 259433804421465710271836 664 272064765080363014149737 665 285300957169722885053342 666 299170923452240954540068 667 313704531567829739709992 668 328933034564594405179824 669 344889134151952730055165 670 361607046796522729570291 671 379122572786423864993620 672 397473168395349477579409 673 416698021283240043788665 674 436838129276589093447887 675 457936382677374302667411 676 480037650256340660419568 677 503188869092854692599405 678 527439138430860621934059 679 552839817727538793100688 680 579444629079205412018421 681 607309764216689596891966 682 636493996271042338476392 683 667058796518810941604416 684 699068456325468796366885 685 732590214514710052947438 686 767694390401475519441376 687 804454522736500573176548 688 842947514821200699418224 689 883253786062509048381658 690 925457430249246883791623 691 969646380843355844770184 692 1015912583592308981029693 693 1064352176781796454385447 694 1115065679461877477903400 695 1168158187993688534379555 696 1223739581279094844347244 697 1281924735050785659285815 698 1342833745616913725687341 699 1406592163470811987045021 700 1473331237194332722062067 701 1543188168101219040735205 702 1616306376086462156447742 703 1692835777167016359081201 704 1772933073220447564158949 705 1856762054449195960530701 706 1944493915121136905700420 707 2036307583160058619450186 708 2132390064184629706435055 709 2232936800619348679373607 710 2338152046528036900236977 711 2448249258847508558498107 712 2563451505728412159148661 713 2683991892719645802702191 714 2810114007564592906895568 715 2942072384409365487127758 716 3080132988257777979146895 717 3224573720542461580581257 718 3375684946718980901498647 719 3533770046827480066620670 720 3699145990006996602026402 721 3872143933988475450434837 722 4053109850636549745550667 723 4242405178654549144029382 724 4440407504614938544086316 725 4647511273525578523786214 726 4864128530193957164725793 727 5090689692703843412854328 728 5327644359374920914354446 729 5575462150632718095039167 730 5834633587276970204145121 731 6105671006698135194351243 732 6389109518657707252951102 733 6685508002314790027542263 734 6995450146252838611941943 735 7319545533332966072835774 736 7658430772277639152894886 737 8012770677967215477935056 738 8383259502515679943044377 739 8770622219277216847160913 740 9175615862026171498059640 741 9599030921645437707626298 742 10041692802756814478058585 743 10504463342827159747814359 744 10988242396390891298179785 745 11493969487138117181928786 746 12022625530733292436029656 747 12575234631347177943665815 748 13152865955010114564782749 749 13756635683022408013380550 750 14387709048793270747401069 751 15047302461618269520340378 752 15736685721052146677520453 753 16457184325683989540819487 754 17210181880280833437684865 755 17997122605428449989647799 756 18819513953970373824009078 757 19678929338722478850092512 758 20577010976126986727092964 759 21515472850700756505158322 760 22496103805334711242967349 761 23520770762708139244792477 762 24591422083300309891541403 763 25710091065705944561963347 764 26878899595197843031406226 765 28100061946722694114571392 766 29375888748772386929191859 767 30708791114836018511532715 768 32101284949415198030520774 769 33555995435869922346483299 770 35075661713662536250458103 771 36663141752875537621947629 772 38321417434203913669081358 773 40053599842956434111493194 774 41862934785951943088997907 775 43752808540557996805791778 776 45726753845499663181757087 777 47788456143457410315684123 778 49941760085884667665607912 779 52190676310898979147485161 780 54539388505546034208443105 781 56992260764194033998676371 782 59553845255297649897090404 783 62228890209266659016027203 784 65022348240695513304347400 785 67939385018746628488645442 786 70985388300043896505864082 787 74165977339013443525658336 788 77487012691218344844471269 789 80954606425862064433890106 790 84575132764294744231162101 791 88355239162035894649343587 792 92301857852540053980992070 793 96422217871666914500521813 794 100723857582588395701782579 795 105214637721660041887503694 796 109902754986617716627994565 797 114796756189320247015181426 798 119905552996159893523875278 799 125238437280192181057375103 800 130805097110010888838838538 801 136615633401399243652897268 802 142680577258841498345979901 803 149010908035065962451750102 804 155618072137928862055180009 805 162514002615123454714024911 806 169711139548429102334645357 807 177222451290485258489314244 808 185061456578404896215027812 809 193242247559914956648511818 810 201779513769148163608356303 811 210688567090694594332129430 812 219985367752073880193893261 813 229686551386392781797317102 814 239809457208630274312348297 815 250372157350725503266997078 816 261393487402456180661924054 817 272893078206967841128022243 818 284891388961772092112422635 819 297409741678055544764411824 820 310470357053255849505036996 821 324096391814047459863766721 822 338311977589163928044454147 823 353142261373845255687164941 824 368613447650165834687914335 825 384752842230049632956777746 826 401588897890443551537519725 827 419151261872875361564301521 828 437470825322499714783098164 829 456579774744711688549388904 830 476511645560513988888516133 831 497301377845037766382428111 832 518985374336971301718246137 833 541601560810121242636161352 834 565189448901952480979256658 835 589790201497699956342997389 836 615446700772555159875449947 837 642203618998475828028664495 838 670107492226387478410315958 839 699206796958913104972151469 840 729552029933322532658108391 841 761195791139107784103550780 842 794192870199507241847225844 843 828600336251390620539301543 844 864477631463222690050913353 845 901886668336316591156003530 846 940891930940313435752520083 847 981560580239752999382851668 848 1023962563674778861468510799 849 1068170729165418657391447589 850 1114260943715546642394579412 851 1162312216799538862682266113 852 1212406828721823759780119846 853 1264630464146979318200911001 854 1319072351005787318806991579 855 1375825404990691163413956499 856 1434986379862474171880895233 857 1496656023798644462258594926 858 1560939242023041385436109826 859 1627945265965530184208619145 860 1697787829210389908472148845 861 1770585350502086757432694507 862 1846461124087627859468064919 863 1925543517685570082988297048 864 2007966178383084970769633198 865 2093868246774214268794737948 866 2183394579664664379925461421 867 2276695981681141285741430280 868 2373929446136397252136176424 869 2475258405514804757407389750 870 2580852991957472546018930999 871 2690890308140630228068058492 872 2805554708956316397483354756 873 2925038094420266460081869560 874 3049540214248399431070525567 875 3179268984560402447390330532 876 3314440817186701244186188891 877 3455280962073537884227153420 878 3602023863300051865726839982 879 3754913529241129846773910267 880 3914203917430455781892427016 881 4080159334699608744173918905 882 4253054853191328434195701894 883 4433176742868148856067062568 884 4620822921161602650688847896 885 4816303420432071671445822336 886 5019940873935223089216548946 887 5232071021017773285681974391 888 5453043232293189601177540922 889 5683221055576820468347503595 890 5922982783389969535715184264 891 6172722042873546097674538524 892 6432848408984271181330339926 893 6703788041879942319274490061 894 6985984349435106133905280689 895 7279898675864602065333077945 896 7586011017469976160281307773 897 7904820766562665944750302261 898 8236847484658287205696563445 899 8582631706078255713462346777 900 8942735773138521040865931076 901 9317744704150320062897076056 902 9708267095504752783458209785 903 10114936059161587016892737744 904 10538410196913198790928440383 905 10979374612846896277696912429 906 11438541965483254059429128266 907 11916653561124445858210705519 908 12414480490005115354757599994 909 12932824806899010940743298627 910 13472520757897650020355597104 911 14034436055142616856562367883 912 14619473201360965363599085144 913 15228570866123540462400991369 914 15862705315819091328199940640 915 16522891899412773811116382788 916 17210186592136283161189733911 917 17925687599338369929176207269 918 18670537022809140909008725957 919 19445922591979282772037199380 920 20253079462486452500278428901 921 21093292084695507250354668649 922 21967896144857296112439318510 923 22878280581692361003958580483 924 23825889681291409134940712898 925 24812225253333781368509341260 926 25838848891738682064312680232 927 26907384322981615954038142715 928 28019519845430647161371563011 929 29177010863183717510399309102 930 30381682518019705945732278501 931 31635432423212145143530089020 932 32940233503095925841950166925 933 34298136942423885603166635141 934 35711275249702308901183941575 935 37181865438852036402913086617 936 38712212333705528258573553453 937 40304712000019831854952778511 938 41961855309861428310779677199 939 43686231643401363356054203848 940 45480532733348392406053262951 941 47347556657444083420616096191 942 49290211984647437102451360445 943 51311522080847607257217660185 944 53414629580162276263964012116 945 55602801028106175948641533459 946 57879431703149714997175777712 947 60248050623431705035567101066 948 62712325745643373502524314302 949 65276069363363248481829979707 950 67943243712394738201004585330 951 70717966790940354544940251946 952 73604518402739221837696717253 953 76607346431597831815348301538 954 79731073356058668243412293223 955 82980503013277407828245068283 956 86360627621517664392052336454 957 89876635071022775333361168794 958 93533916493387733549300989060 959 97338074119931157343693141433 960 101294929439958012361605014652 961 105410531670208786629072443047 962 109691166547210868843748205865 963 114143365454683146675079840637 964 118773914898596275107652948797 965 123589866342958844595305740247 966 128598546419884809969032320551 967 133807567528000229978455457236 968 139224838833768678424765002619 969 144858577690854856306453643485 970 150717321493206087744723607067 971 156809939978111787506414104468 972 163145647996102839253193773070 973 169734018765176422438815881164 974 176584997627478437929089597619 975 183708916327245646571171131656 976 191116507829504292789684985359 977 198818921699741716216422919284 978 206827740065513680661043205397 979 215154994181723295054525562123 980 223813181622108973387871126946 981 232815284120309351832496825336 982 242174786084734050404216045099 983 251905693812361157628949929943 984 262022555427507025898549316374 985 272540481572571973095036425534 986 283475166878758592037164932826 987 294842912245788215231544855104 988 306660647960707577526336027821 989 318945957686982571942562873338 990 331717103356221230244166735055 991 344993050996054460084558108497 992 358793497528932785246520435644 993 373138898577871222851497472442 994 388050497316494774222345978685 995 403550354402104746933198779509 996 419661379031903688089659539213 997 436407361163985126799856398515 998 453813004946216170735868829566 999 471903963397717409869912821822 1000 490706874389278283199666978764