0 1 1 0 2 0 3 0 4 0 5 1 6 3 7 6 8 10 9 16 10 26 11 39 12 56 13 79 14 111 15 150 16 200 17 265 18 349 19 453 20 586 21 749 22 957 23 1209 24 1522 25 1903 26 2379 27 2950 28 3654 29 4500 30 5534 31 6771 32 8271 33 10063 34 12228 35 14799 36 17884 37 21543 38 25919 39 31087 40 37233 41 44477 42 53063 43 63149 44 75059 45 89014 46 105436 47 124631 48 147138 49 173388 50 204085 51 239800 52 281442 53 329783 54 386000 55 451119 56 526659 57 613988 58 715052 59 831651 60 966287 61 1121324 62 1299973 63 1505312 64 1741432 65 2012358 66 2323315 67 2679483 68 3087525 69 3554133 70 4087751 71 4696987 72 5392549 73 6185454 74 7089263 75 8118023 76 9288846 77 10619616 78 12131912 79 13848397 80 15796211 81 18004057 82 20505983 83 23338196 84 26543376 85 30167071 86 34262674 87 38887383 88 44107812 89 49995627 90 56633864 91 64112048 92 72533492 93 82009860 94 92669401 95 104651098 96 118113964 97 133230589 98 150197791 99 169229526 100 190568934 101 214480767 102 241265015 103 271248585 104 304800993 105 342325332 106 384275957 107 431149009 108 483502448 109 541945843 110 607163344 111 679902799 112 761001740 113 851376211 114 952050243 115 1064144027 116 1188907820 117 1327709644 118 1482073709 119 1653668229 120 1844349103 121 2056147592 122 2291320451 123 2552337778 124 2841940033 125 3163126882 126 3519222211 127 3913863813 128 4351078103 129 4835271371 130 5371314896 131 5964538999 132 6620830373 133 7346628994 134 8149040175 135 9035835549 136 10015581146 137 11097644481 138 12292341291 139 13610949354 140 15065877583 141 16670688654 142 18440292764 143 20390982199 144 22540653858 145 24908857420 146 27517052008 147 30388671383 148 33549418898 149 37027354600 150 40853234702 151 45060623970 152 49686287802 153 54770335701 154 60356672652 155 66493181467 156 73232243118 157 80630964127 158 88751778158 159 97662727909 160 107438158801 161 118159067760 162 129913903958 163 142798995250 164 156919474611 165 172389799566 166 189334821888 167 207890419410 168 228204732038 169 250438924400 170 274768616410 171 301384801324 172 330495498885 173 362326859166 174 397125074016 175 435157697092 176 476715856540 177 522115830443 178 571701604901 179 625846752365 180 684957390155 181 749474410999 182 819876907536 183 896684816738 184 980462879634 185 1071823773539 186 1171432691570 187 1280011041463 188 1398341744762 189 1527273598809 190 1667727403272 191 1820701099830 192 1987276855511 193 2168627104616 194 2366022740990 195 2580840212113 196 2814570986722 197 3068829877660 198 3345365982817 199 3646072431243 200 3972999028490 201 4328363657747 202 4714566885181 203 5134205287069 204 5590088316580 205 6085253858343 206 6622987707121 207 7206841705567 208 7840656225202 209 8528581301438 210 9275102574403 211 10085065884814 212 10963707204302 213 11916681235319 214 12950095924934 215 14070545698324 216 15285151247487 217 16601598106918 218 18028182515673 219 19573856160145 220 21248279008356 221 23061871172836 222 25025873759093 223 27152408924596 224 29454549940712 225 31946390695110 226 34643126321470 227 37561133581520 228 40718063626301 229 44132934883193 230 47826239744853 231 51820051837640 232 56138148669868 233 60806135437249 234 65851585969184 235 71304185513826 236 77195892662415 237 83561103924772 238 90436839667713 239 97862933702480 240 105882246721590 241 114540884551894 242 123888443076111 243 133978259343733 244 144867692495286 245 156618412526783 246 169296722390386 247 182973889852856 248 197726516680495 249 213636919819446 250 230793554363495 251 249291451167372 252 269232701251366 253 290726957914897 254 313891991305448 255 338854264247458 256 365749566869538 257 394723676654112 258 425933084408106 259 459545750447423 260 495741934759583 261 534715062907342 262 576672674945899 263 621837416508345 264 670448123058879 265 722760953689079 266 779050629560869 267 839611730365514 268 904760108315056 269 974834369943320 270 1050197489929791 271 1131238503937279 272 1218374349842994 273 1312051800814871 274 1412749565172104 275 1520980492849825 276 1637293969335810 277 1762278433055907 278 1896564103590220 279 2040825852573707 280 2195786311681127 281 2362219145336321 282 2540952590044303 283 2732873183546139 284 2938929793928155 285 3160137867147592 286 3397584011985363 287 3652430836069641 288 3925922161487963 289 4219388528585634 290 4534253126899420 291 4872038056470616 292 5234371069752200 293 5622992691949132 294 6039763882094031 295 6486674127077602 296 6965850144194338 297 7479565078509084 298 8030248384941538 299 8620496275463521 300 9253082936722072 301 9930972392401969 302 10657331232547305 303 11435542077820568 304 12269218019227917 305 13162217895056154 306 14118662665278444 307 15142952738855632 308 16239786535828090 309 17414180133145720 310 18671488299598784 311 20017426762575364 312 21458096037351289 313 23000006655485734 314 24650106150828885 315 26415807633564710 316 28305020340994383 317 30326181989841343 318 32488293351465028 319 34800954869439202 320 37274405776746419 321 39919565526998331 322 42748078035953031 323 45772358543576361 324 49005643635236179 325 52462044228826941 326 56156602112872587 327 60105349839664840 328 64325374609112839 329 68834885946072137 330 73653287861848611 331 78801255302664886 332 84300815636223386 333 90175434980547886 334 96450110192201021 335 103151466321733584 336 110307860425290993 337 117949491546112192 338 126108517833794571 339 134819180623299734 340 144117936527872035 341 154043597379574231 342 164637479165759234 343 175943559810420940 344 188008647052291160 345 200882556287681334 346 214618299743284472 347 229272286871215322 348 244904537455380567 349 261578907351142285 350 279363328483700301 351 298330063062756218 352 318555973788327207 353 340122810048575550 354 363117512048108122 355 387632532919027338 356 413766180933340473 357 441622981929356543 358 471314064268396884 359 502957566505998123 360 536679070310689172 361 572612058898035608 362 610898403751882148 363 651688879997205002 364 695143713458944072 365 741433159884079714 366 790738119649409344 367 843250788562526451 368 899175348396086361 369 958728697912336053 370 1022141228367343365 371 1089657644424397783 372 1161537834849960840 373 1238057794119123074 374 1319510599727471484 375 1406207446561482031 376 1498478743590579051 377 1596675274490754759 378 1701169427975811472 379 1812356499739470896 380 1930656072350463747 381 2056513475336631738 382 2190401332423763062 383 2332821198543890266 384 2484305294265416065 385 2645418340688761581 386 2816759503217940670 387 2998964447736450068 388 3192707518433530696 389 3398704041358158144 390 3617712763867602277 391 3850538434667427038 392 4098034535626592627 393 4361106170762281948 394 4640713124699621347 395 4937873096788189485 396 5253665124416972967 397 5589233202595402291 398 5945790114707872398 399 6324621482504292121 400 6727090051741039693 401 7154640222653940087 402 7608802843339877030 403 8091200276484463340 404 8603551759348652815 405 9147679068859115345 406 9725512513742019467 407 10339097267123944977 408 10990600063775924709 409 11682316277192315494 410 12416677403151188091 411 13196258966925433409 412 14023788883518845047 413 14902156290309946669 414 15834420884488185460 415 16823822787139233232 416 17873792969689873673 417 18987964267331662224 418 20170183018805931321 419 21424521360255633981 420 22755290216580022884 421 24167053021441361585 422 25664640213837712468 423 27253164546230419357 424 28938037257084795761 425 30724985147095048706 426 32620068617410229791 427 34629700713903573534 428 36760667241831524905 429 39020148000237257256 430 41415739207102355964 431 43955477170518114119 432 46647863284229265519 433 49501890409405148242 434 52527070729108238127 435 55733465144636284173 436 59131714309169616158 437 62733071376043076726 438 66549436566966294873 439 70593393646562133015 440 74878248419470883717 441 79418069346443399715 442 84227730407729497251 443 89322956321353643136 444 94720370257893469278 445 100437544171752845060 446 106493051905239116035 447 112906525199196100806 448 119698712782720203376 449 126891542690981415421 450 134508188001572921235 451 142573136155347401622 452 151112262071917311067 453 160152905244553712972 454 169723951046458038350 455 179855916453958264978 456 190581040442651928393 457 201933379285114685987 458 213948907032733066488 459 226665621435831342914 460 240123655613925189419 461 254365395758574197312 462 269435605212954991793 463 285381555241961983608 464 302253162872576633914 465 320103136152993287848 466 338987127249525429851 467 358963893768162873914 468 380095468763120595752 469 402447339861711472433 470 426088638015652410685 471 451092336355096097130 472 477535459708164112852 473 505499305314204626815 474 535069675351607259377 475 566337121865805596923 476 599397204782301850163 477 634350763653787025816 478 671304203896731804463 479 710369798236628235235 480 751666004194993122757 481 795317798414758229344 482 841457028742823646617 483 890222784951928085451 484 941761789114997695203 485 996228806608573408158 486 1053787078862455343640 487 1114608778936426481374 488 1178875491155735799765 489 1246778716001272916782 490 1318520401612270230329 491 1394313503224447814044 492 1474382572040363950226 493 1558964374994977803265 494 1648308547066172435847 495 1742678277747760978263 496 1842351033503159888530 497 1947619317987658061069 498 2058791472042884898620 499 2176192515439287458681 500 2300165032574323992067 501 2431070104309287324914 502 2569288288377098286317 503 2715220650772245310255 504 2869289850802400659028 505 3031941282464413129723 506 3203644275096202066988 507 3384893356244349841313 508 3576209579998154650639 509 3778141924035171534077 510 3991268758958164115252 511 4216199393504640095432 512 4453575699570940944298 513 4704073821002175838975 514 4968405970488126316686 515 5247322318923878790885 516 5541612982013113933031 517 5852110108921301657936 518 6179690078238084804891 519 6525275806549652785004 520 6889839175409542382516 521 7274403582551733374213 522 7680046623716094329409 523 8107902911527474121001 524 8559167038437716733001 525 9035096690829005912041 526 9537015921990240018376 527 10066318591787500103422 528 10624471981512075017529 529 11213020592521695108376 530 11833590138006300413201 531 12487891737367521800439 532 13177726323474524609084 533 13904989273245567331786 534 14671675272840783229244 535 15479883428970761065726 536 16331822638729701490563 537 17229817230617210717357 538 18176312890390861431790 539 19173882885687454480862 540 20225234604409151262921 541 21333216422211708567297 542 22500824915577356162190 543 23731212437346370135050 544 25027695072821279143096 545 26393760995005382964828 546 27833079238879849382346 547 29349508915133986371499 548 30947108885217475098530 549 32630147920163234057550 550 34403115367205050939799 551 36270732348871285125389 552 38237963520943177234170 553 40310029416409244583736 554 42492419404397720869212 555 44790905293907018005738 556 47211555614160398036941 557 49760750604354432753978 558 52445197947746313623998 559 55271949286085137712544 560 58248417552751868046558 561 61382395164161775315042 562 64682073111542943376998 563 68156060996536236168717 564 71813408056839596200102 565 75663625229609055440167 566 79716708303343130518127 567 83983162210640879998837 568 88474026517495817977762 569 93200902166643654184088 570 98175979536033971308881 571 103412067875563710988938 572 108922626189067392952518 573 114721795630860408654970 574 120824433490320564233599 575 127246148840551966558771 576 134003339931725153593866 577 141113233412529912742950 578 148593925468119890194003 579 156464424966082817444446 580 164744698707340387580615 581 173455718882380096091621 582 182619512839056823916255 583 192259215272078129522643 584 202399122950629095576534 585 213064752104884207156477 586 224282898599046831030977 587 236081701023305130942266 588 248490706844586261410177 589 261540941761240642262027 590 275264982414934173202954 591 289697032618827122971282 592 304873003269975366028081 593 320830596120295386607104 594 337609391590065169557211 595 355250940815002702554458 596 373798862128436852705697 597 393298942187883251153309 598 413799241966727832974287 599 435350207840317348266259 600 458004788008144308549829 601 481818554503286362919945 602 506849831053734861478073 603 533159827070679866275184 604 560812778053476538345613 605 589876092712502332460053 606 620420507127059714303536 607 652520246268116112053347 608 686253193233019826876641 609 721701066553229757375639 610 758949605954969709101875 611 798088766967999186002919 612 839212924798226411056921 613 882421087896683264550300 614 927817121679723721845918 615 975509982873756796921622 616 1025613964982134990449391 617 1078248955392080004470885 618 1133540704665979618902753 619 1191621108583631746906235 620 1252628503530795506436988 621 1316707975853817969916633 622 1384011685831426958554949 623 1454699206941558115137744 624 1528937881135168275059405 625 1606903190858354689124396 626 1688779148601189609512752 627 1774758704783877366654007 628 1865044174831202682772550 629 1959847686321528964665507 630 2059391647140527228525455 631 2163909235608484556358399 632 2273644913597837330077104 633 2388854963699932382731948 634 2509808051552031608078499 635 2636785814481962651215037 636 2770083477684418110391072 637 2910010499193691843298961 638 3056891244979232231858416 639 3211065695545980277244678 640 3372890185488482409680912 641 3542738177508596708703766 642 3721001072479541451504284 643 3908089057205582486664820 644 4104431991606013700452985 645 4310480337124871462072818 646 4526706128254173781040163 647 4753603989138067267822809 648 4991692197319220372386351 649 5241513796775816319679505 650 5503637762499727151302889 651 5778660218961559003719369 652 6067205714919484306339326 653 6369928557132709817138713 654 6687514205661440172549429 655 7020680733548749464949654 656 7370180353811425547657904 657 7736801016790889035128045 658 8121368081058512888502813 659 8524746061205131302390705 660 8947840456000332817669416 661 9391599660555044587637235 662 9857016966290401433255308 663 10345132652677367520052387 664 10857036174895938656578999 665 11393868451739000294448638 666 11956824258286445517625173 667 12547154728067493595497741 668 13166169969647255482976065 669 13815241802783448943201840 670 14495806619536377005375093 671 15209368375944215483237661 672 15957501720133631304226382 673 16741855262985451980942779 674 17564154997755650263617106 675 18426207875324210441990726 676 19329905542049511423194917 677 20277228247502764885896364 678 21270248929688765106873600 679 22311137485682880566291353 680 23402165235974892374949854 681 24545709591163085124242051 682 25744258930034131533258937 683 27000417698448800353549409 684 28316911738879831363620938 685 29696593860867277871600837 686 31142449663120060247015904 687 32657603618448918933400165 688 34245325433219728719768915 689 35909036693513349075720188 690 37652317810725762600760661 691 39478915279883795756618808 692 41392749264546866860888889 693 43397921522754943172588257 694 45498723689129703063644910 695 47699645928878027716134727 696 50005385980149860746057600 697 52420858601901549459653965 698 54951205445179608281714505 699 57601805366500810491214431 700 60378285202834474611024064 701 63286531028521032840980914 702 66332699915362724119976077 703 69523232218023552371147701 704 72864864407855341219965176 705 76364642479247406973527700 706 80029935953661656574118918 707 83868452507581852374817940 708 87888253251761884175125514 709 92097768690318501305948175 710 96505815389469697877045259 711 101121613386982294887574991 712 105954804374756131323434511 713 111015470688345108146845602 714 116314155138696524440179102 715 121861881722882938654955434 716 127670177252209281782735809 717 133751093937700984130076571 718 140117232974725477106755536 719 146781769170263852819568788 720 153758476658245881594401778 721 161061755750279477635529945 722 168706660971164630122434296 723 176708930330666271859876744 724 185085015885255746880621048 725 193852115645795752984184550 726 203028206889569986197646473 727 212632080937520072186585649 728 222683379460186024851572537 729 233202632378520643600870270 730 244211297428606706709920637 731 255731801462210865864996643 732 267787583558210323920370984 733 280403140023083872114268990 734 293604071362025285843557774 735 307417131305664218954011520 736 321870277981032622582588647 737 336992727319136467572134167 738 352815008795455957133210713 739 369369023603738655757453135 740 386688105367749941220646424 741 404807083500032850651729103 742 423762349321394151918923520 743 443591925059596733749009900 744 464335535850798483634133297 745 486034684872448271784321311 746 508732731741838107613597768 747 532474974320122372524702640 748 557308734067567635805389636 749 583283445101886813536234871 750 610450747117966916191766784 751 638864582333908382360552350 752 668581296635294279311388862 753 699659745096778286894317747 754 732161402067670820574400185 755 766150476015982127183452326 756 801694029333610862568745852 757 838862103313805798709294273 758 877727848520950325159237556 759 918367660781873199488129828 760 960861323037560814483867952 761 1005292153304074193879893791 762 1051747159001957690209583753 763 1100317197924192833923664617 764 1151097146124113726578722220 765 1204186073016375022219511841 766 1259687423996378387111223997 767 1317709210896221493178038397 768 1378364210608578997366593163 769 1441770172223648126550503942 770 1508050033038752490738306488 771 1577332143815074048889593782 772 1649750503671651735806598650 773 1725445005022910006140640367 774 1804561688982956164492939394 775 1887253011677361609828817120 776 1973678121921532286407944733 777 2064003150743712843868724364 778 2158401513250589964731355219 779 2257054223353982965849636729 780 2360150221898687182164772654 781 2467886718753771981901716356 782 2580469549453004933593915543 783 2698113546994164480174751047 784 2821042929432312216467196715 785 2949491703928193388274444935 786 3083704087940340693022759141 787 3223934948277725160271629435 788 3370450258759473520427108742 789 3523527577258789108163781731 790 3683456542940343404363079226 791 3850539394533563994343408411 792 4025091510519029370421425605 793 4207441972141088280734052440 794 4397934150197476827913754418 795 4596926316595586652827468749 796 4804792281705797515062554302 797 5021922058584382849328863800 798 5248722555182613689484382365 799 5485618295704258477069978591 800 5733052172321422504456906473 801 5991486228508002426815714027 802 6261402475301701333080503975 803 6543303741858946450905280024 804 6837714561722963378455088860 805 7145182096283051986707098075 806 7466277096963606051213798961 807 7801594907743960700948994906 808 8151756509675604512522468023 809 8517409609130970421571752020 810 8899229771588828461969912379 811 9297921602834531195851263134 812 9714219979529959777862762670 813 10148891331187245215547988267 814 10602734975663191221223588553 815 11076584510377034355391136460 816 11571309261543787320061387037 817 12087815793808125625662158063 818 12627049482760689878061739055 819 13189996152918959195978864373 820 13777683783859651786576210014 821 14391184287298069419105851280 822 15031615358023124634594087050 823 15700142401714084441377197388 824 16397980542787591098996816068 825 17126396715550358417594261328 826 17886711842065410771034744281 827 18680303100276877491522982421 828 19508606286081561360311431949 829 20373118273183778133458314499 830 21275399574724765449983354272 831 22217077010838260632179405580 832 23199846486451169343993145359 833 24225475883821531494697777155 834 25295808074486832813101040653 835 26412764055483014097178751915 836 27578346214889968804237165701 837 28794641731961759722351366191 838 30063826117310982372086470286 839 31388166898835484452139879955 840 32770027459303858556350792731 841 34211871031752548278772278582 842 35716264859093977687647307542 843 37285884524590579748861388695 844 38923518460115987806848667391 845 40632072639400673752129294441 846 42414575463747094337180786205 847 44274182847997609942310572700 848 46214183514849300594196187822 849 48238004505931946889525415088 850 50349216918401212177548473752 851 52551541876147039010384557062 852 54848856745079917639394812887 853 57245201602333536237114016868 854 59744785969613964515539253163 855 62351995821331449988466085759 856 65071400878573831543609951307 857 67907762200418949875852860570 858 70866040084540107092698337120 859 73951402289532005957331745343 860 77169232591877674590168537289 861 80525139690988018278755879212 862 84024966476277979232856328454 863 87674799670795146675673853591 864 91480979866491345649258752002 865 95450111966823518214883915515 866 99589076052990565170686653320 867 103905038690755971019484291475 868 108405464695475636367939367483 869 113098129373644577851404467421 870 117991131259998859170817952710 871 123092905369958432777075789921 872 128412236987976529870072684137 873 133958276013169939669531013174 874 139740551884446204479331404853 875 145768989108216487062234766697 876 152053923412691097170490149758 877 158606118553696417431847039830 878 165436783797931931934295214169 879 172557592110602218633091537670 880 179980699075416049556058356632 881 187718762576041099642814423511 882 195784963269243383580949574926 883 204193025881123335512830172585 884 212957241359090878236182728198 885 222092489913497780851227597134 886 231614264984172822820073003003 887 241538698168481624527315172106 888 251882585148964518765460478398 889 262663412660090356154504988817 890 273899386535208029575034555054 891 285609460876378579895067645628 892 297813368391435715163322525032 893 310531651944349233813920506528 894 323785697366761254448562960369 895 337597767580427105501057910998 896 351991038082228660789452112057 897 366989633845435601723754684477 898 382618667692977386826261186839 899 398904280200653395819254511538 900 415873681190459054784114359002 901 433555192876539531087229249047 902 451978294728708525214022995290 903 471173670120985588372050791559 904 491173254835220446432862084353 905 512010287492584845146484405859 906 533719361988531136324395153001 907 556336482009740068071399057553 908 579899117714618242279047910841 909 604446264662056374189988828292 910 630018505076433611630379747329 911 656658071540248718776792340306 912 684408913209287275550344068496 913 713316764648893234122621619232 914 743429217393715213042975611044 915 774795794337240928934816278373 916 807468027061529837515792396145 917 841499536221802614337232040936 918 876946115104959930393838351018 919 913865816485680423486405060196 920 952319042908502961911588241233 921 992368640529229737341624405347 922 1034079996654109332431762905263 923 1077521141120571341397403379951 924 1122762851668802145076610691158 925 1169878763459173895733432730907 926 1218945482896482311379736991780 927 1270042705928112564209840420269 928 1323253340989653981276400179160 929 1378663636778122744608506412923 930 1436363315039845896899358321371 931 1496445708567209282036578481137 932 1559007904605896258842021455804 933 1624150893881942976244820886583 934 1691979725465930503404211092986 935 1762603667699924360130192596558 936 1836136375421380008668856710801 937 1912696063727159213943851074123 938 1992405688530070149968413754859 939 2075393134169954709485716040416 940 2161791408351324312330912515697 941 2251738844689892053427982283093 942 2345379313161090374436414544802 943 2442862438754801545567295086139 944 2544343828652090726779455853665 945 2649985308251720770267133432520 946 2759955166386673475403099782613 947 2874428410083806869907819971595 948 2993587029233173241168779707924 949 3117620271547411926979127046440 950 3246724928206047105940972852685 951 3381105630594468612010288121040 952 3520975158562887897616477403702 953 3666554760646647127956344299345 954 3818074486705953843294627805179 955 3975773533460423034845675028561 956 4139900603411771887815710359053 957 4310714277666637214536144920462 958 4488483403190813123215639900433 959 4673487495046245204241629444239 960 4866017154182911354694265199437 961 5066374501379277964399166412585 962 5274873627947390097986152236722 963 5491841063841846500452896046595 964 5717616263835974099255567726759 965 5952552112453464578853008302801 966 6197015448369619941842104641886 967 6451387609023188709970129903788 968 6716064996207615136996693067277 969 6991459663439386169435859771880 970 7277999925931103886207676498394 971 7576130994027952290703815090141 972 7886315630998429231248733029336 973 8209034836103596418058528748253 974 8544788553903729460741526707663 975 8894096410797147287955714747984 976 9257498479823236816318777813306 977 9635556074800288403768986027142 978 10028852574908795418824727334630 979 10437994280872373856676062872617 980 10863611303931504965592652837734 981 11306358488849924787366667758259 982 11766916372239763961801564982866 983 12245992177539511607834487445901 984 12744320848028628464246059620518 985 13262666119314202551196742814834 986 13801821632778520931079437712373 987 14362612091531863067120268395044 988 14945894460472306341153073884822 989 15552559212113915719970799351703 990 16183531619906475296861224617794 991 16839773100833956878604913208243 992 17522282609145324707635966069769 993 18232098083140097717852712338860 994 18970297947002453464660671148730 995 19738002669751617842096992225174 996 20536376383452971700767593586748 997 21366628562913781584556907787455 998 22230015769169865076825741898279 999 23127843459154899464880444624967 1000 24061467864032622473692149720677