0 1 1 1 2 1 3 1 4 2 5 2 6 5 7 7 8 13 9 18 10 28 11 40 12 60 13 80 14 113 15 152 16 205 17 266 18 353 19 454 20 590 21 751 22 959 23 1210 24 1529 25 1905 26 2381 27 2953 28 3658 29 4501 30 5539 31 6772 32 8278 33 10065 34 12230 35 14801 36 17893 37 21544 38 25921 39 31089 40 37240 41 44478 42 53068 43 63150 44 75063 45 89018 46 105438 47 124632 48 147150 49 173390 50 204089 51 239802 52 281446 53 329784 54 386007 55 451121 56 526666 57 613990 58 715054 59 831652 60 966298 61 1121325 62 1299975 63 1505316 64 1741443 65 2012360 66 2323320 67 2679484 68 3087529 69 3554135 70 4087756 71 4696988 72 5392565 73 6185455 74 7089265 75 8118027 76 9288850 77 10619618 78 12131917 79 13848398 80 15796223 81 18004062 82 20505985 83 23338197 84 26543387 85 30167073 86 34262676 87 38887385 88 44107819 89 49995628 90 56633875 91 64112050 92 72533496 93 82009862 94 92669403 95 104651100 96 118113983 97 133230590 98 150197795 99 169229530 100 190568943 101 214480768 102 241265020 103 271248586 104 304801000 105 342325337 106 384275959 107 431149010 108 483502464 109 541945844 110 607163349 111 679902801 112 761001752 113 851376212 114 952050248 115 1064144029 116 1188907824 117 1327709648 118 1482073711 119 1653668231 120 1844349124 121 2056147594 122 2291320453 123 2552337780 124 2841940037 125 3163126885 126 3519222222 127 3913863814 128 4351078118 129 4835271373 130 5371314901 131 5964539000 132 6620830384 133 7346628996 134 8149040177 135 9035835556 136 10015581153 137 11097644482 138 12292341296 139 13610949355 140 15065877594 141 16670688656 142 18440292766 143 20390982201 144 22540653887 145 24908857422 146 27517052010 147 30388671387 148 33549418902 149 37027354601 150 40853234713 151 45060623971 152 49686287809 153 54770335705 154 60356672657 155 66493181469 156 73232243129 157 80630964128 158 88751778160 159 97662727911 160 107438158820 161 118159067762 162 129913903970 163 142798995251 164 156919474615 165 172389799571 166 189334821890 167 207890419411 168 228204732059 169 250438924402 170 274768616415 171 301384801328 172 330495498889 173 362326859167 174 397125074021 175 435157697096 176 476715856552 177 522115830445 178 571701604903 179 625846752366 180 684957390181 181 749474411000 182 819876907541 183 896684816740 184 980462879641 185 1071823773541 186 1171432691575 187 1280011041465 188 1398341744766 189 1527273598816 190 1667727403277 191 1820701099831 192 1987276855541 193 2168627104617 194 2366022740992 195 2580840212118 196 2814570986731 197 3068829877661 198 3345365982828 199 3646072431244 200 3972999028506 201 4328363657749 202 4714566885183 203 5134205287071 204 5590088316591 205 6085253858345 206 6622987707123 207 7206841705571 208 7840656225214 209 8528581301440 210 9275102574418 211 10085065884815 212 10963707204306 213 11916681235321 214 12950095924936 215 14070545698326 216 15285151247518 217 16601598106920 218 18028182515675 219 19573856160147 220 21248279008367 221 23061871172838 222 25025873759098 223 27152408924597 224 29454549940731 225 31946390695119 226 34643126321472 227 37561133581521 228 40718063626312 229 44132934883194 230 47826239744858 231 51820051837645 232 56138148669875 233 60806135437250 234 65851585969195 235 71304185513828 236 77195892662419 237 83561103924774 238 90436839667718 239 97862933702481 240 105882246721628 241 114540884551895 242 123888443076115 243 133978259343740 244 144867692495290 245 156618412526787 246 169296722390391 247 182973889852858 248 197726516680502 249 213636919819448 250 230793554363502 251 249291451167373 252 269232701251392 253 290726957914899 254 313891991305450 255 338854264247463 256 365749566869560 257 394723676654113 258 425933084408111 259 459545750447425 260 495741934759594 261 534715062907346 262 576672674945901 263 621837416508346 264 670448123058900 265 722760953689081 266 779050629560874 267 839611730365516 268 904760108315060 269 974834369943321 270 1050197489929812 271 1131238503937280 272 1218374349843006 273 1312051800814876 274 1412749565172106 275 1520980492849829 276 1637293969335821 277 1762278433055908 278 1896564103590222 279 2040825852573711 280 2195786311681148 281 2362219145336322 282 2540952590044308 283 2732873183546140 284 2938929793928159 285 3160137867147597 286 3397584011985368 287 3652430836069643 288 3925922161488010 289 4219388528585636 290 4534253126899425 291 4872038056470618 292 5234371069752204 293 5622992691949133 294 6039763882094042 295 6486674127077604 296 6965850144194345 297 7479565078509091 298 8030248384941540 299 8620496275463523 300 9253082936722098 301 9930972392401971 302 10657331232547307 303 11435542077820570 304 12269218019227929 305 13162217895056156 306 14118662665278455 307 15142952738855633 308 16239786535828101 309 17414180133145722 310 18671488299598789 311 20017426762575365 312 21458096037351310 313 23000006655485735 314 24650106150828887 315 26415807633564721 316 28305020340994387 317 30326181989841344 318 32488293351465033 319 34800954869439204 320 37274405776746449 321 39919565526998333 322 42748078035953036 323 45772358543576363 324 49005643635236208 325 52462044228826945 326 56156602112872589 327 60105349839664842 328 64325374609112846 329 68834885946072139 330 73653287861848626 331 78801255302664887 332 84300815636223390 333 90175434980547890 334 96450110192201023 335 103151466321733586 336 110307860425291031 337 117949491546112193 338 126108517833794575 339 134819180623299736 340 144117936527872046 341 154043597379574233 342 164637479165759245 343 175943559810420943 344 188008647052291167 345 200882556287681339 346 214618299743284474 347 229272286871215323 348 244904537455380578 349 261578907351142286 350 279363328483700312 351 298330063062756225 352 318555973788327226 353 340122810048575551 354 363117512048108127 355 387632532919027340 356 413766180933340477 357 441622981929356548 358 471314064268396886 359 502957566505998124 360 536679070310689224 361 572612058898035610 362 610898403751882150 363 651688879997205006 364 695143713458944083 365 741433159884079716 366 790738119649409349 367 843250788562526452 368 899175348396086373 369 958728697912336057 370 1022141228367343370 371 1089657644424397785 372 1161537834849960851 373 1238057794119123075 374 1319510599727471489 375 1406207446561482038 376 1498478743590579058 377 1596675274490754761 378 1701169427975811493 379 1812356499739470897 380 1930656072350463758 381 2056513475336631740 382 2190401332423763064 383 2332821198543890267 384 2484305294265416110 385 2645418340688761586 386 2816759503217940672 387 2998964447736450072 388 3192707518433530700 389 3398704041358158145 390 3617712763867602292 391 3850538434667427040 392 4098034535626592643 393 4361106170762281950 394 4640713124699621349 395 4937873096788189487 396 5253665124416972993 397 5589233202595402292 398 5945790114707872400 399 6324621482504292126 400 6727090051741039722 401 7154640222653940088 402 7608802843339877035 403 8091200276484463342 404 8603551759348652819 405 9147679068859115357 406 9725512513742019472 407 10339097267123944979 408 10990600063775924730 409 11682316277192315495 410 12416677403151188096 411 13196258966925433411 412 14023788883518845051 413 14902156290309946671 414 15834420884488185471 415 16823822787139233234 416 17873792969689873692 417 18987964267331662226 418 20170183018805931326 419 21424521360255633982 420 22755290216580022920 421 24167053021441361586 422 25664640213837712470 423 27253164546230419361 424 28938037257084795768 425 30724985147095048710 426 32620068617410229796 427 34629700713903573536 428 36760667241831524909 429 39020148000237257261 430 41415739207102355969 431 43955477170518114120 432 46647863284229265576 433 49501890409405148243 434 52527070729108238132 435 55733465144636284178 436 59131714309169616162 437 62733071376043076728 438 66549436566966294878 439 70593393646562133016 440 74878248419470883738 441 79418069346443399724 442 84227730407729497256 443 89322956321353643137 444 94720370257893469289 445 100437544171752845062 446 106493051905239116037 447 112906525199196100808 448 119698712782720203406 449 126891542690981415422 450 134508188001572921261 451 142573136155347401624 452 151112262071917311071 453 160152905244553712974 454 169723951046458038352 455 179855916453958264983 456 190581040442651928414 457 201933379285114685988 458 213948907032733066490 459 226665621435831342921 460 240123655613925189430 461 254365395758574197313 462 269435605212954991808 463 285381555241961983609 464 302253162872576633926 465 320103136152993287853 466 338987127249525429853 467 358963893768162873915 468 380095468763120595778 469 402447339861711472435 470 426088638015652410690 471 451092336355096097132 472 477535459708164112859 473 505499305314204626817 474 535069675351607259382 475 566337121865805596927 476 599397204782301850174 477 634350763653787025820 478 671304203896731804465 479 710369798236628235236 480 751666004194993122821 481 795317798414758229346 482 841457028742823646619 483 890222784951928085456 484 941761789114997695212 485 996228806608573408160 486 1053787078862455343659 487 1114608778936426481375 488 1178875491155735799772 489 1246778716001272916784 490 1318520401612270230340 491 1394313503224447814045 492 1474382572040363950237 493 1558964374994977803267 494 1648308547066172435852 495 1742678277747760978274 496 1842351033503159888542 497 1947619317987658061071 498 2058791472042884898625 499 2176192515439287458682 500 2300165032574323992083 501 2431070104309287324916 502 2569288288377098286319 503 2715220650772245310256 504 2869289850802400659080 505 3031941282464413129725 506 3203644275096202066993 507 3384893356244349841317 508 3576209579998154650643 509 3778141924035171534078 510 3991268758958164115267 511 4216199393504640095434 512 4453575699570940944328 513 4704073821002175838982 514 4968405970488126316688 515 5247322318923878790887 516 5541612982013113933042 517 5852110108921301657938 518 6179690078238084804896 519 6525275806549652785006 520 6889839175409542382537 521 7274403582551733374214 522 7680046623716094329420 523 8107902911527474121002 524 8559167038437716733005 525 9035096690829005912052 526 9537015921990240018378 527 10066318591787500103424 528 10624471981512075017567 529 11213020592521695108378 530 11833590138006300413206 531 12487891737367521800443 532 13177726323474524609095 533 13904989273245567331788 534 14671675272840783229249 535 15479883428970761065728 536 16331822638729701490570 537 17229817230617210717359 538 18176312890390861431792 539 19173882885687454480866 540 20225234604409151262973 541 21333216422211708567298 542 22500824915577356162192 543 23731212437346370135052 544 25027695072821279143115 545 26393760995005382964830 546 27833079238879849382361 547 29349508915133986371500 548 30947108885217475098534 549 32630147920163234057554 550 34403115367205050939810 551 36270732348871285125391 552 38237963520943177234191 553 40310029416409244583738 554 42492419404397720869214 555 44790905293907018005743 556 47211555614160398036945 557 49760750604354432753979 558 52445197947746313624009 559 55271949286085137712546 560 58248417552751868046596 561 61382395164161775315047 562 64682073111542943377000 563 68156060996536236168718 564 71813408056839596200113 565 75663625229609055440169 566 79716708303343130518129 567 83983162210640879998849 568 88474026517495817977769 569 93200902166643654184089 570 98175979536033971308896 571 103412067875563710988939 572 108922626189067392952529 573 114721795630860408654972 574 120824433490320564233604 575 127246148840551966558775 576 134003339931725153593943 577 141113233412529912742951 578 148593925468119890194007 579 156464424966082817444448 580 164744698707340387580626 581 173455718882380096091623 582 182619512839056823916260 583 192259215272078129522645 584 202399122950629095576541 585 213064752104884207156488 586 224282898599046831030979 587 236081701023305130942267 588 248490706844586261410203 589 261540941761240642262029 590 275264982414934173202959 591 289697032618827122971284 592 304873003269975366028093 593 320830596120295386607105 594 337609391590065169557232 595 355250940815002702554463 596 373798862128436852705701 597 393298942187883251153311 598 413799241966727832974292 599 435350207840317348266260 600 458004788008144308549881 601 481818554503286362919946 602 506849831053734861478078 603 533159827070679866275188 604 560812778053476538345617 605 589876092712502332460057 606 620420507127059714303541 607 652520246268116112053348 608 686253193233019826876660 609 721701066553229757375644 610 758949605954969709101880 611 798088766967999186002921 612 839212924798226411056947 613 882421087896683264550301 614 927817121679723721845920 615 975509982873756796921627 616 1025613964982134990449412 617 1078248955392080004470886 618 1133540704665979618902758 619 1191621108583631746906236 620 1252628503530795506436999 621 1316707975853817969916640 622 1384011685831426958554951 623 1454699206941558115137746 624 1528937881135168275059443 625 1606903190858354689124401 626 1688779148601189609512754 627 1774758704783877366654012 628 1865044174831202682772554 629 1959847686321528964665509 630 2059391647140527228525491 631 2163909235608484556358400 632 2273644913597837330077111 633 2388854963699932382731950 634 2509808051552031608078501 635 2636785814481962651215039 636 2770083477684418110391083 637 2910010499193691843298965 638 3056891244979232231858421 639 3211065695545980277244682 640 3372890185488482409680957 641 3542738177508596708703767 642 3721001072479541451504289 643 3908089057205582486664821 644 4104431991606013700452996 645 4310480337124871462072823 646 4526706128254173781040168 647 4753603989138067267822810 648 4991692197319220372386408 649 5241513796775816319679507 650 5503637762499727151302900 651 5778660218961559003719374 652 6067205714919484306339330 653 6369928557132709817138714 654 6687514205661440172549434 655 7020680733548749464949656 656 7370180353811425547657916 657 7736801016790889035128049 658 8121368081058512888502818 659 8524746061205131302390706 660 8947840456000332817669452 661 9391599660555044587637236 662 9857016966290401433255310 663 10345132652677367520052392 664 10857036174895938656579006 665 11393868451739000294448643 666 11956824258286445517625184 667 12547154728067493595497743 668 13166169969647255482976069 669 13815241802783448943201842 670 14495806619536377005375098 671 15209368375944215483237663 672 15957501720133631304226446 673 16741855262985451980942780 674 17564154997755650263617108 675 18426207875324210441990742 676 19329905542049511423194926 677 20277228247502764885896365 678 21270248929688765106873605 679 22311137485682880566291355 680 23402165235974892374949875 681 24545709591163085124242053 682 25744258930034131533258942 683 27000417698448800353549410 684 28316911738879831363620964 685 29696593860867277871600839 686 31142449663120060247015911 687 32657603618448918933400167 688 34245325433219728719768927 689 35909036693513349075720190 690 37652317810725762600760676 691 39478915279883795756618809 692 41392749264546866860888893 693 43397921522754943172588268 694 45498723689129703063644912 695 47699645928878027716134729 696 50005385980149860746057621 697 52420858601901549459653967 698 54951205445179608281714507 699 57601805366500810491214433 700 60378285202834474611024090 701 63286531028521032840980915 702 66332699915362724119976098 703 69523232218023552371147703 704 72864864407855341219965206 705 76364642479247406973527705 706 80029935953661656574118920 707 83868452507581852374817942 708 87888253251761884175125525 709 92097768690318501305948176 710 96505815389469697877045264 711 101121613386982294887574995 712 105954804374756131323434518 713 111015470688345108146845604 714 116314155138696524440179117 715 121861881722882938654955439 716 127670177252209281782735813 717 133751093937700984130076573 718 140117232974725477106755538 719 146781769170263852819568789 720 153758476658245881594401876 721 161061755750279477635529947 722 168706660971164630122434300 723 176708930330666271859876746 724 185085015885255746880621052 725 193852115645795752984184554 726 203028206889569986197646484 727 212632080937520072186585650 728 222683379460186024851572558 729 233202632378520643600870281 730 244211297428606706709920642 731 255731801462210865864996645 732 267787583558210323920370995 733 280403140023083872114268991 734 293604071362025285843557776 735 307417131305664218954011531 736 321870277981032622582588666 737 336992727319136467572134169 738 352815008795455957133210724 739 369369023603738655757453136 740 386688105367749941220646435 741 404807083500032850651729108 742 423762349321394151918923525 743 443591925059596733749009901 744 464335535850798483634133318 745 486034684872448271784321313 746 508732731741838107613597770 747 532474974320122372524702644 748 557308734067567635805389647 749 583283445101886813536234873 750 610450747117966916191766805 751 638864582333908382360552351 752 668581296635294279311388874 753 699659745096778286894317749 754 732161402067670820574400190 755 766150476015982127183452328 756 801694029333610862568745904 757 838862103313805798709294274 758 877727848520950325159237558 759 918367660781873199488129833 760 960861323037560814483867973 761 1005292153304074193879893792 762 1051747159001957690209583758 763 1100317197924192833923664619 764 1151097146124113726578722224 765 1204186073016375022219511852 766 1259687423996378387111223999 767 1317709210896221493178038399 768 1378364210608578997366593230 769 1441770172223648126550503943 770 1508050033038752490738306503 771 1577332143815074048889593784 772 1649750503671651735806598654 773 1725445005022910006140640368 774 1804561688982956164492939405 775 1887253011677361609828817124 776 1973678121921532286407944740 777 2064003150743712843868724369 778 2158401513250589964731355221 779 2257054223353982965849636731 780 2360150221898687182164772690 781 2467886718753771981901716358 782 2580469549453004933593915548 783 2698113546994164480174751054 784 2821042929432312216467196744 785 2949491703928193388274444937 786 3083704087940340693022759146 787 3223934948277725160271629436 788 3370450258759473520427108746 789 3523527577258789108163781733 790 3683456542940343404363079231 791 3850539394533563994343408413 792 4025091510519029370421425657 793 4207441972141088280734052442 794 4397934150197476827913754420 795 4596926316595586652827468754 796 4804792281705797515062554306 797 5021922058584382849328863801 798 5248722555182613689484382380 799 5485618295704258477069978593 800 5733052172321422504456906520 801 5991486228508002426815714031 802 6261402475301701333080503977 803 6543303741858946450905280026 804 6837714561722963378455088871 805 7145182096283051986707098080 806 7466277096963606051213798966 807 7801594907743960700948994908 808 8151756509675604512522468030 809 8517409609130970421571752021 810 8899229771588828461969912417 811 9297921602834531195851263135 812 9714219979529959777862762681 813 10148891331187245215547988269 814 10602734975663191221223588558 815 11076584510377034355391136462 816 11571309261543787320061387075 817 12087815793808125625662158065 818 12627049482760689878061739057 819 13189996152918959195978864384 820 13777683783859651786576210025 821 14391184287298069419105851281 822 15031615358023124634594087055 823 15700142401714084441377197389 824 16397980542787591098996816075 825 17126396715550358417594261339 826 17886711842065410771034744286 827 18680303100276877491522982422 828 19508606286081561360311431975 829 20373118273183778133458314500 830 21275399574724765449983354277 831 22217077010838260632179405582 832 23199846486451169343993145389 833 24225475883821531494697777159 834 25295808074486832813101040658 835 26412764055483014097178751917 836 27578346214889968804237165712 837 28794641731961759722351366198 838 30063826117310982372086470288 839 31388166898835484452139879956 840 32770027459303858556350792805 841 34211871031752548278772278584 842 35716264859093977687647307544 843 37285884524590579748861388697 844 38923518460115987806848667395 845 40632072639400673752129294445 846 42414575463747094337180786216 847 44274182847997609942310572704 848 46214183514849300594196187834 849 48238004505931946889525415090 850 50349216918401212177548473763 851 52551541876147039010384557064 852 54848856745079917639394812898 853 57245201602333536237114016869 854 59744785969613964515539253168 855 62351995821331449988466085770 856 65071400878573831543609951314 857 67907762200418949875852860571 858 70866040084540107092698337135 859 73951402289532005957331745344 860 77169232591877674590168537300 861 80525139690988018278755879217 862 84024966476277979232856328456 863 87674799670795146675673853592 864 91480979866491345649258752099 865 95450111966823518214883915517 866 99589076052990565170686653322 867 103905038690755971019484291479 868 108405464695475636367939367494 869 113098129373644577851404467423 870 117991131259998859170817952725 871 123092905369958432777075789923 872 128412236987976529870072684144 873 133958276013169939669531013178 874 139740551884446204479331404858 875 145768989108216487062234766704 876 152053923412691097170490149769 877 158606118553696417431847039831 878 165436783797931931934295214171 879 172557592110602218633091537672 880 179980699075416049556058356670 881 187718762576041099642814423512 882 195784963269243383580949574952 883 204193025881123335512830172586 884 212957241359090878236182728209 885 222092489913497780851227597139 886 231614264984172822820073003005 887 241538698168481624527315172107 888 251882585148964518765460478419 889 262663412660090356154504988819 890 273899386535208029575034555059 891 285609460876378579895067645640 892 297813368391435715163322525036 893 310531651944349233813920506530 894 323785697366761254448562960374 895 337597767580427105501057911000 896 351991038082228660789452112102 897 366989633845435601723754684482 898 382618667692977386826261186841 899 398904280200653395819254511540 900 415873681190459054784114359068 901 433555192876539531087229249049 902 451978294728708525214022995295 903 471173670120985588372050791564 904 491173254835220446432862084360 905 512010287492584845146484405861 906 533719361988531136324395153006 907 556336482009740068071399057554 908 579899117714618242279047910845 909 604446264662056374189988828296 910 630018505076433611630379747344 911 656658071540248718776792340307 912 684408913209287275550344068534 913 713316764648893234122621619234 914 743429217393715213042975611046 915 774795794337240928934816278378 916 807468027061529837515792396149 917 841499536221802614337232040938 918 876946115104959930393838351039 919 913865816485680423486405060197 920 952319042908502961911588241254 921 992368640529229737341624405349 922 1034079996654109332431762905265 923 1077521141120571341397403379953 924 1122762851668802145076610691194 925 1169878763459173895733432730911 926 1218945482896482311379736991782 927 1270042705928112564209840420273 928 1323253340989653981276400179179 929 1378663636778122744608506412924 930 1436363315039845896899358321386 931 1496445708567209282036578481141 932 1559007904605896258842021455808 933 1624150893881942976244820886585 934 1691979725465930503404211092988 935 1762603667699924360130192596563 936 1836136375421380008668856710853 937 1912696063727159213943851074124 938 1992405688530070149968413754864 939 2075393134169954709485716040418 940 2161791408351324312330912515708 941 2251738844689892053427982283094 942 2345379313161090374436414544807 943 2442862438754801545567295086141 944 2544343828652090726779455853677 945 2649985308251720770267133432541 946 2759955166386673475403099782618 947 2874428410083806869907819971596 948 2993587029233173241168779707935 949 3117620271547411926979127046442 950 3246724928206047105940972852696 951 3381105630594468612010288121042 952 3520975158562887897616477403723 953 3666554760646647127956344299346 954 3818074486705953843294627805190 955 3975773533460423034845675028563 956 4139900603411771887815710359057 957 4310714277666637214536144920467 958 4488483403190813123215639900435 959 4673487495046245204241629444241 960 4866017154182911354694265199542 961 5066374501379277964399166412587 962 5274873627947390097986152236727 963 5491841063841846500452896046599 964 5717616263835974099255567726763 965 5952552112453464578853008302803 966 6197015448369619941842104641901 967 6451387609023188709970129903789 968 6716064996207615136996693067293 969 6991459663439386169435859771885 970 7277999925931103886207676498399 971 7576130994027952290703815090142 972 7886315630998429231248733029383 973 8209034836103596418058528748255 974 8544788553903729460741526707665 975 8894096410797147287955714747995 976 9257498479823236816318777813318 977 9635556074800288403768986027143 978 10028852574908795418824727334635 979 10437994280872373856676062872619 980 10863611303931504965592652837760 981 11306358488849924787366667758263 982 11766916372239763961801564982868 983 12245992177539511607834487445902 984 12744320848028628464246059620539 985 13262666119314202551196742814836 986 13801821632778520931079437712378 987 14362612091531863067120268395049 988 14945894460472306341153073884833 989 15552559212113915719970799351705 990 16183531619906475296861224617830 991 16839773100833956878604913208244 992 17522282609145324707635966069788 993 18232098083140097717852712338862 994 18970297947002453464660671148735 995 19738002669751617842096992225176 996 20536376383452971700767593586759 997 21366628562913781584556907787456 998 22230015769169865076825741898281 999 23127843459154899464880444624974 1000 24061467864032622473692149720708