0 1 1 1 2 2 3 3 4 4 5 7 6 10 7 14 8 19 9 27 10 37 11 50 12 67 13 88 14 115 15 153 16 196 17 253 18 324 19 412 20 524 21 661 22 828 23 1036 24 1290 25 1603 26 1980 27 2443 28 2997 29 3671 30 4487 31 5460 32 6631 33 8034 34 9703 35 11703 36 14075 37 16890 38 20226 39 24175 40 28838 41 34332 42 40801 43 48394 44 57307 45 67765 46 79974 47 94249 48 110901 49 130292 50 152876 51 179109 52 209550 53 244844 54 285721 55 333001 56 387618 57 450665 58 523329 59 607030 60 703363 61 814041 62 941161 63 1086997 64 1254130 65 1445561 66 1664560 67 1914888 68 2200819 69 2527132 70 2899230 71 3323157 72 3805823 73 4354842 74 4978967 75 5687947 76 6492595 77 7405299 78 8439811 79 9611501 80 10937822 81 12438005 82 14133773 83 16049413 84 18212085 85 20652059 86 23403197 87 26503350 88 29994600 89 33924084 90 38344353 91 43313518 92 48896948 93 55166950 94 62204076 95 70098144 96 78948612 97 88866149 98 99973859 99 112408192 100 126320648 101 141879120 102 159270122 103 178699808 104 200397248 105 224615794 106 251635457 107 281766918 108 315353373 109 352774088 110 394449086 111 440841360 112 492462952 113 549879155 114 613713885 115 684655226 116 763462260 117 850972075 118 948106711 119 1055882808 120 1175420001 121 1307949780 122 1454829621 123 1617551809 124 1797758048 125 1997254439 126 2218025132 127 2462251098 128 2732328936 129 3030890141 130 3360824050 131 3725301770 132 4127803794 133 4572146548 134 5062517232 135 5603505611 136 6200140603 137 6857935240 138 7582926878 139 8381726750 140 9261575068 141 10230393446 142 11296851486 143 12470433385 144 13761511176 145 15181424639 146 16742569360 147 18458491918 148 20343990332 149 22415230217 150 24689863287 151 27187156739 152 29928144782 153 32935775941 154 36235085040 155 39853379345 156 43820430350 157 48168695064 158 52933549023 159 58153537414 160 63870650487 161 70130621494 162 76983250813 163 84482750030 164 92688128419 165 101663596590 166 111479006744 167 122210345541 168 133940240847 169 146758528687 170 160762866951 171 176059381682 172 192763388257 173 211000159687 174 230905754795 175 252627918465 176 276327053979 177 302177275276 178 330367532702 179 361102851316 180 394605643602 181 431117133067 182 470898916155 183 514234606749 184 561431638963 185 612823215305 186 668770377544 187 729664279229 188 795928614850 189 868022239103 190 946441994608 191 1031725764516 192 1124455759244 193 1225262047065 194 1334826387643 195 1453886328898 196 1583239623482 197 1723749031617 198 1876347419805 199 2042043302616 200 2221926804596 201 2417176037371 202 2629064013383 203 2858966062228 204 3108367796765 205 3378873701160 206 3672216361313 207 3990266399036 208 4335043121629 209 4708726032592 210 5113667136319 211 5552404185927 212 6027674974186 213 6542432593043 214 7099861889963 215 7703397159021 216 8356741058913 217 9063885028972 218 9829131153964 219 10657115640458 220 11552834023177 221 12521668235866 222 13569415646755 223 14702320195182 224 15927105862912 225 17251012505484 226 18681834289942 227 20227961035346 228 21898422362699 229 23702935164478 230 25651954481511 231 27756727949638 232 30029354271677 233 32482845834122 234 35131195765338 235 37989449834011 236 41073783456019 237 44401584198681 238 47991540071238 239 51863734222275 240 56039746173853 241 60542760267866 242 65397681883591 243 70631261616597 244 76272228327125 245 82351431560248 246 88901993741695 247 95959473249168 248 103562038733196 249 111750655584943 250 120569285386223 251 130065099248265 252 140288705892441 253 151294395472526 254 163140400388136 255 175889173905457 256 189607687974766 257 204367751777207 258 220246351715473 259 237326014989205 260 255695198005723 261 275448701094904 262 296688111753765 263 319522277948447 264 344067813477063 265 370449637723183 266 398801551925556 267 429266854429892 268 461998997313250 269 497162287575355 270 534932635135452 271 575498351200468 272 619061000456737 273 665836309813819 274 716055138229065 275 769964511335078 276 827828724581694 277 889930520283177 278 956572342589290 279 1028077675673582 280 1104792470594052 281 1187086666580143 282 1275355812659466 283 1370022796086558 284 1471539684877182 285 1580389691011041 286 1697089262518910 287 1822190313185750 288 1956282597237922 289 2099996239768270 290 2254004432174779 291 2419026302636847 292 2595829973856812 293 2785235819096036 294 2988119929129151 295 3205417803870284 296 3438128282607728 297 3687317727927454 298 3954124479025213 299 4239763592285455 300 4545531885748402 301 4872813307544938 302 5223084648982873 303 5597921622063518 304 5999005326079969 305 6428129126925447 306 6887205973810749 307 7378276182519514 308 7903515712640242 309 8465244969791761 310 9065938165666536 311 9708233270333488 312 10394942593094873 313 11129064030605617 314 11913793024384283 315 12752535269605446 316 13648920222506210 317 14606815456276845 318 15630341914535392 319 16723890120358001 320 17892137398028485 321 19140066168142770 322 20472983383974357 323 21896541176640747 324 23416758782777036 325 25040045833318394 326 26773227085535248 327 28623568685532545 328 30598806053422003 329 32707173490879468 330 34957435612164965 331 37358920710409463 332 39921556176557879 333 42655906090382500 334 45573211118025880 335 48685430852761374 336 52005288743260255 337 55546319767817974 338 59322921015501142 339 63350405348001518 340 67645058326551558 341 72224198597689634 342 77106241942866178 343 82310769208933491 344 87858598351740738 345 93771860832308859 346 100074082625546452 347 106790270115215618 348 113947001157536260 349 121572521623721841 350 129696847741402409 351 138351874572785795 352 147571490994938632 353 157391701558957113 354 167850755631202831 355 178989284243536263 356 190850445102077207 357 203480076229412456 358 216926858742781081 359 231242489302718155 360 246481862788569086 361 262703265798028143 362 279968581600270544 363 298343507197430102 364 317897783203245271 365 338705437275617602 366 360845041881295126 367 384399987225722269 368 409458770215216589 369 436115300373412900 370 464469223687694344 371 494626265412624210 372 526698592915527535 373 560805199710068325 374 597072311893480303 375 635633818257961819 376 676631725431946855 377 720216639479042265 378 766548275448698362 379 815795996478253411 380 868139384119443705 381 923768841653401806 382 982886232273284259 383 1045705554097876688 384 1112453654098438699 385 1183370983137039318 386 1258712394433181893 387 1338747987901732176 388 1423764002942240425 389 1514063762407076957 390 1609968670610024697 391 1711819268411548047 392 1819976348581286868 393 1934822134792251077 394 2056761527819376105 395 2186223422685586583 396 2323662100703555394 397 2469558700597568090 398 2624422773093850487 399 2788793923617050011 400 2963243547988266082 401 3148376666277878921 402 3344833860248033535 403 3553293320113780141 404 3774473006673813136 405 4009132935162696344 406 4258077587549008704 407 4522158460358715555 408 4802276755460226404 409 5099386221691184761 410 5414496155602049490 411 5748674570031544213 412 6103051539732120301 413 6478822733718663142 414 6877253144552654663 415 7299681025322402287 416 7747522045650750945 417 8222273678662942568 418 8725519831491066685 419 9258935732570859913 420 9824293089663691786 421 10423465533311294038 422 11058434361208998981 423 11731294599763758543 424 12444261400034068403 425 13199676786111790487 426 14000016774964018691 427 14847898887798930853 428 15746090074034524890 429 16697515070080607664 430 17705265216328318577 431 18772607756957338515 432 19902995648470614388 433 21100077904228477921 434 22367710503709028304 435 23709967896678349677 436 25131155134094192722 437 26635820659216751579 438 28228769794106015400 439 29915078958605807430 440 31700110660797629188 441 33589529299931298575 442 35589317825044879457 443 37705795294661313002 444 39945635385349195438 445 42315885899423162511 446 44823989324660748197 447 47477804501646916913 448 50285629457254694591 449 53256225465814675907 450 56398842402655961440 451 59723245458107475420 452 63239743283556607865 453 66959217644776311734 454 70893154661736356776 455 75053677718100979924 456 79453582127898101932 457 84106371651416871487 458 89026296957031358675 459 94228396130642168976 460 99728537339664359779 461 105543463763932386443 462 111690840911647651493 463 118189306444532628270 464 125058522642734390832 465 132319231646584628773 466 139993313619418774619 467 148103847982966628810 468 156675177884448242300 469 165732978062749758762 470 175304326289449446206 471 185417778569361880557 472 196103448294754817630 473 207393089557084823695 474 219320184830479860170 475 231920037252036594748 476 245229867735346123400 477 259288917165573711459 478 274138553936965109541 479 289822387106817006629 480 306386385453635924076 481 323879002741795827285 482 342351309510171347226 483 361857131718011609183 484 382453196598265594535 485 404199286085944947790 486 427158398207510121157 487 451396916836710846752 488 476984790242407415754 489 503995718875202949546 490 532507352862048932027 491 562601499701305370060 492 594364342675263798998 493 627886670522868059515 494 663264118942406775381 495 700597424522072895814 496 739992691726145633718 497 781561673595608500427 498 825422066854484000763 499 871697822147657994057 500 920519470171654709177 501 972024464497405079056 502 1026357541923717377637 503 1083671101241265252952 504 1144125601330375120406 505 1207889979561375210402 506 1275142091513872932920 507 1346069173081247969845 508 1420868326079057237005 509 1499747028530979390012 510 1582923670863262934208 511 1670628119299158825499 512 1763102307807974306847 513 1860600860029361710231 514 1963391742663280303617 515 2071756951888517692482 516 2185993234448873938345 517 2306412845126253790002 518 2433344342403319508197 519 2567133424206167637400 520 2708143805709465518162 521 2856758141282659578187 522 3013378992756737566388 523 3178429846296731885561 524 3352356180275961862695 525 3535626586663690925411 526 3728733948559703117333 527 3932196676636466055960 528 4146560007382546969721 529 4372397366181082179929 530 4610311798402986022877 531 4860937471847688346043 532 5124941254024994373108 533 5403024367939214886495 534 5695924130212824254277 535 6004415775571200477355 536 6329314371902820274074 537 6671476830311243620559 538 7031804014786823091276 539 7411242956347630536914 540 7810789176730616460359 541 8231489126957200586204 542 8674442746351565809478 543 9140806147855567753661 544 9631794435763452575535 545 10148684662290657754257 546 10692818929696171311859 547 11265607644997924130270 548 11868532934654582799377 549 12503152226937356463095 550 13171102010081939787124 551 13874101774693986611618 552 14613958149282789732198 553 15392569238217895094521 554 16211929171843035591942 555 17074132878941178419465 556 17981381092226346861519 557 18935985598041313601131 558 19940374741966654325152 559 20997099202598932819316 560 22108838046332010086501 561 23278405076578927182913 562 24508755491503941846221 563 25802992864994137993585 564 27164376466291402073530 565 28596328934428655004806 566 30102444324370274000770 567 31686496542547636030243 568 33352448190308307806931 569 35104459834663060802345 570 36946899726619478570186 571 38884353988338474675277 572 40921637291340057319742 573 43063804049019510052220 574 45316160147819439694657 575 47684275242534833601683 576 50173995642412535815842 577 52791457815945932025500 578 55543102543559679598164 579 58435689748733800998043 580 61476314039532540464738 581 64672420993983444128408 582 68031824224299791160259 583 71562723256557831519374 584 75273722264132210633172 585 79173849694960628623351 586 83272578834558618555400 587 87579849348637724703076 588 92106089851199626801155 589 96862241546092185218426 590 101859782992219541395998 591 107110756044905426951455 592 112627793028321441718517 593 118424145196411073871032 594 124513712542374747406079 595 130911075019534322006085 596 137631525239271925885128 597 144691102714744304418395 598 152106629722215768790163 599 159895748855136050229521 600 168076962349518614041275 601 176669673262760805754477 602 185694228591792066372507 603 195171964420348338901947 604 205125253189261448005063 605 215577553187922249633391 606 226553460369538753012260 607 238078762597474164626682 608 250180496434818458228891 609 262887006594435568505573 610 276228008172043507215452 611 290234651790435956079266 612 304939591788752765744044 613 320377057596764388284017 614 336582928440462253536354 615 353594811531853534354742 616 371452123902761946850291 617 390196178049643595672699 618 409870271563952666086698 619 430519780930455960641975 620 452192259684102696187332 621 474937541124628687320745 622 498807845797028230153773 623 523857893955372692836891 624 550145023237216409230833 625 577729311786022857609564 626 606673707069684688067796 627 637044160654321494492049 628 668909769204139546910243 629 702342921990248810901427 630 737419455203973877287862 631 774218813383397079215685 632 812824218275650403305313 633 853322845471854665679334 634 895806009166623220072483 635 940369355409718303076224 636 987113064233807776452427 637 1036142061059349278283025 638 1087566237795449275412414 639 1141500684074148523725331 640 1198065929075001820954685 641 1257388194417082614008101 642 1319599658616690323509448 643 1384838733631108870472351 644 1453250354031796903577954 645 1524986279374422283247751 646 1600205410358236818208587 647 1679074119393457668562545 648 1761766596222627322425916 649 1848465209270423750958179 650 1939360883426120029248478 651 2034653494993913223025124 652 2134552284578711184284155 653 2239276288708729471795927 654 2349054791031480735701263 655 2464127793956492992767067 656 2584746511656433474283365 657 2711173885378312559290863 658 2843685122058167816676548 659 2982568257276154019092917 660 3128124743634362934528733 661 3280670065687058686035472 662 3440534382602409937649741 663 3608063199786318955971356 664 3783618070752691829402608 665 3967577330580537102343333 666 4160336862356733527032114 667 4362310898064275593409172 668 4573932855439377918276589 669 4795656212387124288416886 670 5027955420614491111673527 671 5271326860211676195877554 672 5526289836987850012613145 673 5793387624445849359259702 674 6073188552362084807954144 675 6366287144023170479298899 676 6673305304259668108921750 677 6994893560510004317398393 678 7331732359244231904834994 679 7684533420178046424067487 680 8054041150812481840825985 681 8441034123944193950664418 682 8846326620905385074468564 683 9270770243411404648799530 684 9715255597018100590469309 685 10180714049320299069208000 686 10668119566157570274593184 687 11178490629233930537800117 688 11712892238704574386914747 689 12272438004435370336724328 690 12858292329799941894764673 691 13471672692044980029330332 692 14113852023427251786870414 693 14786161197505879276649467 694 15489991625161187118334316 695 16226797965107035854667641 696 16998100953867425719590124 697 17805490360400615555856584 698 18650628070775384108624422 699 19535251308534765234078098 700 20461175996622986888607143 701 21430300267001833981161987 702 22444608124343660188092042 703 23506173270460231112492062 704 24617163096409937129076928 705 25779842849521133471214657 706 26996579982876960435256828 707 28269848695127451391053190 708 29602234668828585065547599 709 30996440015855763093607812 710 32455288438801519692835444 711 33981730617644729535158002 712 35578849831371795282951903 713 37249867824639883539116521 714 38998150929998943765945424 715 40827216456633676684075858 716 42740739357049536096733306 717 44742559183609020609477934 718 46836687347326726971323243 719 49027314691854711990604528 720 51318819396134486121847759 721 53715775219759361304065297 722 56222960105681782838257456 723 58845365155515661286601205 724 61588203993324618136918065 725 64456922534454450219728871 726 67457209176663122903634730 727 70595005431525352507328079 728 73876517014842457973868705 729 77308225415572916178536633 730 80896899963616187896527269 731 84649610417633202036700918 732 88573740094972772263277497 733 92676999566695600999833171 734 96967440941647870916312946 735 101453472764536263313574105 736 106143875553997215601594457 737 111047818007736956936725736 738 116174873902947080761259106 739 121535039721374975003229847 740 127138753029651126349564683 741 132996911646748147874347522 742 139120893631771375700202955 743 145522578126660092472642460 744 152214367089814107276549428 745 159209207958154807745305429 746 166520617276685249985448970 747 174162705336232844325404848 748 182150201861743285788566524 749 190498482795248219226245274 750 199223598219454464301273775 751 208342301469802384599519907 752 217872079484818089730917820 753 227831184446641731748396958 754 238238666765755480044062686 755 249114409466163091308069814 756 260479164029591885503704690 757 272354587759701031400745039 758 284763282729791028127518633 759 297728836380122138933714449 760 311275863833668326013148255 761 325430052001962169330550267 762 340218205555629741843825286 763 355668294837277036668059076 764 371809505797576030554545582 765 388672292038713743892763980 766 406288429052816914076138794 767 424691070746553393966943160 768 443914808346844674857952941 769 463995731786507851604261662 770 484971493672685747862020298 771 506881375945127112369779769 772 529766359335751249038833139 773 553669195745479780617374895 774 578634483659049536637072229 775 604708746723442016349695635 776 631940515620684011424972907 777 660380413371098638789602179 778 690081244208624362295600904 779 721098086175580007376340127 780 753488387590245043215050174 781 787312067546855732586768430 782 822631620614098498047306275 783 859512225904921895581810659 784 898021860697498238943501022 785 938231418794455643808475015 786 980214833815082202777812401 787 1024049207623087640873758585 788 1069814944100705920569401859 789 1117595888488447364287138479 790 1167479472518673735346886410 791 1219556865580387687997941534 792 1273923132162212955491072969 793 1330677395830508003483009881 794 1389923010009918560107202108 795 1451767735844448952915462340 796 1516323927428334774955195965 797 1583708724707646700202400174 798 1654044254365664700778314486 799 1727457839017651686972738494 800 1804082215053744252945590365 801 1884055759482285409654620502 802 1967522726140070177118356723 803 2054633491650680568700457927 804 2145544811527373815194753549 805 2240420086832879262265849031 806 2339429641824978729491986651 807 2442751013033916740042297249 808 2550569250235536304793038535 809 2663077229802589205019438325 810 2780475980935954289369474741 811 2902975025297541747233375424 812 3030792730587494976358285285 813 3164156678629955209091704346 814 3303304048554159455722144004 815 3448482015681032329478220785 816 3599948166749741398839427470 817 3757970932143949491608715537 818 3922830035803752607225384602 819 4094816963536577350862623088 820 4274235450468666830171778710 821 4461401988408250054897806377 822 4656646353922110024071650563 823 4860312157959084448971844666 824 5072757417887096644628993519 825 5294355152844670499144040928 826 5525494003343582606224537846 827 5766578876096398146804757752 828 6018031615081178670950816882 829 6280291699895695497120188933 830 6553816972495089516655912833 831 6839084393450147046868318521 832 7136590828908274354617711554 833 7446853869485915011732059623 834 7770412682369631719858450283 835 8107828897953437232361661755 836 8459687532392279735224479081 837 8826597947505941643279823264 838 9209194849524075103788324820 839 9608139328221753336774468825 840 10024119938055848080626491916 841 10457853822975837108861539903 842 10910087886648392072927057612 843 11381600009903389590525118583 844 11873200317279925024262833595 845 12385732494624589262206919002 846 12920075159770799009792817197 847 13477143288407459310627931560 848 14057889697327795636926258165 849 14663306587334939215305757284 850 15294427148169904506305778137 851 15952327227920087761668528785 852 16638127069462471062577356674 853 17352993116595472749531688096 854 18098139892616983218914711330 855 18874831954213710493834041674 856 19684385923638684394814383188 857 20528172602269788203873626878 858 21407619168762665389826726890 859 22324211465136455525837866653 860 23279496374260722714517614835 861 24275084292346833842861337826 862 25312651700187111473031604516 863 26393943837030522392905749025 864 27520777481134671154040284058 865 28695043841190658680139814852 866 29918711562980157476321775273 867 31193829855793073720250090911 868 32522531743309647511817529245 869 33907037443833029359077017722 870 35349657884947516212572938418 871 36852798357873996497017978380 872 38418962316998012036793791765 873 40050755330257477581208342137 874 41750889186296798601059994937 875 43522186164522197714198361832 876 45367583474429814462395225971 877 47290137870823908408106653371 878 49293030451797609366375739634 879 51379571646613472294450175871 880 53553206400895971463763563483 881 55817519566833386065516341523 882 58176241506382678623160713799 883 60633253915778354106623355383 884 63192595879965331879645671763 885 65858470165907000526713430207 886 68635249764063309805665651873 887 71527484687690452735498224936 888 74539909039983890407606906379 889 77677448359470677016577263673 890 80945227254455774557630874447 891 84348577337740848032901686325 892 87893045473263464665123603971 893 91584402346750266293373751912 894 95428651372940147271627146430 895 99432037952413376551589656138 896 103601059091560600984812146183 897 107942473399742430198998337627 898 112463311478226529197527773678 899 117170886716045555955977134298 900 122072806508496627145994949233 901 127176983914602053243364499123 902 132491649770472659406700471288 903 138025365276159935717301221741 904 143787035074252405711549598058 905 149785920839165861592312579952 906 156031655396797418677803401196 907 162534257394960654435881601396 908 169304146545794417061385021250 909 176352159462142251240946584055 910 183689566110733867447777799071 911 191328086905865787905173493324 912 199279910468176390380487966925 913 207557712074042235128606947204 914 216174672822089038739110796888 915 225144499544313234599443129731 916 234481445490350063971904114441 917 244200331814502951842683285273 918 254316569896267966498084539621 919 264846184526247922385239153990 920 275805837990554695004576291165 921 287212855088047165082298770111 922 299085249116047544674298653236 923 311441748861522366308738634480 924 324301826636107907850277285049 925 337685727394805113187732302071 926 351614498979668051264344200952 927 366110023531364601864574795377 928 381195050113100405395194331120 929 396893228593069278425344722704 930 413229144833327466232838566290 931 430228357234787547400799522040 932 447917434689892872913107479844 933 466323995996467548663115382854 934 485476750788242679820487138152 935 505405542039639500309371555078 936 526141390204546820067218186059 937 547716539051066742573961843156 938 570164503256521740782097680486 939 593520117829420943543678981069 940 617819589427576996049990961442 941 643100549644150347935387963801 942 669402110336078639787007513325 943 696764921072128470966369832656 944 725231228780688831094795297327 945 754844939680413585477742470069 946 785651683579918477205507483058 947 817698880635950137370455312050 948 851035810662774716393654989680 949 885713685088986249395714098155 950 921785721661514182492175584209 951 959307222000320212808053874288 952 998335652111121494058647279990 953 1038930725967465261253238548027 954 1081154492277614141450027035541 955 1125071424555987131738487341271 956 1170748514623343918935170872969 957 1218255369664505562497472737057 958 1267664312977178439638051591449 959 1319050488550396845156384596491 960 1372491969616229050868815766678 961 1428069871323708489587402328297 962 1485868467689462794629511744262 963 1545975312985225698806279577569 964 1608481367728337527894072028459 965 1673481129447476717370504302061 966 1741072768402225213778110178013 967 1811358268441662844052140651634 968 1884443573194018081830837694446 969 1960438737786483743263417631404 970 2039458086301644943943277966594 971 2121620375184572398015742545780 972 2207048962822516424425161809114 973 2295871985527305766828816297974 974 2388222540159020806846955816193 975 2484238873638283592841417410466 976 2584064579603598334718035240843 977 2687848802479597031270192280596 978 2795746449231807508339955515900 979 2907918409093677579994722920922 980 3024531781562071954095319521053 981 3145760112968320993517727500814 982 3271783641943156080917535295971 983 3402789554105529159895701078294 984 3538972246317398580663888370530 985 3680533600859084714699884048161 986 3827683269892772501700433728278 987 3980638970595180284833826864746 988 4139626791354341675638844866403 989 4304881509439877053021739199852 990 4476646920571081535200306400226 991 4655176180822645394024134989242 992 4840732161323870078856269725332 993 5033587816223868129826500435465 994 5234026564412458833954615653748 995 5442342685504314772738101323420 996 5658841730612399439705008570686 997 5883840948455885653579892431121 998 6117669727367582134564042817401 999 6360670053786445757286520270372 1000 6613196987842044904360019879485