0 1 1 0 2 0 3 1 4 2 5 5 6 6 7 11 8 13 9 17 10 23 11 29 12 34 13 47 14 64 15 74 16 107 17 136 18 185 19 233 20 308 21 392 22 518 23 637 24 814 25 1002 26 1272 27 1560 28 1912 29 2339 30 2863 31 3475 32 4212 33 5123 34 6147 35 7398 36 8935 37 10734 38 12843 39 15464 40 18382 41 22041 42 26249 43 31326 44 37213 45 44273 46 52375 47 62103 48 73376 49 86605 50 101993 51 120156 52 141037 53 165398 54 193627 55 226507 56 264476 57 308420 58 359154 59 417640 60 485285 61 562758 62 652318 63 754741 64 873249 65 1008331 66 1163637 67 1341250 68 1545373 69 1777316 70 2044090 71 2347405 72 2694668 73 3089713 74 3541183 75 4053451 76 4638712 77 5301457 78 6057065 79 6913577 80 7887421 81 8988490 82 10240167 83 11654764 84 13257336 85 15069117 86 17117473 87 19429330 88 22042003 89 24987490 90 28308977 91 32051120 92 36265795 93 41007594 94 46342608 95 52340101 96 59075301 97 66642245 98 75131401 99 84655682 100 95332504 101 107298572 102 120695425 103 135698099 104 152476366 105 171251525 106 192226413 107 215672936 108 241846606 109 271076872 110 303678564 111 340053697 112 380588853 113 425778051 114 476097972 115 532138299 116 594491485 117 663884257 118 741032066 119 826813349 120 922112889 121 1027986290 122 1145525668 123 1276007839 124 1420749003 125 1581310969 126 1759305877 127 1956579938 128 2175126872 129 2417192124 130 2685152642 131 2981726428 132 3309829899 133 3672691967 134 4073862392 135 4517239886 136 5007088860 137 5548111262 138 6145483247 139 6804777638 140 7532281729 141 8334730379 142 9219602455 143 10194999314 144 11269970921 145 12454148750 146 13758417357 147 15194357353 148 16774928538 149 18514050462 150 20427271971 151 22531130891 152 24844281060 153 27386517832 154 30180036868 155 33248506877 156 36618441102 157 40318017329 158 44378839839 159 48834535428 160 53722649360 161 59083302485 162 64961124366 163 71403787548 164 78464383427 165 86199604340 166 94672412901 167 103950173739 168 114107523196 169 125224437409 170 137389319715 171 150697114357 172 165252345166 173 181167526697 174 198566306857 175 217581928183 176 238360465215 177 261059515618 178 285851631545 179 312923066099 180 342477292779 181 374734486310 182 409934410831 183 448336744430 184 490224260380 185 535902890637 186 585705494660 187 639992810086 188 699156163323 189 763620040364 190 833844779273 191 910329681215 192 993615250486 193 1084288553771 194 1182984134070 195 1290391078497 196 1407254564268 197 1534382661862 198 1672648725292 199 1823001315753 200 1986463177335 201 2164145212378 202 2357246067225 203 2567066045428 204 2795007215141 205 3042591890525 206 3311459537507 207 3603389375805 208 3920298593396 209 4264265349197 210 4637528687508 211 5042516453919 212 5481841370328 213 5958335481612 214 6475048634289 215 7035282534380 216 7642592206653 217 8300826486993 218 9014126998268 219 9786975888349 220 10624197323246 221 11531007016245 222 12513018888084 223 13576301744471 224 14727384059695 225 15973319783800 226 17321700139943 227 18780720023207 228 20359197181717 229 22066649183370 230 23913313534792 231 25910234706654 232 28069294450663 233 30403301430192 234 32926035523487 235 35652347084372 236 38598207384542 237 41780820782839 238 45218691929204 239 48931742848617 240 52941398006888 241 57270715457788 242 61944488178229 243 66989388265065 244 72434092286288 245 78309436633752 246 84648571687900 247 91487131574848 248 98863417764778 249 106818585918801 250 115396867194906 251 124645772334353 252 134616352710710 253 145363427355892 254 156945890169127 255 169426962740671 256 182874551218155 257 197361531248232 258 212966164484556 259 229772412521355 260 247870426404827 261 267356897504800 262 288335618223680 263 310917888000219 264 335223153799119 265 361379461782707 266 389524209555728 267 419804651969592 268 452378751236226 269 487415773099805 270 525097251231514 271 565617651581624 272 609185500279717 273 656024130989990 274 706372951234778 275 760488332444839 276 818645030379686 277 881137196118795 278 948280014782465 279 1020410851608856 280 1097891091900816 281 1181107499066791 282 1270474273737391 283 1366434594549446 284 1469462991519673 285 1580067101168520 286 1698790309635555 287 1826213839348908 288 1962959697616434 289 2109693049133525 290 2267125599545901 291 2436018296275813 292 2617185108820999 293 2811496212032456 294 3019882185192255 295 3243337658767061 296 3482926104465060 297 3739783996551500 298 4015126145243604 299 4310250571726429 300 4626544468595741 301 4965489731989918 302 5328669767700661 303 5717775789631107 304 6134614412761248 305 6581114992088812 306 7059338075651317 307 7571483776608921 308 8119901386409296 309 8707098881772119 310 9335753673546109 311 10008723590062106 312 10729058925155365 313 11500014895140524 314 12325065291283636 315 13207916657756696 316 14152523575670857 317 15163104946835037 318 16244161104575813 319 17400492294549719 320 18637218078810314 321 19959798261586407 322 21374054666257823 323 22886195047480869 324 24502837544543544 325 26231037756254693 326 28078316393963616 327 30052689934157582 328 32162701718313354 329 34417456781680934 330 36826656832013951 331 39400639618837150 332 42150418507036533 333 45087726918803878 334 48225062854518320 335 51575739278378347 336 55153934244483283 337 58974747772996925 338 63054258403881628 339 67409587356053352 340 72058962345321212 341 77021789921406386 342 82318727410441290 343 87971764473453851 344 94004304255405677 345 100441255235335632 346 107309122721457671 347 114636112289197399 348 122452232963001045 349 130789413621815864 350 139681619269327418 351 149164982013709076 352 159277932222610230 353 170061345668510196 354 181558691363462023 355 193816197067605122 356 206883015742160448 357 220811411556387025 358 235656947529711375 359 251478694181350515 360 268339441106238214 361 286305931327232787 362 305449099230018224 363 325844333783298655 364 347571746632111565 365 370716467048533241 366 395368943837066926 367 421625276467411567 368 449587554364660876 369 479364228416648217 370 511070492963831929 371 544828701698028775 372 580768797677835275 373 619028779707675500 374 659755185083911836 375 703103612664674782 376 749239265810477387 377 798337537564409592 378 850584621067484003 379 906178165602040325 380 965327961170392579 381 1028256673676252056 382 1095200614193718971 383 1166410560959066405 384 1242152623445127129 385 1322709163203530420 386 1408379762063488250 387 1499482253541179066 388 1596353809542230734 389 1699352093143240163 390 1808856477850292654 391 1925269338271265300 392 2049017415181515415 393 2180553260257836491 394 2320356766516043590 395 2468936782608039425 396 2626832828024479890 397 2794616899415218204 398 2972895389337793107 399 3162311107056609632 400 3363545427421143962 401 3577320548037395775 402 3804401895059858026 403 4045600647516398533 404 4301776426265636497 405 4573840116459279393 406 4862756876114831966 407 5169549287368299959 408 5495300721454665147 409 5841158860840012207 410 6208339457500271775 411 6598130268675897681 412 7011895257518037067 413 7451078985968244879 414 7917211308700068643 415 8411912279629331519 416 8936897390795241421 417 9493983051833620270 418 10085092440277014421 419 10712261614879046875 420 11377646046625840526 421 12083527443049191567 422 12832321032613245627 423 13626583180940222234 424 14469019518094493148 425 15362493432209119423 426 16310035135385065678 427 17314851138397144686 428 18380334355695610869 429 19510074673295899382 430 20707870213982981308 431 21977739117024815798 432 23323932093490530041 433 24750945559088608798 434 26263535620207947281 435 27866732711403549505 436 29565857175970781356 437 31366535572972458125 438 33274718030624686948 439 35296696413975811618 440 37439123642858072015 441 39709033929423978241 442 42113864282936737414 443 44661477043336873373 444 47360183815398054543 445 50218770557161060967 446 53246524209964185578 447 56453260624691262114 448 59849354186639198142 449 63445768893482822380 450 67254091305121085594 451 71286565122729448029 452 75556127826949293283 453 80076449145013967002 454 84861971784920794801 455 89927954215988115199 456 95290515947105571831 457 100966685095789237392 458 106974448708862906340 459 113332805644239805037 460 120061822481160202032 461 127182692299570522861 462 134717796790117227220 463 142690771570118048219 464 151126575171318152026 465 160051561604717638928 466 169493556969132970451 467 179481940057576472088 468 190047727411107663233 469 201223662833865380151 470 213044311814625987084 471 225546160913493672220 472 238767722551481959041 473 252749645347400020785 474 267534830396047965978 475 283168553720183135401 476 299698595285934025417 477 317175374874599627736 478 335652095190161085700 479 355184892607742511093 480 375832995879952996114 481 397658893341247674708 482 420728508904131489217 483 445111387475965432255 484 470880890070963136688 485 498114399406292558330 486 526893536171512747581 487 557304386926186578805 488 589437743802651799817 489 623389357080864105618 490 659260200785900552857 491 697156752586878660442 492 737191288034672414864 493 779482190647236410683 494 824154277859439731251 495 871339144481162877572 496 921175523670722396220 497 973809667331949359461 498 1029395745806467042692 499 1088096269055888412621 500 1150082529193484133782 501 1215535066740505424948 502 1284644160455782093491 503 1357610343443438462863 504 1434644945242775668490 505 1515970662956462093930 506 1601822161134398816808 507 1692446703670802294347 508 1788104817463780770814 509 1889070991491591954988 510 1995634410902577453632 511 2108099730202583508978 512 2226787885180069806872 513 2352036947912174086618 514 2484203024556255895673 515 2623661200734522797807 516 2770806534104506141108 517 2926055099417604490844 518 3089845085770490919172 519 3262637951645258889763 520 3444919637587756007841 521 3637201842676105032423 522 3840023364544018367698 523 4053951509707415654978 524 4279583574154008000430 525 4517548401297251352725 526 4768508017511983559351 527 5033159352975532285875 528 5312236048061465852082 529 5606510353681129206486 530 5916795126159380458508 531 6243945925449627540528 532 6588863217683832270916 533 6952494691593950142624 534 7335837689961117875391 535 7739941766397602987572 536 8165911369158724383973 537 8614908662767577593100 538 9088156489782877721630 539 9586941484315394938156 540 10112617340004499867177 541 10666608244950024431101 542 11250412487095515690138 543 11865606243144617290585 544 12513847555430564206647 545 13196880510751635747773 546 13916539626298675639054 547 14674754457683714236589 548 15473554435355936237977 549 16315073945106815735491 550 17201557660264158708695 551 18135366142373319530029 552 19118981719064380932139 553 20155014657078043830619 554 21246209640751341076859 555 22395452574826265028812 556 23605777723690921251436 557 24880375207181744633214 558 26222598866743261099759 559 27635974523444123462138 560 29124208643838654188645 561 30691197436312722940567 562 32341036396364240641889 563 34078030324971217978809 564 35906703840921814812603 565 37831812412900565890014 566 39858353935154829791687 567 41991580874056064895560 568 44237013012643367765057 569 46600450822321373302259 570 49087989492173169196447 571 51706033647119186088755 572 54461312789262916041500 573 57360897495682746168071 574 60412216411319197296794 575 63623074072581305134481 576 67001669604893205973726 577 70556616332388473718128 578 74296962348065916718655 579 78232212085426082977245 580 82372348945454539636681 581 86727859023018565538487 582 91309755992661142104222 583 96129607201274409460407 584 101199561034172510766408 585 106532375605876479780631 586 112141448849334065107462 587 118040850058951630193879 588 124245352969153002843403 589 130770470428337832101329 590 137632490758404317663845 591 144848515865010068786113 592 152436501197920093021726 593 160415297632024279992059 594 168804695378803085244654 595 177625470004951758383233 596 186899430678588468447845 597 196649470727141218873237 598 206899620638954111231090 599 217675103600168615266504 600 229002393712306849109328 601 240909276990288748642677 602 253424915299984922515761 603 266579913345153471174014 604 280406388877591357502052 605 294938046250435524373918 606 310210253505545374026644 607 326260123126265018656254 608 343126596663581605800641 609 360850533380848886952241 610 379474803143749134407612 611 399044383714512040868125 612 419606462698765424545912 613 441210544319325324940515 614 463908561287090824377976 615 487754991962289908757662 616 512806983099624600832026 617 539124478389453088466669 618 566770353116044594574823 619 595810555166000281876734 620 626314252735318414338061 621 658353988993597711632698 622 692005844083624991940913 623 727349604740473860744423 624 764468941943070462384994 625 803451596910615884543045 626 844389575891544132325832 627 887379354091809855595747 628 932522089227554984620427 629 979923845083509955746288 630 1029695825606197886425029 631 1081954619951398128891045 632 1136822459058946053119631 633 1194427484219895917755381 634 1254904028256797221958722 635 1318392909828643003264747 636 1385041741536588367124276 637 1455005252393101058553946 638 1528445625386507931351240 639 1605532850764341124170964 640 1686445095827832929862599 641 1771369091922728490064683 642 1860500539489365827136464 643 1954044531925041892347430 644 2052215999192852669497208 645 2155240172009843604328856 646 2263353067625734083249846 647 2376801998107448122052983 648 2495846102229734793205905 649 2620756901977077184634509 650 2751818884848391608972018 651 2889330113074285443837280 652 3033602861037121081980915 653 3184964282111782927527452 654 3343757106331143259625362 655 3510340370212762922473767 656 3685090180267263949238248 657 3868400511661503204320182 658 4060684043683574545198941 659 4262373033625105072426547 660 4473920230872725299262398 661 4695799832979131678883221 662 4928508485655983632918485 663 5172566328636271194013343 664 5428518089511202646882878 665 5696934227675069999981609 666 5978412130668214233186260 667 6273577365254371120842573 668 6583084985715646751309456 669 6907620901930545430449548 670 7247903309928738991094642 671 7604684187729471171388262 672 7978750859394695350820991 673 8370927630366614526546208 674 8782077497270701483817658 675 9213103935549526239636332 676 9664952768379614439044958 677 10138614120550020748105048 678 10635124461059322799342247 679 11155568738450524889104767 680 11701082612963470625240027 681 12272854789903715810407936 682 12872129458659202570067984 683 13500208842167860129943185 684 14158455861659322741788215 685 14848296921913438174582292 686 15571224822276398834189811 687 16328801799164808613067367 688 17122662705752830107937723 689 17954518335093562737702004 690 18826158892874678539417753 691 19739457626624738041899256 692 20696374618111485907707196 693 21698960746371832579438155 694 22749361828703767144888047 695 23849822947729429689867432 696 25002692972509196606704511 697 26210429282542720201278739 698 27475602703336777591687963 699 28800902663173221689583045 700 30189142580519131003155836 701 31643265492570234080759670 702 33166349935208151373257516 703 34761616085793242346248380 704 36432432179979858931559997 705 38182321214993332434667789 706 40014967951541495921042279 707 41934226227899230448380851 708 43944126599418306987984554 709 46048884318192872890650447 710 48252907667304581600948375 711 50560806665675028206689117 712 52977402159224918491500988 713 55507735315771844474107568 714 58157077540757998131759607 715 60930940832762939422781533 716 63835088597405342939064840 717 66875546940243735668220915 718 70058616458925741744230295 719 73390884556990147281050934 720 76879238301363501552146169 721 80530877847900086708426815 722 84353330458959358216090206 723 88354465139476545938320575 724 92542507917643917434403782 725 96926057798947939970601895 726 101514103421984818002243304 727 106316040447281981574230230 728 111341689710061637309382489 729 116601316170858796883702338 730 122105648697663947618635267 731 127865900716421043710617470 732 133893791766515722960345641 733 140201570001248369768714209 734 146802035673161076137685929 735 153708565647631325113281236 736 160935138988116628239196525 737 168496363660184074770145526 738 176407504401513772972705452 739 184684511809042583934143109 740 193344052694591821023595672 741 202403541764496860535239615 742 211881174679095939559663302 743 221795962552335229471211290 744 232167767952227401195686820 745 243017342467558694221155430 746 254366365906908413405440239 747 266237487200915595955805562 748 278654367079642739792703164 749 291641722602007764553546359 750 305225373615383551905927690 751 319432291228876832192926852 752 334290648385209076188653670 753 349829872621762225531572323 754 366080701113117671513089077 755 383075238093334425477393612 756 400847014758289123632678089 757 419431051754652355611866510 758 438863924364545635563672284 759 459183830501426969900036031 760 480430661635715756682423645 761 502646076775483102308481121 762 525873579630930899690346138 763 550158599098580264401223345 764 575548573205032137947513401 765 602093036657639780967397519 766 629843712154035407240198913 767 658854605610289771666353979 768 689182105472677079733191864 769 720885086286303872637386777 770 754025016699776379718914801 771 788666072093687872336642651 772 824875252027500472106499279 773 862722502708422521713745923 774 902280844693459529460151567 775 943626506045376487305798391 776 986839061171838562044137961 777 1032001575586939420280598037 778 1079200756843985389614771524 779 1128527111898850285013884447 780 1180075111173906849275540865 781 1233943359603633188117452789 782 1290234774954903338887405479 783 1349056773726540930796989218 784 1410521464946069382723077366 785 1474745852193786344699209000 786 1541852044198968350836324877 787 1611967474366002273435326551 788 1685225129604480766915504434 789 1761763788850895642765420940 790 1841728271687618201516835086 791 1925269697479242484784179479 792 2012545755466114941855712640 793 2103720986270262337589477798 794 2198967075290635613193129208 795 2298463158480771288504973318 796 2402396141025950879526205485 797 2510961029454139905361129721 798 2624361277741093950911076115 799 2742809147988496205484911243 800 2866526086282549691457899810 801 2995743114359988088283030771 802 3130701237739827351131819004 803 3271651871000054794551251248 804 3418857280912480849936722171 805 3572591048171495460418845212 806 3733138548489531394187981892 807 3900797453855982898700256779 808 4075878254796846831482241380 809 4258704804498053559360343367 810 4449614885699281302394710197 811 4648960801292885927406332121 812 4857109989610143692577377582 813 5074445665406785158573106446 814 5301367487611570679452375089 815 5538292254933771880151850483 816 5785654630481298596682822158 817 6043907896576104633003076077 818 6313524741013963802908923728 819 6594998076053218996488742456 820 6888841891482707639614091136 821 7195592143159671634682948191 822 7515807678479096880863859335 823 7850071200280171779898397860 824 8198990270771800004486875504 825 8563198357106879488660083399 826 8943355920317535254105232206 827 9340151549375363000336372858 828 9754303142229429505177679868 829 10186559135731386686628795913 830 10637699786452576352879246434 831 11108538504459350660314286605 832 11599923242215914635732673379 833 12112737940850761292277465567 834 12647904036133442501012794640 835 13206382026581367291295427705 836 13789173106235347322043311513 837 14397320864721841474530524688 838 15031913057348043600838386296 839 15694083448062298742315059746 840 16385013728249851044104974806 841 17105935514428310585832170611 842 17858132428054891903612814192 843 18642942260760192089929062948 844 19461759228482056825354298036 845 20316036318085095546409745382 846 21207287730221614915354374611 847 22137091422312140437284323609 848 23107091755706335361370983731 849 24119002251218428706314264903 850 25174608457427396630257581576 851 26275770936277547279114295177 852 27424428370725305163710815028 853 28622600799336826455617901309 854 29872392982966361015880533492 855 31175997908818341937731774686 856 32535700437437912353785497903 857 33953881098363298843882834110 858 35433020040432397888113583550 859 36975701142941852498859485574 860 38584616294134435083537145119 861 40262569843714888255595211474 862 42012483236391937314706552937 863 43837399833688668138798823432 864 45740489931582244243363208163 865 47725055981800419413321376267 866 49794538024943886489994736400 867 51952519343893673185439287196 868 54202732346328944123662988915 869 56549064685496497279283660776 870 58995565628765547156463101141 871 61546452683845365896839779757 872 64206118492963706607925944418 873 66979138005678264315835842040 874 69870275941443898757776174478 875 72884494553465499689834289131 876 76026961705849241153063536370 877 79303059276507640702626214966 878 82718391898791376397211651143 879 86278796055302077679822183805 880 89990349537894982915458033473 881 93859381288403283075267887119 882 97892481635210724710906458300 883 102096512941366918141952579897 884 106478620680577433495302716704 885 111046244958017565956217942076 886 115807132493602200655820618795 887 120769349086013578678500686864 888 125941292576522195932014428570 889 131331706332361974116061054461 890 136949693270207505664879835312 891 142804730441088838602087535009 892 148906684198922818470621806056 893 155265825975693902133448612457 894 161892848687222923361927505926 895 168798883794387200054805495994 896 175995519045627202586235687490 897 183494816927577468428571769783 898 191309333851702069788268090666 899 199452140105900441604312019666 900 207936840601169360697311433868 901 216777596444581293697671946025 902 225989147371041851586693018864 903 235586835067560757529860828461 904 245586627425061410621094296397 905 256005143754129697479215128771 906 266859681002489995082471472110 907 278168241013482876864396691110 908 289949558866309481086519648122 909 302223132340415460060105939069 910 315009252547987966112660070106 911 328329035780276774305289038489 912 342204456615171857912664036710 913 356658382335345833381613641881 914 371714608708119776727976384504 915 387397897180238312900064663837 916 403734013542727659767339176960 917 420749768123199054215143451524 918 438473057565098876142360859211 919 456932908255767667540396265603 920 476159521467470437628001176527 921 496184320278109684378864288925 922 517039998340804981125766311627 923 538760570574272703943393276833 924 561381425848600846175206150916 925 584939381743977474562132074296 926 609472741462794744936156998915 927 635021352978747459998690364781 928 661626670509624299032393493499 929 689331818403935811335097372019 930 718181657534839021713832316180 931 748222854298529822528663727275 932 779503952317842870209540017479 933 812075446955799506859037752790 934 845989862747682990029309398762 935 881301833864529644565983916871 936 918068187725059417916197694861 937 956348031877707384977254933560 938 996202844278869314541154099900 939 1037696567098470716368268715799 940 1080895704188758783966689413688 941 1125869422357595009853711803642 942 1172689656592686598162529883634 943 1221431219388980372030316837961 944 1272171914336999398854022791760 945 1324992654136131246556691295551 946 1379977583202857180177259036534 947 1437214205050612802474769030004 948 1496793514624414177891033885154 949 1558810135780588450471192378750 950 1623362464108887168624777115222 951 1690552815302013255073806582975 952 1760487579285061892753521040149 953 1833277380325712705572495930185 954 1909037243354058542641064244860 955 1987886766729916434191376635595 956 2069950301704133693929623531032 957 2155357138830038876467837341323 958 2244241701590517881223828603201 959 2336743747516554247776720796017 960 2433008577083125509491274211146 961 2533187250679476735717592531029 962 2637436813961618770697734169816 963 2745920531906863522384246429960 964 2858808131901863089705014476904 965 2976276056208476506120846774832 966 3098507724164343267921336151952 967 3225693804488852024801833051227 968 3358032498078713290578727120977 969 3495729831692185647023630434285 970 3638999962935559011952104984454 971 3788065496981441157338870227515 972 3943157815464069927472944292284 973 4104517418013993218433444132344 974 4272394276911337793719318861980 975 4447048205355280843486795995364 976 4628749239865505529839756713178 977 4817778037351175410718411740145 978 5014426287402527067138845333351 979 5218997140381388127765323339880 980 5431805651907989363553558836492 981 5653179244364219079205777041681 982 5883458186056133676891207692113 983 6122996088702998537415891462467 984 6372160423944535546976238233849 985 6631333059584310731033462211899 986 6900910816313459553650764719887 987 7181306045687144240214977245785 988 7472947230154396622251786185422 989 7776279605972272080573505606782 990 8091765809865656394499700706289 991 8419886550326559351749086820424 992 8761141304479457463584267995636 993 9116049041474134363747980171565 994 9485148973402674603307975977803 995 9869001334774715388147363476585 996 10268188191622943760755961596786 997 10683314281351017975022553249019 998 11115007884476844242188300737296 999 11563921729467286088230604083828 1000 12030733931904211419441721112821