0 0 1 1 2 1 3 2 4 4 5 5 6 9 7 12 8 18 9 26 10 35 11 50 12 67 13 90 14 122 15 158 16 212 17 272 18 355 19 457 20 582 21 745 22 941 23 1185 24 1494 25 1858 26 2325 27 2875 28 3561 29 4388 30 5386 31 6604 32 8061 33 9815 34 11936 35 14440 36 17482 37 21058 38 25352 39 30438 40 36460 41 43610 42 52040 43 61980 44 73727 45 87464 46 103695 47 122619 48 144859 49 170820 50 201123 51 236498 52 277660 53 325524 54 381215 55 445675 56 520593 57 607118 58 707340 59 823037 60 956549 61 1110520 62 1287796 63 1491730 64 1726305 65 1995380 66 2304495 67 2658425 68 3064092 69 3528138 70 4058697 71 4664892 72 5356779 73 6145822 74 7045386 75 8069240 76 9235034 77 10559911 78 12065910 79 13775580 80 15715511 81 17915286 82 20407775 83 23229981 84 26424226 85 30035521 86 34118182 87 38728100 88 43932665 89 49803293 90 56422061 91 63879957 92 72278258 93 81729930 94 92362566 95 104314197 96 117745376 97 132826379 98 149755290 99 168745586 100 190038735 101 213901836 102 240631439 103 270556501 104 304045372 105 341499452 106 383375527 107 430165819 108 482430277 109 540777488 110 605888745 111 678515573 112 759489750 113 849730421 114 950259574 115 1062194417 116 1186788946 117 1325404580 118 1479568497 119 1650947035 120 1841391261 121 2052937947 122 2287834306 123 2548555046 124 2837836992 125 3158674575 126 3514397261 127 3908631792 128 4345408846 129 4829131121 130 5364661713 131 5957338975 132 6613033957 133 7338193091 134 8139915240 135 9025962969 136 10004910228 137 11086106200 138 12279872373 139 13597479781 140 15051323486 141 16654977375 142 18423326092 143 20372670458 144 22520896014 145 24887536660 146 27494062158 147 30363876092 148 33522688852 149 36998547885 150 40822186060 151 45027182903 152 49650262194 153 54731543777 154 60314912485 155 66448223911 156 73183872200 157 80578914260 158 88695790952 159 97602521801 160 107373412793 161 118089478627 162 129839100918 163 142718618027 164 156833127253 165 172297039259 166 189235219847 167 207783465448 168 228089920308 169 250315706711 170 274636377821 171 301242945295 172 330343319104 173 362163655613 174 396950083764 175 434970076569 176 476514772276 177 521900315615 178 571470686982 179 625599382262 180 684692405875 181 749190662655 182 819573066763 183 896359547550 184 980114735339 185 1071451168878 186 1171034036605 187 1279584527716 188 1397885533145 189 1526785713164 190 1667205676218 191 1820143354560 192 1986680624853 193 2167989879674 194 2365341818744 195 2580112652278 196 2813793806744 197 3067999736552 198 3344479455276 199 3645125848514 200 3971988398046 201 4327284925132 202 4713415522655 203 5132976652145 204 5588777428236 205 6083855330171 206 6621496028350 207 7205250777578 208 7838959756797 209 8526772572691 210 9273174317997 211 10083010659145 212 10961516795233 213 11914347168560 214 12947609138809 215 14067896440721 216 15282329476988 217 16598592817332 218 18024982300524 219 19570448864680 220 21244651553823 221 23058010082955 222 25021764295714 223 27148035812605 224 29449896891772 225 31941440249734 226 34637860414996 227 37555532565945 228 40712107068901 229 44126601055543 230 47819505362723 231 51812892797086 232 56130538804466 233 60798047534267 234 65842991079505 235 71295052709838 236 77186189828138 237 83550796347361 238 90425891155735 239 97851305838708 240 105869898478316 241 114527773308863 242 123874522842220 243 133963482168925 244 144852007472721 245 156601765422328 246 169279056734273 247 182955144920186 248 197706629041741 249 213615822252002 250 230771175280860 251 249267716012306 252 269207529962231 253 290700266867745 254 313863691874533 255 338824262239514 256 365717764013804 257 394689967718404 258 425897359327661 259 459507892742039 260 495701820685152 261 534672563341847 262 576627651790988 263 621789725334351 264 670397611032057 265 722707458706920 266 778993982260659 267 839551750021067 268 904696605727045 269 974767145141425 270 1050126330909736 271 1131163189181496 272 1218294643224689 273 1311967455163229 274 1412660319288692 275 1520886070187469 276 1637194080670054 277 1762172770661389 278 1896452345119936 279 2040707657727744 280 2195661320320453 281 2362086980805462 282 2540812851972132 283 2732725452594676 284 2938773627498820 285 3159972797363976 286 3397409549189440 287 3652246460574258 288 3925727328719033 289 4219182664252515 290 4534035624171206 291 4871808280287920 292 5234128346671558 293 5622736316387146 294 6039493110147413 295 6486388173440736 296 6965548186650707 297 7479246246270666 298 8029911765365585 299 8620140907050093 300 9252707804878386 301 9930576434929575 302 10656913325331787 303 11435101042922737 304 12268752615978954 305 13161726815347799 306 14118144539204403 307 15142406118238967 308 16239209902848446 309 17413571890181856 310 18670846762858942 311 20016750168915003 312 21457382524121183 313 22999254270831257 314 24649312840842571 315 26414971235093340 316 28304138588516477 317 30325252492206723 318 32487313602754001 319 34799922234211074 320 37273317480443843 321 39918418664157345 322 42746869541822273 323 45771085206945533 324 49004302079873376 325 52460630902493610 326 56155113295373895 327 60103781610004071 328 64323722858807794 329 68833146357704977 330 73651455894592795 331 78799326201739485 332 84298784392904388 333 90173296347707188 334 96447858657433351 335 103149096090590594 336 110305365430147616 337 117946865399756493 338 126105753845199652 339 134816271766391357 340 144114875419673281 341 154040376290366214 342 164634089962689146 343 175939993975608503 344 188004895643849448 345 200878609914152915 346 214614148572425253 347 229267920564355542 348 244899945185192269 349 261574077756089335 350 279358249635018237 351 298324722474090292 352 318550358336101695 353 340116905991909767 354 363111304972169861 355 387626007696092002 356 413759321729672399 357 441615772112257187 358 471306486424655902 359 502949602375361728 360 536670700735971979 361 572603263831819568 362 610889162143891761 363 651679169814175976 364 695133511602137790 365 741422442130047423 366 790726860651617449 367 843238961719513143 368 899162925867821628 369 958715650522909046 370 1022127525529607694 371 1089643254139372233 372 1161522723547253491 373 1238041926673006741 374 1319493939336560024 375 1406189954658773986 376 1498460379833967986 377 1596655996575690513 378 1701149191644353490 379 1812335258637763095 380 1930633777914997678 381 2056490076778859713 382 2190376776503541138 383 2332795429574915190 384 2484278253939436144 385 2645389967939210502 386 2816729734189499053 387 2998933215518355082 388 3192674753052122341 389 3398669669567910804 390 3617676708979650028 391 3850500616506925952 392 4097994870210403186 393 4361064570281931263 394 4640669497264131224 395 4937827346217781269 396 5253617150175610332 397 5589182899410393610 398 5945737372530384603 399 6324566186202716224 400 6727032080842821694 401 7154579451255485518 402 7608739139647055660 403 8091133502753346755 404 8603481771508894651 405 9147605716202569794 406 9725435638792508250 407 10339016705093639459 408 10990515642468391711 409 11682227816552304940 410 12416584714876595041 411 13196161854297593929 412 14023687140746156828 413 14902049702394327318 414 15834309226673135063 415 16823705824440938125 416 17873670456663610809 417 18987835947293532916 418 20170048623637646782 419 21424380609743313998 420 22755142817832092563 421 24166898668588814520 422 25664478587094733043 423 27252995311635570174 424 28937860065691806864 425 30724799634268493578 426 32619874402425444830 427 34629497398830602473 428 36760454411177386248 429 39019925219974896926 430 41415506023799258574 431 43955233110828468291 432 46647607853547318181 433 49501623091401244061 434 52526790984542304507 435 55733172410302641078 436 59131407997233274924 437 62732750872436960399 438 66549101230771161074 439 70593042808580879983 440 74877881380927093175 441 79417685378145794727 442 84227328748138619416 443 89322536175789280317 444 94719930796795296046 445 100437084529103801312 446 106492571177490057177 447 112906022442961240379 448 119698187013741338420 449 126890992882035891527 450 134507613080534562156 451 142572535003841579645 452 151111633522542017232 453 160152248079569586000 454 169723263995239814756 455 179855198190645526186 456 190580289584438350386 457 201932594388931229029 458 213948086593563275499 459 226664763883644040158 460 240122759310792664012 461 254364458996544134867 462 269434626210052393299 463 285380532140075715859 464 302252093733728083344 465 320102018955845628277 466 338985959886701624386 467 358962674041468711302 468 380094194380859336564 469 402446008434191253588 470 426087247050914483644 471 451090883255593964799 472 477533941765007708998 473 505497719703813405023 474 535068019130252603113 475 566335391964438561738 476 599395398002399125841 477 634348876660468211047 478 671302233214546792943 479 710367740242985228001 480 751663855113843358962 481 795315554311473024651 482 841454685515905070900 483 890220338327786852900 484 941759234639980382969 485 996226139641320384743 486 1053784294567532262940 487 1114605872274406123090 488 1178872456876675017533 489 1246775548635112545108 490 1318517095459523873348 491 1394310052348375677408 492 1474378970255033895382 493 1558960615857216180194 494 1648304623863933303946 495 1742674183488866935388 496 1842346760905624161501 497 1947614859465393962200 498 2058786819695714426664 499 2176187661038940042523 500 2300159967550745413151 501 2431064819738784486508 502 2569282774965146839136 503 2715214898841209672409 504 2869283850274593513462 505 3031935022845554086428 506 3203637745460823481842 507 3384886545215213959416 508 3576202475731090963050 509 3778134514198691768003 510 3991261030713386069090 511 4216191333487461607356 512 4453567293867292997434 513 4704065055129452231454 514 4968396829370551434508 515 5247312786868274552367 516 5541603042687041774757 517 5852099745323434417105 518 6179679272675380823473 519 6525264540607731024712 520 6889827429923323712349 521 7274391337578812585497 522 7680033858501142438095 523 8107889604474370180008 524 8559153167073796742209 525 9035082231769660867419 526 9537000850906378620723 527 10066302883362934717443 528 10624455609409402199725 529 11213003529339325754009 530 11833572355235643436569 531 12487873205353443064226 532 13177707011364184444403 533 13904969148946882055961 534 14671654302970635757740 535 15479861578803425855194 536 16331799872148678546939 537 17229793510053994788671 538 18176288176774262398522 539 19173857138381396275440 540 20225207781150398206549 541 21333188479051464126195 542 22500795806807806516836 543 23731182115439144483740 544 25027663488352576762022 545 26393728096581042807307 546 27833044973064409555399 547 29349473226362805270184 548 30947071715721881555894 549 32630109209880674559574 550 34403075053688759507420 551 36270690367204450242206 552 38237919803633603519838 553 40309983893298680070229 554 42492372002553834530474 555 44790855937514833109906 556 47211504224418296095102 557 49760697099348193556587 558 52445142242339139214696 559 55271891291788130163432 560 58248357177593350666458 561 61382332312561715565418 562 64682007684162097443088 563 68155992890143218939413 564 71813337164155360857755 565 75663551439150012225566 566 79716631499269352919066 567 83983082272575819819719 568 88473943320365485082106 569 93200815580490313324911 570 98175889425827588362825 571 103411974101019004267412 572 108922528604428108075352 573 114721694084705333152971 574 120824327825340103612826 575 127246038893322045593097 576 134003225532486552498570 577 141113114384930623896607 578 148593801628980978342498 579 156464296125131027770383 580 164744564666936790674420 581 173455579437254608706267 582 182619367776000201555072 583 192259064369660087647058 584 202398965978878029438084 585 213064588824962183201809 586 224282728762930023975472 587 236081524373416227448443 588 248490523113454964310169 589 261540750671120738435005 590 275264783677414014657849 591 289696825934445815984171 592 304872788327783730002154 593 320830372597447983611403 594 337609159151362181796468 595 355250699112423939443450 596 373798610800680620786239 597 393298680859842773314180 598 413798970249000868657524 599 435349925328659004746509 600 458004494282909311512096 601 481818249128876114735330 602 506849513577972697352450 603 533159497024222785081527 604 560812434949161347617802 605 589875736044679195452720 606 620420136370928995940098 607 652519860878983938535083 608 686252792645592307172412 609 721700650180832805132320 610 758949173188752443271639 611 798088317176139976614856 612 839212457325045464735523 613 882420602061797348650971 614 927816616777114994294561 615 975509458170822018448073 616 1025613419718734915670051 617 1078248388779482835846467 618 1133540115885848662951144 619 1191620496786915488818023 620 1252627867836592612489229 621 1316707315348240877555055 622 1384010999566343648925805 623 1454698493933381577071775 624 1528937140363533301736288 625 1606902421264764746260540 626 1688778349087658365494201 627 1774757874211431965698485 628 1865043312018436349964051 629 1959846790043025422924024 630 2059390716125247432815425 631 2163908268538145033468887 632 2273643909105129503501239 633 2388853920366794404987182 634 2509806967907772163718805 635 2636784689001339824285887 636 2770082308785703782030738 637 2910009285236555378675083 638 3056889984262677418077539 639 3211064386306113590795505 640 3372888825896225361242083 641 3542736765667378431106965 642 3720999606422783387666599 643 3908087534894238662776246 644 4104430410925916178132325 645 4310478695884009182109950 646 4526704424179942441678639 647 4753602219874282624497159 648 4991690360423186243193061 649 5241511889715170279678788 650 5503635782649204101390844 651 5778658163599717156871882 652 6067203581225158907443383 653 6369926342181522241946088 654 6687511906422050179592376 655 7020678346879009749674860 656 7370177876454484981230552 657 7736798445370985669324046 658 8121365412076818746804072 659 8524743291035303663533602 660 8947837580883945955951060 661 9391596676596956681906592 662 9857013869453764303966555 663 10345129438778685925381190 664 10857032839599790381230381 665 11393864990552614208151769 666 11956820666554194588780513 667 12547151000964980390836974 668 13166166102175439313138130 669 13815237789762384850879294 670 14495802455598782059936535 671 15209364055528929395760668 672 15957497237478607672783562 673 16741850612120784213952198 674 17564150172496148761989357 675 18426202869261774866572498 676 19329900348545367846366348 677 20277222859679166727757993 678 21270243340420714179924347 679 22311131687589333944124976 680 23402159221409721430832031 681 24545703352205868577463132 682 25744252458480330610824436 683 27000410985799939664766073 684 28316904776333085146607336 685 29696586639304762546017803 686 31142442173097918492776843 687 32657595850185697006669997 688 34245317376584734893951437 689 35909028338014329894533815 690 37652309145496225542559987 691 39478906293670077934293888 692 41392739945694388938236829 693 43397911859194418706505202 694 45498713668362558653779578 695 47699635537961404661782602 696 50005375205681301902183541 697 52420847430002752990097632 698 54951193861480097441504947 699 57601793356120696947137018 700 60378272750366719899956037 701 63286518118013328833179612 702 66332686530298297269965185 703 69523218341301841457485402 704 72864850021771626102304137 705 76364627565471844109835582 706 80029920493217847001944155 707 83868436480824175791928356 708 87888236638352645530100384 709 92097751469203871226913585 710 96505797538854944116374232 711 101121594884306450886788562 712 105954785196665240994190589 713 111015450810665215939343993 714 116314134536405269189350926 715 121861860370080310380057758 716 127670155122087693224493161 717 133751071002513708142082700 718 140117209205754737256287653 719 146781744537787306964315365 720 153758451131502108123287745 721 161061729297432640281242351 722 168706633559267256342973176 723 176708901925621581500460358 724 185084986451778120081277774 725 193852085147370022016640870 726 203028175288409733710557711 727 212632048194523762150471045 728 222683345534892547317718573 729 233202597229062715852709838 730 244211261011662876897672034 731 255731763732956329990474668 732 267787544470265239928559092 733 280403099528460933755768180 734 293604029411074813895382041 735 307417087847017606403777111 736 321870232961544352103507945 737 336992680683823250830926661 738 352814960487434934551969256 739 369368973564162733969271546 740 386688053535741179262666938 741 404807029812614146444126991 742 423762293713417603705975393 743 443591867463670835425177082 744 464335476197212004417602918 745 486034623089091840262397127 746 508732667754123759980871937 747 532474908050899274091614332 748 557308665437036348688298028 749 583283374027509738974881339 750 610450673514376021482121065 751 638864506112810510847476910 752 668581217705372038091244251 753 699659663363589151990681610 754 732161317433541810195809845 755 766150388379901283935461661 756 801693938591115851949615367 757 838862009356867414330357930 758 877727751237853800179424709 759 918367560057094401746707384 760 960861218751638674576536206 761 1005292045333479718075022777 762 1051747047218957085811067837 763 1100317082196707969212861732 764 1151097026315576662611450193 765 1204185948985578122489773823 766 1259687295597320366085437804 767 1317709077977946679606424528 768 1378364073015013349104368718 769 1441770029793428398364628622 770 1508049885605050191213091944 771 1577331991205414598401254575 772 1649750345707725779398498282 773 1725444841520380807394181018 774 1804561519751259065483199671 775 1887252836519497380493982244 776 1973677940633854783971469278 777 2064002963115707626031600186 778 2158401319064648162989737930 779 2257054022385165991385689611 780 2360150013914484243248210543 781 2467886503513850891085701466 782 2580469326708952453844379929 783 2698113316489220985245206214 784 2821042690901095728534299335 785 2949491457096415194647562340 786 3083703832524513027384058599 787 3223934683984856815603976257 788 3370449985286758627562565977 789 3523527294293283636124266369 790 3683456250158631769663680810 791 3850539091601416329034709462 792 4025091197091044832689145571 793 4207441647860330205645940130 794 4397933814695093651405627534 795 4596925969490421260514279319 796 4804791922603985569694209238 797 5021921687078935010295833629 798 5248722170852988073829077349 799 5485617898115916672752916180 800 5733051761025372007277082352 801 5991485803040326125338843857 802 6261402035183068362927570087 803 6543303286594111443881032263 804 6837714090800246655353861586 805 7145181609173803877694501759 806 7466276593121655966622467984 807 7801594386605044694575641488 808 8151755970656779025372703439 809 8517409051630003990925517913 810 8899229194983574839055029578 811 9297921006482284570545400041 812 9714219362766785127249754086 813 10148890693327292273223312400 814 10602734315997982920657798189 815 11076583828174733558409169998 816 11571308556048442518233497276 817 12087815064238887918107372731 818 12627048728311010515773970015 819 13189995372755757608323831079 820 13777682977122458205399654638 821 14391183453098142866692385760 822 15031614495442537690393569678 823 15700141509804785043271243087 824 16397979620570430155808848565 825 17126395762014087779052696119 826 17886710856165652296581040320 827 18680302080935053754367103112 828 19508605232183799189710636151 829 20373117183579772621139721988 830 21275398448226609321848158894 831 22217075846219239804314040586 832 23199845282444514110405746629 833 24225474639119135699518573781 834 25295806787737927240601971647 835 26412762725292799482588519988 836 27578344839818209238062687270 837 28794640310521324813422271335 838 30063824647966351649860088333 839 31388165380001198829232036299 840 32770025889342924665125033411 841 34211869408974796525728469457 842 35716263181754361055756033911 843 37285882790887428193542888443 844 38923516668189201363632267818 845 40632070787329860750854904286 846 42414573549549655488534264752 847 44274180869626753993267787541 848 46214181470192007736707219993 849 48238002392806861306778300441 850 50349214734556470594203150888 851 52551539619258036068251600134 852 54848854412746992157592768700 853 57245199192079596157061661034 854 59744783478882029832141556524 855 62351993247482121201775531676 856 65071398218882684328693313783 857 67907759452073838385848506801 858 70866037244638395278903614456 859 73951399355077704079069233807 860 77169229559778488984369770037 861 80525136558052315114476016858 862 84024963239211642655986621561 863 87674796326198352634402177014 864 91480976410855226024289768945 865 95450108396526724085575834695 866 99589072364295729753242080628 867 103905034879806050654549302615 868 108405460758290152714288571644 869 113098125306115733295368004103 870 117991127057887534883569010374 871 123092901028890069936677781982 872 128412232503436869957470238840 873 133958271380500649236727072864 874 139740547098840353279348241578 875 145768984164713889831726740319 876 152053918306173519300700668304 877 158606113278882617934051875457 878 165436778349372571288140438277 879 172557586482674597195069980606 880 179980693262318687482748374515 881 187718756571788158472379914325 882 195784957067658899845452257078 883 204193019475835296594417345381 884 212957234743525102322843963029 885 222092483080871612903402112373 886 231614257927488646281696144076 887 241538690880520156062055085724 888 251882577622277918789860957744 889 262663404886995113074440807057 890 273899378507777630355196935388 891 285609452586435966493198990649 892 297813359830545490378072830108 893 310531643103809652377484348483 894 323785688237595952586686223737 895 337597758153376582639045009388 896 351991028347741512347663901186 897 366989623793659462729202997633 898 382618657313749625145069473698 899 398904269483491503374192507767 900 415873670124550751192519898243 901 433555181450732578300357322494 902 451978282931500208288999877554 903 471173657940511904729383169934 904 491173242259244946218723282745 905 512010274508487138261573361131 906 533719348583295063866825714522 907 556336468169941488595041304334 908 579899103426412478655685870025 909 604446249911165257713368867383 910 630018489848132139690391389328 911 656658055819351323258285627289 912 684408896980133646693099690856 913 713316747895333749721955702909 914 743429200099095902576488235259 915 774795776484387990119661994718 916 807468008632733701281804139602 917 841499517198801497093744322276 918 876946095468922927411481163717 919 913865796217190065609842463472 920 952319021987537253838255449854 921 992368618935143672532936278654 922 1034079974365615816543196665346 923 1077521118115721582734206465056 924 1122762827924965425625172619679 925 1169878738953016742182288155320 926 1218945457603947059570944776469 927 1270042679824395241642140156452 928 1323253314049181570653390201937 929 1378663608974529732893316056068 930 1436363286345950129915256904837 931 1496445678954987116680093205770 932 1559007874046456928890622653310 933 1624150862345502240076315208313 934 1691979692921783467429878228628 935 1762603634116417499089284600688 936 1836136340765882372607087134331 937 1912696027966032728838475895145 938 1992405651628639085374654848320 939 2075393096092474195786714381685 940 2161791369060947929156571143922 941 2251738804148638477061294544940 942 2345379271329808980480192404813 943 2442862395593137046238384305900 944 2544343784118446712286433092983 945 2649985262303222176763712941299 946 2759955118979127964258250895222 947 2874428361171665003354176273723 948 2993586978769487539331482917445 949 3117620219483794661875145312283 950 3246724874492626855003271074025 951 3381105575179845553009575383128 952 3520975101394087716797252050052 953 3666554701669073633056796405751 954 3818074425863340120857305456322 955 3975773470694781174957258490909 956 4139900538663341253951170530259 957 4310714210873831116370343810523 958 4488483334290163990259237148468 959 4673487423972348082552326979202 960 4866017080868365749298734670315 961 5066374425754628001054914964725 962 5274873549941062845712192928976 963 5491840983380088559998670878751 964 5717616180842786259781843100305 965 5952552026850534565470052883596 966 6197015360076253221937803867100 967 6451387517956237182367234996618 968 6716064902281403815775785928582 969 6991459566565637643445602689231 970 7277999826018860575546508527799 971 7576130890983496462464289201878 972 7886315524725200578142317877803 973 8209034726502107319630556162669 974 8544788440871477683504079030121 975 8894096294228526144833312881556 976 9257498359609442740000796579979 977 9635555950829225715885738523559 978 10028852447064978421662625104863 979 10437994149036825977399771811298 980 10863611167981654970744764796460 981 11306358348659500014447162946199 982 11766916227678680324430182815917 983 12245992028473760509480944674179 984 12744320694320160319930208323172 985 13262665960820806932688576507307 986 13801821469353703272041776735207 987 14362611923024717657579491055013 988 14945894286727385753387790849226 989 15552559032971096332482614359746 990 16183531435200818927515032272525 991 16839772910395568452705079786802 992 17522282412799205658649305776007 993 18232097880705995271257011194324 994 18970297738294705433694925103489 995 19738002454578992942287239355640 996 20536376161618505295102283171327 997 21366628334214606523089660006914 998 22230015533397037788011659071714 999 23127843216093220886708403726422 1000 24061467613460453824471851017603