0 0 1 1 2 1 3 2 4 4 5 6 6 9 7 13 8 19 9 27 10 39 11 52 12 71 13 95 14 127 15 170 16 220 17 286 18 371 19 474 20 614 21 770 22 979 23 1229 24 1541 25 1934 26 2392 27 2968 28 3668 29 4504 30 5556 31 6764 32 8271 33 10055 34 12199 35 14798 36 17836 37 21504 38 25860 39 30996 40 37185 41 44348 42 52943 43 63003 44 74856 45 88874 46 105165 47 124376 48 146842 49 173009 50 203787 51 239312 52 280969 53 329241 54 385324 55 450562 56 525817 57 613171 58 714119 59 830523 60 965313 61 1119946 62 1298606 63 1503787 64 1739618 65 2010746 66 2321116 67 2677304 68 3085092 69 3551288 70 4085146 71 4693577 72 5389132 73 6181689 74 7084890 75 8113955 76 9283649 77 10614381 78 12126147 79 13841807 80 15789957 81 17996286 82 20498076 83 23329560 84 26533567 85 30157646 86 34251161 87 38875640 88 44095004 89 49981229 90 56619822 91 64095245 92 72516225 93 81991131 94 92648455 95 104630478 96 118089633 97 133205532 98 150170637 99 169199412 100 190538962 101 214445914 102 241228916 103 271209641 104 304757989 105 342282224 106 384226365 107 431097540 108 483446985 109 541884997 110 607101831 111 679832859 112 760928861 113 851297924 114 951964666 115 1064057046 116 1188809764 117 1327607284 118 1481963868 119 1653548779 120 1844226930 121 2056011126 122 2291177551 123 2552184832 124 2841774225 125 3162956568 126 3519033265 127 3913665718 128 4350866300 129 4835042691 130 5371078886 131 5964279041 132 6620557218 133 7346337544 134 8148726320 135 9035510610 136 10015225198 137 11097270119 138 12291942215 139 13610521024 140 15065432562 141 16670203914 142 18439782159 143 20390438822 144 22540071941 145 24908251416 146 27516394806 147 30387978699 148 33548682402 149 37026567929 150 40852413355 151 45059737239 152 49685352227 153 54769342362 154 60355613600 155 66492073867 156 73231051545 157 80629706518 158 88750443974 159 97661308517 160 107436671641 161 118157473543 162 129912220306 163 142797211248 164 156917579598 165 172387811735 166 189332696980 167 207888175044 168 228202355675 169 250436404623 170 274765969868 171 301381980286 172 330492518272 173 362323706496 174 397121735392 175 435154187862 176 476712124428 177 522111887447 178 571697437180 179 625842345201 180 684952753962 181 749469491490 182 819871709528 183 896679327385 184 980457081258 185 1071817671116 186 1171426228030 187 1280004213358 188 1398334538545 189 1527265995998 190 1667719397914 191 1820692636073 192 1987267915031 193 2168617676502 194 2366012803179 195 2580829746038 196 2814559937647 197 3068818209654 198 3345353685656 199 3646059482211 200 3972985388006 201 4328349278287 202 4714551703337 203 5134189297797 204 5590071492939 205 6085236136177 206 6622969047090 207 7206822011518 208 7840635495152 209 8528559507882 210 9275079616061 211 10085041739775 212 10963681728873 213 11916654436570 214 12950067770364 215 14070516042858 216 15285120089296 217 16601565245735 218 18028147965177 219 19573819887379 220 21248240806156 221 23061831072796 222 25025831482650 223 27152364500158 224 29454503329042 225 31946341615550 226 34643074844387 227 37561079335190 228 40718006650981 229 44132875139072 230 47826176851170 231 51819985922520 232 56138079237147 233 60806062549471 234 65851509578224 235 71304105120698 236 77195808461903 237 83561015272868 238 90436746646066 239 97862836261335 240 105882144205536 241 114540777248940 242 123888330149648 243 133978140907660 244 144867568488071 245 156618282108352 246 169296585955761 247 182973746337531 248 197726366226513 249 213636762360926 250 230793388821800 251 249291278080625 252 269232519263828 253 290726767213268 254 313891791805521 255 338854054589509 256 365749347755146 257 394723446383842 258 425932843207593 259 459545498222164 260 495741669792997 261 534714786112422 262 576672384191314 263 621837112078329 264 670447804829032 265 722760619523704 266 779050280612563 267 839611363994753 268 904759724856522 269 974833969249908 270 1050197069341266 271 1131238064908709 272 1218373889104359 273 1312051318773627 274 1412749061631036 275 1520979964534053 276 1637293418040192 277 1762277854771347 278 1896563498783971 279 2040825221002857 280 2195785649311210 281 2362218454381863 282 2540951865589034 283 2732872426141410 284 2938929003245714 285 3160137038265047 286 3397583147584683 287 3652429930174369 288 3925921214712237 289 4219387540514709 290 4534252091524521 291 4872036977039953 292 5234369939000641 293 5622991510576683 294 6039762649541597 295 6486672836070303 296 6965848798604065 297 7479563669568901 298 8030246913402813 299 8620494740610222 300 9253081329743433 301 9930970717912570 302 10657329479969269 303 11435540247973631 304 12269216111154722 305 13162215898160119 306 14118660584981414 307 15142950562475906 308 16239784264196826 309 17414177765031602 310 18671485822255789 311 20017424182369562 312 21458093339081552 313 23000003839997942 314 24650103216493167 315 26415804565141433 316 28305017145860144 317 30326178649875690 318 32488289867435680 319 34800951239252783 320 37274401982181206 321 39919561576590321 322 42748073908107943 323 45772354238959146 324 49005639151105770 325 52462039543510296 326 56156597236120592 327 60105344745867549 328 64325369298684317 329 68834880415505596 330 73653282085366734 331 78801249291382458 332 84300809359777583 333 90175428439027802 334 96450103381063508 335 103151459210460459 336 110307853026384379 337 117949483823728307 338 126108509787463079 339 134819172247240179 340 144117927785957342 341 154043588285818917 342 164637469677862639 343 175943549927198267 344 188008636766326270 345 200882545556379486 346 214618288582130316 347 229272275230477046 348 244904525332793198 349 261578894737327640 350 279363315328444610 351 298330049383076055 352 318555959525773889 353 340122795199517814 354 363117496600621539 355 387632516814127585 356 413766164189412052 357 441622964477936037 358 471314046103926074 359 502957547613489817 360 536679050620865646 361 572612038430586198 362 610898382426638347 363 651688857806191601 364 695143690383260230 365 741433135842614130 366 790738094662785742 367 843250762537150578 368 899175321320715114 369 958728669763356248 370 1022141199049802099 371 1089657613959566870 372 1161537803128602898 373 1238057761125929143 374 1319510565432880407 375 1406207410854645533 376 1498478706492714800 377 1596675235874705500 378 1701169387820926304 379 1812356458009030741 380 1930656028915079048 381 2056513430216809834 382 2190401285471525078 383 2332821149731983705 384 2484305243548178895 385 2645418287915532285 386 2816759448407294202 387 2998964390716579262 388 3192707459168691318 389 3398703979791936747 390 3617712699824582240 391 3850538368163010856 392 4098034466461348875 393 4361106098890035601 394 4640713050050645109 395 4937873019158683549 396 5253665043817154522 397 5589233118794252715 398 5945790027646010961 399 6324621392096009227 400 6727089957749571189 401 7154640125082178824 402 7608802741920252718 403 8091200171141466430 404 8603551649976929064 405 9147678955184119530 406 9725512395756131614 407 10339097144517819949 408 10990599936453887514 409 11682316145025476077 410 12416677265821190628 411 13196258824410658424 412 14023788735461681156 413 14902156136590213307 414 15834420724948249474 415 16823822621410537901 416 17873792797731885997 417 18987964088731619393 418 20170182833413328434 419 21424521167878470724 420 22755290016791600539 421 24167052814176767773 422 25664639998620534588 423 27253164322873470061 424 28938037025354344906 425 30724984906497771192 426 32620068367849426134 427 34629700454830103178 428 36760666973013191010 429 39020147721390539733 430 41415738917656837050 431 43955476870336971663 432 46647862972679489929 433 49501890086200329367 434 52527070393904701881 435 55733464796775247374 436 59131713948463169071 437 62733071001762353399 438 66549436178758840116 439 70593393244012659242 440 74878248001818424077 441 79418068913436517693 442 84227729958528843862 443 89322955855527521449 444 94720369774940457674 445 100437543670794804348 446 106493051385945086837 447 112906524660600398005 448 119698712224295192741 449 126891542112123353974 450 134508187401268223131 451 142573135533167346464 452 151112261426750630445 453 160152904575758077300 454 169723950353307136437 455 179855915735283104372 456 190581039697902984165 457 201933378513014108224 458 213948906232500409288 459 226665620606595002317 460 240123654754336560232 461 254365394867936583966 462 269435604289798577070 463 285381554285341753767 464 302253161881447576049 465 320103135125800566499 466 338987126185392347623 467 358963892665399772419 468 380095467620585223351 469 402447338678153692091 470 426088636789279026016 471 451092335084812750273 472 477535458392027747446 473 505499303950838703116 474 535069673939517632599 475 566337120402925168889 476 599397203267272261947 477 634350762084374745676 478 671304202271280679422 479 710369796553356072340 480 751666002451516191602 481 795317796609400943452 482 841457026873017526430 483 890222783015685791850 484 941761787110195431121 485 996228804532463280539 486 1053787076712979676210 487 1114608776710632434347 488 1178875488851242265419 489 1246778713615553631317 490 1318520399142156215522 491 1394313500667424741100 492 1474382569393035540569 493 1558964372254497806817 494 1648308544229538624965 495 1742678274811319641430 496 1842351030463849942166 497 1947619314841573802795 498 2058791468786628919128 499 2176192512069297839128 500 2300165029086386325070 501 2431070100699690145553 502 2569288284641347822233 503 2715220646906294717272 504 2869289846802027823508 505 3031941278324757627407 506 3203644270812777716424 507 3384893351811986531008 508 3576209575412038389074 509 3778141919290305298050 510 3991268754048939944637 511 4216199388425654093721 512 4453575694316241749783 513 4704073815566047636816 514 4968405964864660218437 515 5247322313106604808421 516 5541612975995539918008 517 5852110102696576754087 518 6179690071799430919067 519 6525275799890092601027 520 6889839168521608057124 521 7274403575427648408092 522 7680046616347968185274 523 8107902903907282687819 524 8559167030557228232575 525 9035096682679600899716 526 9537015913562625033525 527 10066318583072586327628 528 10624471972500374422010 529 11213020583203508563997 530 11833590128371674962357 531 12487891727405379627459 532 13177726313174391044267 533 13904989262596240754275 534 14671675261830845240784 535 15479883417588718655348 536 16331822626962376787675 537 17229817218452530280676 538 18176312877815615191424 539 19173882872688216263877 540 20225234590972644214821 541 21333216408322292040342 542 22500824901221106697889 543 23731212422507731220711 544 25027695057484476719669 545 26393760979155078804131 546 27833079222497513556237 547 29349508898203559409079 548 30947108867720656357193 549 32630147902081511868012 550 34403115348520698879907 551 36270732329562394238845 552 38237963500991215261853 553 40310029395792710818253 554 42492419383094908134314 555 44790905271897438791900 556 47211555591418190608089 557 49760750580858207800015 558 52445197923470835665896 559 55271949261004979229625 560 58248417526843342265011 561 61382395137394409290171 562 64682073083892039175383 563 68156060967972210509295 564 71813408027332686412207 565 75663625199131874639528 566 79716708271859825697244 567 83983162178122928331530 568 88474026483908571581268 569 93200902131952310461932 570 98175979500206855906597 571 103412067838558709121252 572 108922626150851551357308 573 114721795591393193126051 574 120824433449561308923682 575 127246148798464037298115 576 134003339888259147215789 577 141113233367647752180120 578 148593925421774196671975 579 156464424918226118046238 580 164744698657930301363477 581 173455718831358755034103 582 182619512786380215341074 583 192259215217690931833829 584 202399122894475928939768 585 213064752046916041990629 586 224282898539195968274392 587 236081700961520691632061 588 248490706780803703492161 589 261540941695395418355243 590 275264982346969551405074 591 289697032548664008647057 592 304873003197554926208817 593 320830596045542394911018 594 337609391512904445315273 595 355250940735368603009960 596 373798862046237075140082 597 393298942103049760447630 598 413799241879173019228074 599 435350207749953717893304 600 458004787914895898390196 601 481818554407045588023416 602 506849830954423028278745 603 533159826968195035170570 604 560812777947716953974218 605 589876092603380093620062 606 620420507014449556061352 607 652520246151927010286322 608 686253193113133257805506 609 721701066429527471273840 610 758949605827349983181111 611 798088766836316333437767 612 839212924662375129350833 613 882421087756525864669341 614 927817121535122874171774 615 975509982724594794671406 616 1025613964828242561442961 617 1078248955233335330508487 618 1133540704502222861264695 619 1191621108414703535252585 620 1252628503356559636145930 621 1316707975674077968455752 622 1384011685646041889917321 623 1454699206750342575714884 624 1528937880937937430886606 625 1606903190654950951280543 626 1688779148391385141791176 627 1774758704567509125820459 628 1865044174608055758190568 629 1959847686091389140650282 630 2059391646903212181405285 631 2163909235363730332014052 632 2273644913345455306541561 633 2388854963439673633389193 634 2509808051283648013359813 635 2636785814205243305666270 636 2770083477399057475555565 637 2910010498899471730298422 638 3056891244675864501677769 639 3211065695233177732420174 640 3372890185166001104184802 641 3542738177176083281701164 642 3721001072136743522697624 643 3908089056852166764183617 644 4104431991241647946274933 645 4310480336749273570712975 646 4526706127866935407612535 647 4753603988738896528681767 648 4991692196907731986623066 649 5241513796351626190007169 650 5503637762062509088373256 651 5778660218510841511415583 652 6067205714454929847082579 653 6369928556653873310199920 654 6687514205167877814396041 655 7020680733040084182828005 656 7370180353287113330786072 657 7736801016250539629154922 658 8121368080501612436669175 659 8524746060631167326113344 660 8947840455408869502093940 661 9391599659945454736214852 662 9857016965662233908348377 663 10345132652030029438617969 664 10857036174228838557381673 665 11393868451051634604429257 666 11956824257578091636008742 667 12547154727337630127381944 668 13166169968895198754419571 669 13815241802008516735551780 670 14495806618737987580836096 671 15209368375121536920774886 672 15957501719286061127517571 673 16741855262112202298363082 674 17564154996855934583559406 675 18426207874397356928298822 676 19329905541094562919643380 677 20277228246519025416288752 678 21270248928675327169880702 679 22311137484638837966847049 680 23402165234899469422439734 681 24545709590055181312297230 682 25744258928892943065125749 683 27000417697273282561601669 684 28316911737668940658383381 685 29696593859620118941861348 686 31142449661835368542201053 687 32657603617125766415459029 688 34245325431856913451245919 689 35909036692109669886956013 690 37652317809280186408860749 691 39478915278394870426257586 692 41392749263013521200946038 693 43397921521175795058342028 694 45498723687503370628255336 695 47699645927203319314182120 696 50005385978425109793036535 697 52420858600125519939928367 698 54951205443350711669211885 699 57601805364617457860429221 700 60378285200895291847421882 701 63286531026524108369102368 702 66332699913306632171662772 703 69523232215906468153185705 704 72864864405675438590640874 705 76364642477003101983458500 706 80029935951350757836393852 707 83868452505202715822470315 708 87888253249312414620308561 709 92097768687796601021202203 710 96505815386873541648650677 711 101121613384309371952765434 712 105954804372004546520296294 713 111015470685512457034120865 714 116314155135780398425466511 715 121861881719881235307733181 716 127670177249119125898153792 717 133751093934520191921538311 718 140117232971451290518584821 719 146781769166893507656272580 720 153758476654776956964793175 721 161061755746708682715233513 722 168706660967489449433887588 723 176708930326883543251502695 724 185085015881362299474172769 725 193852115641788800282279743 726 203028206885445763511942655 727 212632080933275683103028986 728 222683379455817845546070214 729 233202632374025038369017516 730 244211297423980469424405223 731 255731801457449691866804980 732 267787583553310879413054405 733 280403140018042006119233548 734 293604071356836831506396396 735 307417131300325488808741725 736 321870277975538696825100698 737 336992727313483510528083861 738 352815008789639216049443782 739 369369023597753357179876995 740 386688105361591845709858584 741 404807083493696337981833172 742 423762349314874810694285481 743 443591925052889124626022894 744 464335535843897140570121830 745 486034684865348322744489180 746 508732731734533135050643637 747 532474974312607305013447796 748 557308734059836250841058525 749 583283445093932854726567006 750 610450747109784786720235743 751 638864582325490757494467090 752 668581296626635331172560791 753 699659745087870900114858579 754 732161402058507837090726309 755 766150476006557120256777450 756 801694029323915475533838401 757 838862103303833337233738823 758 877727848510692656207219760 759 918367660771322136839593082 760 960861323026708981379513335 761 1005292153292912060357112174 762 1051747158990477569805253083 763 1100317197912385434241226493 764 1151097146111969689329774381 765 1204186073003885883754815875 766 1259687423983533283767265154 767 1317709210883011603101641707 768 1378364210594993707726013466 769 1441770172209676743573728655 770 1508050033024385307701284462 771 1577332143800298686748302063 772 1649750503656458073811161908 773 1725445005007285928259454718 774 1804561688966889455687930038 775 1887253011660841142443260202 776 1973678121904543960007089970 777 2064003150726245052572346115 778 2158401513232628881700152360 779 2257054223335514643946559201 780 2360150221879698870039739712 781 2467886718734247624509482448 782 2580469549432931227580378787 783 2698113546973525652463818028 784 2821042929411092348317141070 785 2949491703906377873923292539 786 3083704087917911258531639967 787 3223934948254666563146484220 788 3370450258735767774119129964 789 3523527577234418050689593761 790 3683456542915290312774842116 791 3850539394507808076765758552 792 4025091510492553169938785929 793 4207441972113871294450128827 794 4397934150169498342255042489 795 4596926316566827528883261610 796 4804792281676234104357375106 797 5021922058553995167478545077 798 5248722555151378373694636791 799 5485618295672151912670608543 800 5733052172288422796598999493 801 5991486228474082687402572830 802 6261402475266838694002900926 803 6543303741823114300325027121 804 6837714561686134804151067947 805 7145182096245201951631888069 806 7466277096924703994140929836 807 7801594907703980465231601186 808 8151756509634515796174498584 809 8517409609088742565715073038 810 8899229771545432848230153658 811 9297921602789933099818200743 812 9714219979484129294084666793 813 10148891331140147852525751115 814 10602734975614792064349665436 815 11076584510327300706429888882 816 11571309261492679737091126426 817 12087815793755609931833826406 818 12627049482706726826702956544 819 13189996152863509040411229910 820 13777683783802677182427273703 821 14391184287239525580607065374 822 15031615357962972519845562504 823 15700142401652279408518728233 824 16397980542724087916432519098 825 17126396715485114452414565976 826 17886711841998375185541702003 827 18680303100208005705243388527 828 19508606286010802611689029882 829 20373118273111080967297492794 830 21275399574650081215766523073 831 22217077010761531640592038094 832 23199846486372344711544166956 833 24225475883740553520847464649 834 25295808074403642982879482330 835 26412764055397556915992635283 836 27578346214802178827594595311 837 28794641731871578897109562166 838 30063826117218345131866429247 839 31388166898740324276631424622 840 32770027459206112169687952023 841 34211871031652141461307917850 842 35716264858990844233790377147 843 37285884524484645178865260392 844 38923518460007176525403348175 845 40632072639288913640474943399 846 42414575463632301248671065694 847 44274182847879708405564241243 848 46214183514728206031776012360 849 48238004505807573422219570879 850 50349216918273477640816968898 851 52551541876015848030934795386 852 54848856744945184218517176037 853 57245201602195164361896439468 854 59744785969471856656192201729 855 62351995821185512573066034467 856 65071400878423956505324906570 857 67907762200265039260586908372 858 70866040084382051940507574456 859 73951402289369695544145673442 860 77169232591711002395105431982 861 80525139690816861887085311643 862 84024966476102227118242498629 863 87674799670614675224647485631 864 91480979866306029199394920525 865 95450111966633235552598924536 866 99589076052795177667070373819 867 103905038690555351747010236477 868 108405464695269645132610751996 869 113098129373433072083566821501 870 117991131259781700991471284913 871 123092905369735465239309744931 872 128412236987747608576034471649 873 133958276012934905670351431946 874 139740551884204896075067653876 875 145768989107968747478601178080 876 152053923412436748770470903391 877 158606118553435296008363461068 878 165436783797663857329745153533 879 172557592110327007509045749806 880 179980699075133523722155384816 881 187718762575751058099131784395 882 195784963268945639667135097455 883 204193025880817685095199212537 884 212957241358777113507525586990 885 222092489913175699357669459979 886 231614264983842197186659908082 887 241538698168142242653740772262 888 251882585148616149420669642785 889 262663412659732763870953474249 890 273899386534840984418748051283 891 285609460876001824723657202810 892 297813368391049009062679755299 893 310531651943952314937441802838 894 323785697366353856069105616480 895 337597767580008966573599364632 896 351991038081799490582986470872 897 366989633844995126701927511737 898 382618667692525310561035520718 899 398904280200189416267435456451 900 415873681189982875690871059206 901 433555192876050823831293235276 902 451978294728206979337755361063 903 471173670120470868398159578788 904 491173254834692210430121123126 905 512010287492042757026549946107 906 533719361987974824732771271495 907 556336482009169180779611506360 908 579899117714032399726997998093 909 604446264661455189408485014308 910 630018505075816703481762719307 911 656658071539615667723907436535 912 684408913208637682123469369990 913 713316764648226669011190643679 914 743429217393031238438737246961 915 774795794336539112770805047433 916 807468027060809705939991312525 917 841499536221063714471813046405 918 876946115104201776795974078354 919 913865816484902520977865724826 920 952319042907704820867628962463 921 992368640528410822698370740506 922 1034079996653269130951682154090 923 1077521141119709304323370943346 924 1122762851667917712507881533104 925 1169878763458266513019694042970 926 1218945482895551374487858838030 927 1270042705927157491711032480361 928 1323253340988674153016659975744 929 1378663636777117527691422670399 930 1436363315038814663236231613710 931 1496445708566151349904081733317 932 1559007904604810969797886521457 933 1624150893880829629646732791994 934 1691979725464788384051321680424 935 1762603667698752757023273816133 936 1836136375420178152590183297424 937 1912696063725926359505011357723 938 1992405688528805505812873828098 939 2075393134168657467639367326827 940 2161791408349993668220078282014 941 2251738844688527139323523275228 942 2345379313159690346821968337955 943 2442862438753365510875663510919 944 2544343828650617772490423459481 945 2649985308250209986233250382790 946 2759955166385123883004197006863 947 2874428410082217514918153579112 948 2993587029231543114886303589803 949 3117620271545739999104431336377 950 3246724928204332347252300247223 951 3381105630592709919091666534390 952 3520975158561084191378137581120 953 3666554760644797270038730315177 954 3818074486704056670745724129295 955 3975773533458477384187414348215 956 4139900603409776515219120438162 957 4310714277664590900130755381823 958 4488483403188714582666685235074 959 4673487495044093125234857901375 960 4866017154180704422424463541533 961 5066374501377014777090995950735 962 5274873627945069277092672526921 963 5491841063839466597337386776324 964 5717616263833533633470625848148 965 5952552112450962065080649058167 966 6197015448367053800677137479560 967 6451387609020557384077651362716 968 6716064996204916992856663545418 969 6991459663436619537390149384188 970 7277999925928267088866009879820 971 7576130994025043548942445369737 972 7886315630995446786346404828908 973 8209034836100538428507956703240 974 8544788553900594044008568436211 975 8894096410793932550361486358166 976 9257498479819940754235008926497 977 9635556074796909031706586184315 978 10028852574905330661356117484066 979 10437994280868821591831076912863 980 10863611303927863056207223678761 981 11306358488846190977505701051652 982 11766916372235936010705096586605 983 12245992177535587177057365612093 984 12744320848024605162576688662079 985 13262666119310077967455242875427 986 13801821632774292525840978036308 987 14362612091527528312359080754273 988 14945894460467862602762551077764 989 15552559212109360304063388161180 990 16183531619901805483973113786987 991 16839773100829169810859334869833 992 17522282609140417533832460204395 993 18232098083135067471614055278912 994 18970297946997297111922535315086 995 19738002669746332316664066423863 996 20536376383447553787115658498123 997 21366628562908228068025454739618 998 22230015769164172617715951198228 999 23127843459149064646905001821970 1000 24061467864026641840794491901714