0 0 1 0 2 1 3 2 4 3 5 5 6 8 7 12 8 18 9 25 10 36 11 49 12 68 13 91 14 123 15 162 16 214 17 278 18 362 19 464 20 596 21 757 22 961 23 1209 24 1521 25 1897 26 2366 27 2931 28 3627 29 4463 30 5487 31 6711 32 8200 33 9976 34 12121 35 14672 36 17738 37 21371 38 25716 39 30852 40 36964 41 44168 42 52709 43 62746 44 74600 45 88497 46 104849 47 123971 48 146402 49 172564 50 203161 51 238769 52 280290 53 328502 54 384576 55 449541 56 524910 57 612054 58 712909 59 829287 60 963682 61 1118456 62 1296811 63 1501840 64 1737620 65 2008178 66 2318726 67 2674458 68 3082018 69 3548112 70 4081164 71 4689796 72 5384703 73 6176899 74 7079927 75 8107858 76 9277769 77 10607569 78 12118801 79 13834152 80 15780734 81 17987261 82 20487743 83 23318419 84 26521928 85 30143838 86 34237496 87 38860133 88 44078313 89 49963729 90 56599367 91 64074777 92 72493213 93 81966375 94 92622444 95 104600445 96 118059325 97 133171691 98 150134293 99 169161128 100 190495252 101 214401454 102 241179630 103 271156736 104 304702185 105 342219114 106 384161763 107 431026328 108 483370651 109 541804336 110 607011409 111 679739766 112 760826805 113 851188609 114 951849054 115 1063928392 116 1188676703 117 1327462067 118 1481808504 119 1653384290 120 1844045127 121 2055822311 122 2290972385 123 2551965503 124 2841541887 125 3162701261 126 3518767246 127 3913377685 128 4350558722 129 4834716674 130 5370722528 131 5963906650 132 6620155397 133 7345908788 134 8148271769 135 9035016016 136 10014707160 137 11096712747 138 12291348079 139 13609890965 140 15064749853 141 16669487416 142 18439013354 143 20389619957 144 22539203582 145 24907313864 146 27515409340 147 30386923743 148 33547559774 149 37025377436 150 40851132228 151 45058388847 152 49683911922 153 54767810854 154 60353989797 155 66490331439 156 73229215833 157 80627749352 158 88748364663 159 97659104268 160 107434312530 161 118154986113 162 129909573021 163 142794400828 164 156914601229 165 172384631411 166 189329341759 167 207884609712 168 228198573661 169 250432397758 170 274761700276 171 301377473919 172 330487736646 173 362318637903 174 397116367571 175 435148478603 176 476706097013 177 522105500031 178 571690671464 179 625835182807 180 684945148865 181 749461461262 182 819863209907 183 896670330520 184 980447561165 185 1071807577749 186 1171415570123 187 1279992944460 188 1398322618753 189 1527253388549 190 1667706049675 191 1820678541788 192 1987253027730 193 2168601939512 194 2365996166426 195 2580812153396 196 2814541364208 197 3068798608844 198 3345332979772 199 3646037602866 200 3972962277793 201 4328324884143 202 4714525981704 203 5134162142773 204 5590042813517 205 6085205874163 206 6622937111864 207 7206788364332 208 7840599994845 209 8528522033322 210 9275040110880 211 10085000062170 212 10963637849020 213 11916608167124 214 12950018952914 215 14070464624092 216 15285065861046 217 16601508189996 218 18028087837376 219 19573756480415 220 21248174073433 221 23061760718840 222 25025757507171 223 27152286584779 224 29454421206766 225 31946255248454 226 34642983825870 227 37560983687173 228 40717905964135 229 44132769069231 230 47826065374183 231 51819868488871 232 56137955898894 233 60805932781857 234 65851372942395 235 71303961608801 236 77195657345404 237 83560856640143 238 90436579830641 239 97862660704119 240 105881959921312 241 114540583282726 242 123888126636556 243 133977927003372 244 144867343486212 245 156618046049419 246 169296337604338 247 182973485883090 248 197726092607664 249 213636474686170 250 230793087164349 251 249290960855314 252 269232186727090 253 290726418033626 254 313891424865668 255 338853669997865 256 365748943497308 257 394723022791995 258 425932398621964 259 459545031243769 260 495741180572346 261 534714272105521 262 576671845819815 263 621836547277471 264 670447211857211 265 722759998573382 266 779049628495208 267 839610681229606 268 904759008888154 269 974833217912756 270 1050196282873827 271 1131237239334058 272 1218373025052428 273 1312050413087687 274 1412748111630937 275 1520978970498441 276 1637292375038983 277 1762276763549110 278 1896562355458326 279 2040824022260717 280 2195784395467982 281 2362217139350715 282 2540950490237115 283 2732870985701724 284 2938927493639352 285 3160135459826048 286 3397581492835433 287 3652428200098767 288 3925919403478991 289 4219385643107529 290 4534250108278019 291 4872034898799334 292 5234367766861367 293 5622989237416758 294 6039760269213205 295 6486670348867636 296 6965846193366269 297 7479560947476676 298 8030244065785159 299 8620491759941064 300 9253078216230606 301 9930967457988942 302 10657326074869955 303 11435536687156860 304 12269212385434008 305 13162212007577122 306 14118656513103103 307 15142946310527474 308 16239779819397429 309 17414173116180196 310 18671480969133182 311 20017419105121721 312 21458088038845594 313 22999998301298103 314 24650097425707095 315 26415798521643725 316 28305010825737047 317 30326172054047328 318 32488282977207831 319 34800944038074927 320 37274394468847067 321 39919553722359562 322 42748065713524121 323 45772345681467063 324 49005630210642276 325 52462030218036695 326 56156587491187835 327 60105334581406142 328 64325358687536466 329 68834869333373931 330 73653270529075796 331 78801237219719107 332 84300796771767239 333 90175415302006190 334 96450089665662386 335 103151444911949865 336 110307838095572762 337 117949468258326847 338 126108493548255529 339 134819155298762163 340 144117910121416059 341 154043569846598244 342 164637450459855784 343 175943529883368121 344 188008615853920968 345 200882523765867923 346 214618265843805310 347 229272251537736162 348 244904500629307932 349 261578868971605732 350 279363288487395901 351 298330021383924645 352 318555930358588590 353 340122764796903279 354 363117464900653326 355 387632483799088944 356 413766129761178903 357 441622928622158466 358 471314008740078429 359 502957508667164032 360 536679010068423724 361 572611996155856592 362 610898338409518973 363 651688811950545873 364 695143642599801375 365 741433086100130068 366 790738042823944193 367 843250708574385379 368 899175265119392282 369 958728611216419802 370 1022141138116463634 371 1089657550477656505 372 1161537737061005465 373 1238057692336053195 374 1319510493792522616 375 1406207336310921144 376 1498478628854369952 377 1596675155092441992 378 1701169303732164533 379 1812356370460356693 380 1930655937838468731 381 2056513335386920450 382 2190401186823677963 383 2332821047072795536 384 2484305136694272148 385 2645418176779954354 386 2816759332724829441 387 2998964270403179274 388 3192707333994550981 389 3398703849538019588 390 3617712564380445098 391 3850538227216756223 392 4098034319904736789 393 4361105946450146082 394 4640712891466113254 395 4937872854289949325 396 5253664872297763286 397 5589232940485814151 398 5945789842224677094 399 6324621199250120039 400 6727089757303692939 401 7154639916606042402 402 7608802525238142750 403 8091199945869317878 404 8603551415743455583 405 9147678711769746457 406 9725512142656055434 407 10339096881510209426 408 10990599663083611736 409 11682315860850503554 410 12416676970567908085 411 13196258517487140637 412 14023788416589430419 413 14902155805230164196 414 15834420380574600510 415 16823822263683604126 416 17873792425958033620 417 18987963702562849183 418 20170182432211601342 419 21424520751018736062 420 22755289583853736838 421 24167052364348316001 422 25664639531468642820 423 27253163837643322273 424 28938036521303504465 425 30724984383108319645 426 32620067824170227382 427 34629699890324886412 428 36760666386789554913 429 39020147112567157493 430 41415738285597320202 431 43955476213928231584 432 46647862291259701605 433 49501889378714912499 434 52527069659308249962 435 55733464034288044979 436 59131713156783155080 437 62733070180075520901 438 66549435325819684534 439 70593392358581885123 440 74878247082943468977 441 79418067959594688903 442 84227728968722293983 443 89322954828285905399 444 94720368708795685514 445 100437542564586125111 446 106493050237892401300 447 112906523469484111922 448 119698710988380476990 449 126891540829672099546 450 134508186070869624020 451 142573134152740826842 452 151112259994809907831 453 160152903090257136834 454 169723948812189592382 455 179855914136838175253 456 190581038039699559607 457 201933376793245621937 458 213948904448755086826 459 226665618756441291304 460 240123652835704699790 461 254365392877986336337 462 269435602226339714702 463 285381552145532539028 464 302253159662414733328 465 320103132825045252714 466 338987123799597060136 467 358963890191915321042 468 380095465056064907112 469 402447336019204175568 470 426088634032889714410 471 451092332227109163078 472 477535455429812895578 473 505499300880172813076 474 535069670756395719886 475 566337117103726975128 476 599397199847473602628 477 634350758540125632572 478 671304198597945376316 479 710369792746210321727 480 751665998506214854616 481 795317792520661701783 482 841457022636213569058 483 890222778625364707249 484 941761782560787936268 485 996228799818763298472 486 1053787071828820597253 487 1114608771650464422220 488 1178875483608655345915 489 1246778708183985953850 490 1318520393515380973911 491 1394313494838243595937 492 1474382563354803915085 493 1558964365999683074613 494 1648308537750414106953 495 1742678268100449611847 496 1842351023512832763442 497 1947619307642467964278 498 2058791461330586575622 499 2176192504347225657249 500 2300165021089419068952 501 2431070092418022487273 502 2569288276065504307953 503 2715220638025886920740 504 2869289837606360308513 505 3031941268803276476920 506 3203644260954040735587 507 3384893341604705942773 508 3576209564844022476053 509 3778141908348981052227 510 3991268742721761527865 511 4216199376699270251110 512 4453575682177226689544 513 4704073803000099272530 514 4968405951857006868636 515 5247322299642353245867 516 5541612962059113152679 517 5852110088272029301823 518 6179690056869992615311 519 6525275784438417916102 520 6889839152530041166649 521 7274403558878017174005 522 7680046599221361685466 523 8107902886184045041009 524 8559167012217003124632 525 9035096663701484203777 526 9537015893925419780365 527 10066318562753894897792 528 10624471951477169089588 529 11213020561451912363590 530 11833590105866969063946 531 12487891704122841344845 532 13177726289087528317331 533 13904989237678087105410 534 14671675236053409787840 535 15479883390922806563126 536 16331822599379157265868 537 17229817189920707520839 538 18176312848303624601423 539 19173882842163261632870 540 20225234559400284730184 541 21333216375668910407052 542 22500824867449777694201 543 23731212387581524092358 544 25027695021364986144676 545 26393760941801720637204 546 27833079183871095573373 547 29349508858260565066227 548 30947108826417896182113 549 32630147859374035820119 550 34403115304360736191295 551 36270732283904260084198 552 38237963453783683766341 553 40310029346985295265273 554 42492419332635027121458 555 44790905219728921088427 556 47211555537487792845605 557 49760750525105694500606 558 52445197865837217027678 559 55271949201428779116841 560 58248417465258579733558 561 61382395073739042773184 562 64682073018095314459693 563 68156060899965233223684 564 71813407957043619756217 565 75663625126483290900433 566 79716708196779446054602 567 83983162100527727470848 568 88474026403718124704516 569 93200902049082717746058 570 98175979414567344824938 571 103412067750065091446249 572 108922626059406499609847 573 114721795496902864502679 574 120824433351927767130655 575 127246148697580963417002 576 134003339784028503809709 577 141113233259955554685538 578 148593925310510996483693 579 156464424803277653274537 580 164744698539172157378084 581 173455718708676793192714 582 182619512659641068091919 583 192259215086767007509023 584 202399122759233988936366 585 213064751907210623110626 586 224282898394894220105537 587 236081700812466707533131 588 248490706626848810607184 589 261540941536384329556311 590 275264982182732339863084 591 289697032379046084240174 592 304873003022374194401047 593 320830595864625697847917 594 337609391326070893161092 595 355250940542419854884149 596 373798861846993293902512 597 393298941897298444624690 598 413799241666712587984124 599 435350207530573564981584 600 458004787688364705467816 601 481818554173154206647939 602 506849830712923678127567 603 533159826718853155069901 604 560812777690287466075541 605 589876092337593429983633 606 620420506740062553070129 607 652520245868650982523406 608 686253192820695396088625 609 721701066127642728219696 610 758949605515704457860813 611 798088766514627401377511 612 839212924330306710516083 613 882421087413760811957076 614 927817121181329821410160 615 975509982359408488174149 616 1025613964451334618536291 617 1078248954844314791178480 618 1133540704100721207924293 619 1191621108000335749559868 620 1252628502928901020485506 621 1316707975232747098507125 622 1384011685190584301105764 623 1454699206280330257971653 624 1528937880452923252750805 625 1606903190154441445227173 626 1688779147874937426697567 627 1774758704034595295801610 628 1865044174058178940153312 629 1959847685524030327601385 630 2059391646317798397724670 631 2163909234759747516262947 632 2273644912722290674390533 633 2388854962796750637423070 634 2509808050620364518045810 635 2636785813520934463833235 636 2770083476693126821099090 637 2910010498171208437475401 638 3056891243924599887027529 639 3211065694458213560898052 640 3372890184366566435685910 641 3542738176351486288589487 642 3721001071286160202476249 643 3908089055974821933752202 644 4104431990336732333423886 645 4310480335815893785649205 646 4526706126904289317875934 647 4753603987746029553871367 648 4991692195883745902899681 649 5241513795295583486671884 650 5503637760973375129395957 651 5778660217387686626426168 652 6067205713296648888425679 653 6369928555459425966308545 654 6687514203936178544758017 655 7020680731769935507901675 656 7370180351977438185351092 657 7736801014900059339326743 658 8121368079109122688606018 659 8524746059195411780870904 660 8947840453928463041092492 661 9391599658419150021858754 662 9857016964088552391230385 663 10345132650407577592294811 664 10857036172556163071184105 665 11393868449327134258117151 666 11956824255800322483014698 667 12547154725504883507877971 668 13166169967005862949802120 669 13815241800060911381141480 670 14495806616730262706741653 671 15209368373052021657885850 672 15957501717152782037132640 673 16741855259913296163192301 674 17564154994589459435153525 675 18426207872061176605540817 676 19329905538686744765911583 677 20277228244037291469781110 678 21270248926117524462633332 679 22311137482002723253494377 680 23402165232182577441105190 681 24545709587255277527495357 682 25744258926007399459351074 683 27000417694299612493518175 684 28316911734604554080834730 685 29696593856462172326554529 686 31142449658581279406265029 687 32657603613772504533043276 688 34245325428401608107698124 689 35909036688549332004983933 690 37652317805611537896014285 691 39478915274614927928116351 692 41392749259118792585584073 693 43397921517162967718937094 694 45498723683368996577325149 695 47699645922943621445369177 696 50005385974036643121311414 697 52420858595604262108670586 698 54951205438692841892037840 699 57601805359819000603474662 700 60378285195951897252570872 701 63286531021431800085405146 702 66332699908060779479437038 703 69523232210502666109508227 704 72864864400109105490798069 705 76364642471269230873491727 706 80029935945444761012971001 707 83868452499119264855007895 708 87888253243046433379334912 709 92097768681342811588174451 710 96505815380226183552484284 711 101121613377463154419598592 712 105954804364953341299868583 713 111015470678250417146487714 714 116314155128301446678593485 715 121861881712178747513348831 716 127670177241187003105570122 717 133751093926351389398127136 718 140117232963039076367946654 719 146781769158230887487149025 720 153758476645856316991340042 721 161061755737522995397780086 722 168706660958030620336266543 723 176708930317143825049056361 724 185085015871333645715009968 725 193852115631462463828622862 726 203028206874813650368926407 727 212632080922328497040700318 728 222683379444546674565044012 729 233202632362420629771711653 730 244211297412032778638086060 731 255731801445149400641190285 732 267787583540647316178970130 733 280403140005004923582809366 734 293604071343415594540170512 735 307417131286508568168891373 736 321870277961315369490577711 737 336992727298841531616069991 738 352815008774566808020653853 739 369369023582238301214291799 740 386688105345620914339442138 741 404807083477257196982204155 742 423762349297953416133758514 743 443591925035471946036194523 744 464335535825970145644169300 745 486034684846896342287654773 746 508732731715541987691404160 747 532474974293060890452597748 748 557308734039719031448072437 749 583283445073228722416763828 750 610450747088476353048165674 751 638864582303561724357887828 752 668581296604067248716382223 753 699659745064645933385135740 754 732161402034607502987105151 755 766150475981961494872192581 756 801694029298605836175380153 757 838862103277788550524293115 758 877727848483892258863417320 759 918367660743744929461894369 760 960861322998332144467428330 761 1005292153263714095175898635 762 1051747158960434279205319749 763 1100317197881473349129365816 764 1151097146080164504952463904 765 1204186072971161474980403464 766 1259687423949864974804737730 767 1317709210848371700200290052 768 1378364210559355305704532772 769 1441770172173011988950297629 770 1508050032986664303051583322 771 1577332143761493121815382136 772 1649750503616536265771386233 773 1725445004966217045539843942 774 1804561688924641591028712766 775 1887253011617380095173331989 776 1973678121859837263919138151 777 2064003150680256475593573121 778 2158401513185323107415770220 779 2257054223286855136195881315 780 2360150221829646521047313789 781 2467886718682765217788658974 782 2580469549379977344876278461 783 2698113546919059856657067253 784 2821042929355072819713077809 785 2949491703848759911066832890 786 3083704087858652217623573120 787 3223934948193719115747200194 788 3370450258673085638714680376 789 3523527577169953379152227453 790 3683456542848992029653701191 791 3850539394439627339970629176 792 4025091510422435918189496746 793 4207441972041764578456694243 794 4397934150095347438202568988 795 4596926316490574100723239945 796 4804792281597822234145006950 797 5021922058473363126606090609 798 5248722555068465608686870880 799 5485618295586895860658014661 800 5733052172200756853955072776 801 5991486228383942861790918367 802 6261402475174154528366038625 803 6543303741727816572394898335 804 6837714561588152017057985676 805 7145182096144458090795822440 806 7466277096821125857143746856 807 7801594907597487661989651253 808 8151756509525029225766795656 809 8517409608976180553171916046 810 8899229771429708670253048790 811 9297921602670963052672018506 812 9714219979361821687732959509 813 10148891331014412332908775919 814 10602734975485535365387045341 815 11076584510194423923525191024 816 11571309261356087197731164021 817 12087815793615197095310660572 818 12627049482562390524928388701 819 13189996152715142811847957447 820 13777683783650168270839179177 821 14391184287082764677538394589 822 15031615357801840475316901187 823 15700142401486658468410946644 824 16397980542553856602864147339 825 17126396715310144263389161328 826 17886711841818541283396046963 827 18680303100023172336941837979 828 19508606285820835426192981581 829 20373118272915841404377480730 830 21275399574449422880537584241 831 22217077010555312016888475737 832 23199846486160409183631364106 833 24225475883522748859518721210 834 25295808074179811202322040010 835 26412764055167531295195899741 836 27578346214565796732919042815 837 28794641731628664289892987611 838 30063826116968723317752487829 839 31388166898483815187389097442 840 32770027458942526001651200983 841 34211871031381292696609844298 842 35716264858712532511016912725 843 37285884524198671405754424986 844 38923518459713335540004713695 845 40632072638986989434577443775 846 42414575463322082282816339415 847 44274182847560966712044384212 848 46214183514400714796899613973 849 48238004505471098978319947086 850 50349216917927774240640034877 851 52551541875660674557003117780 852 54848856744580281380015528239 853 57245201601820273858532782533 854 59744785969086712449953956180 855 62351995820789835177148764658 856 65071400878017471194295972878 857 67907762199847451214444386386 858 70866040083953067108382128394 859 73951402288929011141721335301 860 77169232591258300669543519941 861 80525139690351829940021153844 862 84024966475624529842266449146 863 87674799670123977990957850567 864 91480979865801987524162007379 865 95450111966115488296775693343 866 99589076052263368590219944824 867 103905038690009100072969854050 868 108405464694708570191390346217 869 113098129372856782086926430043 870 117991131259189785624269383417 871 123092905369127519067687553301 872 128412236987123199070918699208 873 133958276012293599939552344383 874 139740551883546248685772779202 875 145768989107292292394209058933 876 152053923411742024742495446924 877 158606118552721811877965892640 878 165436783796931120991864689170 879 172557592109574512716587740484 880 179980699074360741319947550808 881 187718762574957463534128059941 882 195784963268130675380297574062 883 204193025879980791864624165313 884 212957241357917716166744084635 885 222092489912293197275566294980 886 231614264982935994035972062743 887 241538698167211705697520592575 888 251882585147660643386569885603 889 262663412658751635513369550893 890 273899386533833552191223966759 891 285609460874967410950227278180 892 297813368389986895915928457924 893 310531651942861781000275542279 894 323785697365234159668493685167 895 337597767578859334589170649695 896 351991038080619153170360131443 897 366989633843783269752149105352 898 382618667691281115110189450083 899 398904280198912040527492868615 900 415873681188671442935948006596 901 433555192874704459825541308124 902 451978294726824761059953474673 903 471173670119051866462141282421 904 491173254833235469736893928709 905 512010287490547283666939933518 906 533719361986439626275694427706 907 556336482007593211039856283815 908 579899117712414604361642188788 909 604446264659794485112907700210 910 630018505074111963845371396254 911 656658071537865766536298390009 912 684408913206841433959387926584 913 713316764646382878168438484834 914 743429217391138676600295476871 915 774795794334596503747799883631 916 807468027058815772154466621210 917 841499536219017113129437624128 918 876946115102101152330469255250 919 913865816482746481100965927228 920 952319042905491920131779161955 921 992368640526139612313992553269 922 1034079996650938090317058736851 923 1077521141117316897137693028096 924 1122762851665462361131708172040 925 1169878763455746580787716232746 926 1218945482892965219016835550932 927 1270042705924503391556267343359 928 1323253340985950367611540577149 929 1378663636774322269942046102468 930 1436363315035946080513479673811 931 1496445708563207580994021870747 932 1559007904601790066457252570247 933 1624150893877729620519413246565 934 1691979725461607245423596848408 935 1762603667695488392422900286894 936 1836136375416828453525298721895 937 1912696063722489121695789211489 938 1992405688525278497226071437750 939 2075393134165038397333674420733 940 2161791408346280164479662660474 941 2251738844684716814322278042148 942 2345379313155780707317198381076 943 2442862438749354030488349094655 944 2544343828646501858575446119260 945 2649985308245986956474206507514 946 2759955166380791034128592847796 947 2874428410077772027650248235100 948 2993587029226982130584552154351 949 3117620271541060584597158992146 950 3246724928199531469821531257679 951 3381105630587784519349241761834 952 3520975158556031082291169901788 953 3666554760639613218014263699953 954 3818074486698738358380968437743 955 3975773533453021383570966900153 956 4139900603404179365059484373851 957 4310714277658848998687809213191 958 4488483403182824273348404934524 959 4673487495038050657220654854678 960 4866017154174505922214730617288 961 5066374501370656329955436682463 962 5274873627938546813767598127895 963 5491841063832775984167536501942 964 5717616263826670630876949976967 965 5952552112443922297291484819519 966 6197015448359832841535773159950 967 6451387609013150637396587918057 968 6716064996197319787100716635765 969 6991459663428827081974148308642 970 7277999925920274442005612831446 971 7576130994016845707825369662077 972 7886315630987038561074295051442 973 8209034836091914541271779567373 974 8544788553891749083219964751026 975 8894096410784860936565931156382 976 9257498479810636834610913968387 977 9635556074787366947571452383468 978 10028852574895544451733430005144 979 10437994280858785145439196527647 980 10863611303917570075385113904591 981 11306358488835635076955122631331 982 11766916372225110578594029392569 983 12245992177524485482815423795315 984 12744320848013220306790643264348 985 13262666119298402843765274604600 986 13801821632762319923785340059976 987 14362612091515250772172609189883 988 14945894460455272527166835704039 989 15552559212096449906145800651364 990 16183531619888566747022682332937 991 16839773100815594595106513747985 992 17522282609126497425118196670348 993 18232098083120793896857275938039 994 18970297946982661285093492344045 995 19738002669731325196540588341999 996 20536376383432166187635064889116 997 21366628562892450501088269078851 998 22230015769147995411918585511089 999 23127843459132477891755600474976 1000 24061467864009635342386060541389