0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 21 9 28 10 39 11 51 12 69 13 89 14 117 15 150 16 194 17 245 18 313 19 392 20 494 21 614 22 766 23 944 24 1168 25 1430 26 1754 27 2135 28 2601 29 3146 30 3810 31 4585 32 5519 33 6611 34 7917 35 9440 36 11253 37 13361 38 15856 39 18755 40 22169 41 26124 42 30766 43 36132 44 42401 45 49639 46 58063 47 67766 48 79027 49 91970 50 106942 51 124124 52 143940 53 166634 54 192745 55 222593 56 256843 57 295933 58 340682 59 391662 60 449903 61 516139 62 591645 63 677390 64 774938 65 885534 66 1011131 67 1153308 68 1314474 69 1496660 70 1702827 71 1935542 72 2198476 73 2494854 74 2829190 75 3205566 76 3629510 77 4106130 78 4642242 79 5244204 80 5920367 81 6678672 82 7529325 83 8482175 84 9549732 85 10744161 86 12080731 87 13574496 88 15244047 89 17107909 90 19188768 91 21509346 92 24097220 93 26980286 94 30192005 95 33766483 96 37744349 97 42167190 98 47084213 99 52546126 100 58612413 101 65344706 102 72814931 103 81097838 104 90280191 105 100452612 106 111719604 107 124190747 108 137991883 109 153255261 110 170132136 111 188782009 112 209386407 113 232137296 114 257252435 115 284962482 116 315528213 117 349226548 118 386369384 119 427288580 120 472356923 121 521971519 122 576577288 123 636649000 124 702717002 125 775348028 126 855173793 127 942869900 128 1039187814 129 1144932185 130 1260995921 131 1388336037 132 1528012644 133 1681162592 134 1849043010 135 2033003140 136 2234532138 137 2455229317 138 2696857260 139 2961309565 140 3250670139 141 3567178986 142 3913297450 143 4291672320 144 4705208320 145 5157029629 146 5650560742 147 6189486076 148 6777839066 149 7419960297 150 8120596573 151 8884856514 152 9718321117 153 10626997811 154 11617442505 155 12696712742 156 13872503472 157 15153098324 158 16547521139 159 18065486615 160 19717567936 161 21515147808 162 23470605158 163 25597265610 164 27909609966 165 30423226022 166 33155039623 167 36123269305 168 39347683882 169 42849559243 170 46651966258 171 50779732291 172 55259760974 173 60121000824 174 65394802155 175 71114892602 176 77317776329 177 84042720286 178 91332198447 179 99231892212 180 107791186906 181 117063187098 182 127105272550 183 137979133863 184 149751392300 185 162493661148 186 176283239244 187 191203200254 188 207343169943 189 224799451298 190 243675892660 191 264084056572 192 286144192364 193 309985453472 194 335746988494 195 363578218458 196 393640057291 197 426105261008 198 461159796461 199 499003270766 200 539850468142 201 583931876400 202 631495408556 203 682807043987 204 738152761020 205 797839307081 206 862196370169 207 931577502305 208 1006362554905 209 1086958781650 210 1173803574558 211 1267365769015 212 1368148720057 213 1476691845118 214 1593574077483 215 1719415685047 216 1854882152530 217 2000686312042 218 2157592710024 219 2326420100822 220 2508046352785 221 2703411360975 222 2913522565085 223 3139458335750 224 3382374183430 225 3643506692741 226 3924180501605 227 4225812865069 228 4549921507062 229 4898129895766 230 5272176080253 231 5673918784276 232 6105347342745 233 6568588732263 234 7065918751588 235 7599770110537 236 8172745013258 237 8787624459453 238 9447382396163 239 10155196401461 240 10914463608085 241 11728812948491 242 12602123074973 243 13538536386268 244 14542479181669 245 15618677714050 246 16772180864293 247 18008378480932 248 19333026892147 249 20752269846591 250 22272667202325 251 23901218818523 252 25645396824357 253 27513172838114 254 29513054263197 255 31654115282102 256 33946037662026 257 36399146022456 258 39024453716885 259 41833702914196 260 44839416186019 261 48054942036934 262 51494512881275 263 55173296729662 264 59107462350089 265 63314237883036 266 67811984070995 267 72620260699656 268 77759908861469 269 83253126224065 270 89123559441620 271 95396389347292 272 102098434751845 273 109258248825804 274 116906235644183 275 125074759169467 276 133798274099704 277 143113449004587 278 153059313210661 279 163677395868451 280 175011890781599 281 187109813388386 282 200021185708169 283 213799213423651 284 228500493364045 285 244185213180300 286 260917384032309 287 278765065634882 288 297800627175730 289 318101000801182 290 339747974134408 291 362828475681905 292 387434902672769 293 413665442266316 294 441624438918318 295 471422755681358 296 503178185779210 297 537015858850706 298 573068701908247 299 611477895927890 300 652393392024450 301 695974424370328 302 742390088076404 303 791819915178544 304 844454521405068 305 900496252734809 306 960159909120832 307 1023673469931988 308 1091278903607751 309 1163232981322121 310 1239808182506810 311 1321293607128600 312 1407995988221649 313 1500240714294443 314 1598372961255519 315 1702758837856800 316 1813786650729169 317 1931868187216451 318 2057440128867684 319 2190965487569152 320 2332935184544680 321 2483869657580234 322 2644320624419593 323 2814872880857154 324 2996146269623075 325 3188797691261481 326 3393523301929164 327 3611060761529865 328 3842191686372158 329 4087744161739262 330 4348595478337810 331 4625674939418288 332 4919966913123178 333 5232513967731606 334 5564420275465513 335 5916855113121780 336 6291056656931509 337 6688335889858952 338 7110080831431003 339 7557760897654375 340 8032931614439306 341 8537239481105805 342 9072427221475942 343 9640339207411134 344 10242927307512627 345 10882256933443671 346 11560513552580398 347 12280009426677636 348 13043190862163611 349 13852645718146060 350 14711111475987726 351 15621483602157301 352 16586824527407442 353 17610372959188506 354 18695553870651707 355 19845988867421528 356 21065507297381190 357 22358157788058594 358 23728220599902785 359 25180220462976100 360 26718940309747856 361 28349435553413391 362 30077049350706918 363 31907428479571414 364 33846540298353792 365 35900690397315255 366 38076541438458455 367 40381132773742983 368 42821901369276112 369 45406703603779081 370 48143838502234329 371 51042071950691318 372 54110662488448774 373 57359388200018790 374 60798575341089349 375 64439128196180489 376 68292560842336995 377 72371030291271526 378 76687371726853430 379 81255135283731752 380 86088625129765442 381 91202940270211700 382 96614017884733903 383 102338678586773874 384 108394674467706907 385 114800739285502478 386 121576641715534617 387 128743240992186375 388 136322545917334817 389 144337776532754397 390 152813429494600525 391 161775346413946283 392 171250786268280175 393 181268501113611160 394 191858816272795562 395 203053714194976312 396 214886923236918236 397 227394010524931530 398 240612480228977699 399 254581876370247612 400 269343891579518917 401 284942480889926114 402 301423982072651644 403 318837241560163900 404 337233747563562289 405 356667769388597317 406 377196504661038676 407 398880233425941148 408 421782480942370904 409 445970188096980178 410 471513891377218851 411 498487911285638532 412 526970551262835323 413 557044305959043652 414 588796081057059880 415 622317423444294535 416 657704764081952134 417 695059672326624071 418 734489124206973594 419 776105783369441019 420 820028297360725024 421 866381607919435272 422 915297278122232936 423 966913835015743966 424 1021377130768797469 425 1078840720937288021 426 1139466263078363842 427 1203423934267990072 428 1270892870976101190 429 1342061629816637165 430 1417128672858770263 431 1496302875983347849 432 1579804064219058547 433 1667863572511146985 434 1760724836124334048 435 1858644009104611134 436 1961890615286974797 437 2070748230251004320 438 2185515199016870120 439 2306505387864883142 440 2434048975400168416 441 2568493281232000256 442 2710203637741278466 443 2859564303300117028 444 3016979422794113343 445 3182874033812351674 446 3357695124761934062 447 3541912743281423466 448 3736021161645011287 449 3940540097552697622 450 4156015997464920203 451 4383023380908155989 452 4622166253412859214 453 4874079586553893228 454 5139430873293990778 455 5418921757160428404 456 5713289744034363918 457 6023309995158423128 458 6349797210766223522 459 6693607603032849741 460 7055640968419935992 461 7436842858230654908 462 7838206858168287146 463 8260776975852136850 464 8705650147861243849 465 9173978865423738104 466 9666973931156805563 467 10185907346170674171 468 10732115340839267557 469 11307001548777817950 470 11912040338298976910 471 12548780301150342270 472 13218847913846883649 473 13923951371706733658 474 14665884612025559696 475 15446531526847039657 476 16267870382975943123 477 17131978450089614961 478 18041036855898140423 479 18997335669665291218 480 20003279234445277162 481 21061391749863359412 482 22174323127312899578 483 23344855119979878620 484 24575907751202269326 485 25870546044236182604 486 27231987078698843042 487 28663607377502165377 488 30168950651452008699 489 31751735906159189068 490 33415865940491108900 491 35165436242146339892 492 37004744311796930187 493 38938299422425981598 494 40970832847701024466 495 43107308567177135862 496 45352934484754971788 497 47713174169492035727 498 50193759157982691789 499 52800701828855201171 500 55540308891619166738 501 58419195502022949823 502 61444300049412267115 503 64622899630043105052 504 67962626255359162234 505 71471483811173892712 506 75157865820574466669 507 79030574028688273889 508 83098837866241374233 509 87372334812489922614 510 91861211718897816029 511 96576107116837471048 512 101528174575495973149 513 106729107136240901316 514 112191162894824779635 515 117927191760974295012 516 123950663472361533652 517 130275696896131261468 518 136917090701062830038 519 143890355437538080212 520 151211747114968212518 521 158898302318259198357 522 166967874960078926180 523 175439174715354122248 524 184331807242457944062 525 193666316242847872606 526 203464227471939500661 527 213748094758842677586 528 224541548156751478857 529 235869344288056060537 530 247757419015719308577 531 260232942512057596098 532 273324376867017387551 533 287061536314853646301 534 301475650232716483175 535 316599428998566642627 536 332467132874287392471 537 349114644010746285305 538 366579541754049376725 539 384901181359975425798 540 404120776310308315076 541 424281484349259913157 542 445428497449378705764 543 467609135837401530450 544 490872946306409835000 545 515271804958178109216 546 540860024620440705774 547 567694467097651320041 548 595834660519851293660 549 625342921964278545734 550 656284485635861507700 551 688727636798790708931 552 722743851768617742450 553 758407944176257265632 554 795798217838582866800 555 834996626467943799085 556 876088940582616017831 557 919164921873401544911 558 964318505417969336951 559 1011647990023128682966 560 1061256237118664481252 561 1113250878510178608703 562 1167744533449246453224 563 1224855035358073715728 564 1284705668704508019660 565 1347425416397018592038 566 1413149218236160129627 567 1482018240827486481572 568 1554180159536447744439 569 1629789452928780312232 570 1709007710324577716916 571 1792003952951544389266 572 1878954969377226024857 573 1970045665751461153814 574 2065469431594711434341 575 2165428521713345457370 576 2270134455038010406718 577 2379808431020414583329 578 2494681764450140807016 579 2614996339385862406352 580 2741005083133467210039 581 2872972461029737212436 582 3011174993040822767145 583 3155901793004085358694 584 3307455131605627238502 585 3466151023998143906110 586 3632319843241340646851 587 3806306960552285522082 588 3988473413645272521746 589 4179196604238518911272 590 4378871026112638729345 591 4587909024895998038307 592 4806741591075930244683 593 5035819187517208851918 594 5275612613110174534626 595 5526613903945405330821 596 5789337273770915162918 597 6064320095254238716350 598 6352123923949948220853 599 6653335566631265335110 600 6968568196042746601487 601 7298462513880724120035 602 7643687964227775439385 603 8004943999408620020610 604 8382961400676890960847 605 8778503655874674263900 606 9192368396672452882142 607 9625388897720736283751 608 10078435640535459661443 609 10552417944653958574530 610 11048285669115594428836 611 11567030987026861449694 612 12109690236516015274856 613 12677345851078991409474 614 13271128372893155320283 615 13892218552363071511323 616 14541849537768497069976 617 15221309158563404203416 618 15931942306513861225157 619 16675153418532180367854 620 17452409065738709907024 621 18265240652943247469926 622 19115247233448974886859 623 20004098443733584543534 624 20933537563312256748664 625 21905384704730236669373 626 22921540139424130806301 627 23983987764825627157850 628 25094798718916506102182 629 26256135148070194622836 630 27470254134896606226074 631 28739511792425514469717 632 30066367531894298997014 633 31453388511016889546864 634 32903254270593319655098 635 34418761566923287767095 636 36002829408524755076597 637 37658504305256142570432 638 39388965739036697320850 639 41197531864951289896027 640 43087665452683771179961 641 45062980077809668905216 642 47127246573702405534300 643 49284399754389685225886 644 51538545419989640654586 645 53893967655935555771760 646 56355136438564664582272 647 58926715559223686430424 648 61613570880488621870112 649 64420778937672686920398 650 67353635900324136233915 651 70417666907992657920532 652 73618635796158977163394 653 76962555227801482371990 654 80455697247783092176951 655 84104604276824790373218 656 87916100563640943031026 657 91897304113400713347884 658 96055639112593997160443 659 100398848869977799192926 660 104935009295305001787037 661 109672542937145746613159 662 114620233603256661755391 663 119787241586574913960668 664 125183119522185496928366 665 130817828900248519118734 666 136701757262278996552061 667 142845736107829978627600 668 149261059541178438493024 669 155959503687295322149730 670 162953346909081645239120 671 170255390857562314059960 672 177878982389591323024125 673 185838036387364099791174 674 194147059517066603823693 675 202821174963770141033610 676 211876148182897527093338 677 221328413708408365442465 678 231195103061262379413199 679 241494073801590614734610 680 252243939771622620024854 681 263464102576343818767969 682 275174784352696056095129 683 287397061878122902408959 684 300152902073334759098165 685 313465198954227729797984 686 327357812092213730272664 687 341855606642357043504926 688 356984495003302364705961 689 372771480173205383692081 690 389244700870750455534013 691 406433478490664369602284 692 424368365968311105314797 693 443081198628386423258376 694 462605147098229257258609 695 482974772366822560765803 696 504226083076397782699001 697 526396595134247736778084 698 549525393738560379144183 699 573653197912925766574431 700 598822427650766705565220 701 625077273771948253508492 702 652463770600835822995891 703 681029871576258126235408 704 710825527911290009956587 705 741902770422156882730659 706 774315794653495123558025 707 808121049428809807325456 708 843377328963409275135030 709 880145868678945002240997 710 918490444867662979253861 711 958477478356587165764343 712 1000176142331409177744883 713 1043658474482263793720660 714 1088999493643738018429561 715 1136277321104185582308902 716 1185573306770243127196083 717 1236972160375517037089954 718 1290562087933934857521327 719 1346434933641709119340159 720 1404686327444134386904861 721 1465415838487308480423722 722 1528727134687940844294281 723 1594728148658735303007966 724 1663531250240759858416263 725 1735253425899035859633606 726 1810016465252415762876471 727 1887947155014178203804401 728 1969177480635579920334737 729 2053844835950551314811887 730 2142092241136573813695396 731 2234068569313364277077346 732 2329928782118954830051418 733 2429834174610039486231523 734 2533952629852610326130743 735 2642458883576945334699208 736 2755534799291431338016881 737 2873369654258566761852498 738 2996160436758267513290984 739 3124112155073353078577340 740 3257438158655319545389309 741 3396360471939228594616361 742 3541110141301322304289885 743 3691927595664746891833532 744 3849063021285207575177250 745 4012776751261289582179210 746 4183339670342392646462035 747 4361033635621374176967565 748 4546151913729104682150359 749 4738999635163625166190798 750 4939894266418732047168743 751 5149166100593750617954458 752 5367158767200562369383856 753 5594229761902455828961086 754 5830750996955994012250508 755 6077109373147293991642892 756 6333707374053217837129491 757 6600963683480013542005104 758 6879313826973701577253860 759 7169210838320528441924814 760 7471125952000403749244980 761 7785549322582410824248818 762 8112990772099111847679423 763 8453980566464863095836620 764 8809070222054234950876391 765 9178833343587633387986566 766 9563866494525573642212794 767 9964790101206767445091270 768 10382249392023256726119473 769 10816915372962462074353370 770 11269485840908063545003080 771 11740686436131423760355393 772 12231271735471568594091431 773 12742026387744940407201738 774 13273766292996997901167232 775 13827339827254612490073282 776 14403629114513943216258626 777 15003551347749313103836466 778 15628060160809556370860514 779 16278147053123422974393549 780 16954842869222153138193201 781 17659219335147061785624742 782 18392390653902470223873869 783 19155515162179018711445311 784 19949797050671280972041549 785 20776488150383653203636400 786 21636889787424215614354138 787 22532354708862085677305723 788 23464289082336826089606948 789 24434154572190506289159070 790 25443470495013892088207563 791 26493816057586967264126558 792 27586832680323248083624534 793 28724226409423288057694694 794 29907770421080997683746478 795 31139307621190098597062990 796 32420753344145859140839617 797 33754098154449304044221900 798 35141410754979192443452853 799 36584841005918090907435501 800 38086623058487965588440239 801 39649078607781418930374280 802 41274620269155561862189933 803 42965755082796615527692177 804 44725088151256796198964327 805 46555326414917327923071222 806 48459282570538366020164198 807 50439879138220936305805079 808 52500152682327358806120354 809 54643258192083882730609928 810 56872473627826061105275773 811 59191204639038558361280467 812 61602989460594407817037279 813 64111503993804848640075618 814 66720567079161877092469853 815 69434145967877824545679321 816 72256361999616201973087387 817 75191496494047490850325340 818 78243996864173737809723401 819 81418482959623796895093798 820 84719753648452911252574443 821 88152793646258236262316592 822 91722780601776943983400148 823 95435092448432858546022858 824 99295315031677426341131214 825 103309250022293115961733501 826 107482923126233752679038003 827 111822592601923261140744218 828 116334758096369115652965413 829 121026169811820261471305760 830 125903838015164503101369613 831 130975042902662261960856556 832 136247344833111374214675749 833 141728594942970035771648452 834 147426946157497582604289317 835 153350864612437996320259058 836 159509141501340855282429595 837 165910905364114813694545995 838 172565634833018375684230852 839 179483171852830820419916146 840 186673735392598458816165347 841 194147935666929966379951246 842 201916788885512481593187010 843 209991732550142140992495192 844 218384641319309473603819662 845 227107843461048629701293165 846 236174137915558383849279181 847 245596811989821350080303040 848 255389659707302669897857430 849 265567000836581490459270031 850 276143700623683126707906636 851 287135190253709286453278974 852 298557488068342232218159899 853 310427221566689809097342074 854 322761650217985135460621949 855 335578689115611811739929581 856 348896933503045503982637814 857 362735684203330566374801725 858 377114973984908591541468333 859 392055594897719412448166893 860 407579126614776969603472143 861 423707965815607353846594926 862 440465356649307706321196830 863 457875422316256631881400710 864 475963197808973851235721525 865 494754663853992092118240974 866 514276782098173632599352645 867 534557531584369141491758612 868 555625946562995319346287103 869 577512155687680155203825175 870 600247422644920508024297463 871 623864188269383731438229025 872 648396114198406102121755801 873 673878128121050667883663150 874 700346470679141989222184459 875 727838744079636666581507862 876 756393962479886481094414104 877 786052604209433278419507722 878 816856665894325637296570051 879 848849718552180516213919717 880 882076965728727534912597465 881 916585303748968208518344111 882 952423384158771764336897753 883 989641678435296737305503076 884 1028292545047503773348187043 885 1068430298950777723366108299 886 1110111283602753159961286900 887 1153393945590388216150586814 888 1198338911961621285204341739 889 1245009070358107924531905077 890 1293469652049053253018373595 891 1343788317969544852966022909 892 1396035247870553158014510348 893 1450283232691398855962468804 894 1506607770269509615722438487 895 1565087164506180820524400066 896 1625802628111356510700294736 897 1688838389054617103434009201 898 1754281800854159866757586996 899 1822223456840025894633252903 900 1892757308532745075813616971 901 1965980788283356466696249167 902 2041994936326019397734736788 903 2120904532399556869397356914 904 2202818232099894202717786743 905 2287848708130846123425701040 906 2376112796626715252214217090 907 2467731648726044468544248789 908 2562830887582290376337551615 909 2661540771003480893210484579 910 2763996359919788091868739144 911 2870337692884688375455298178 912 2980709966822723816926681497 913 3095263724244095429127835087 914 3214155047154166865815556477 915 3337545757893682891983290919 916 3465603627153895204447739877 917 3598502589419058080284418856 918 3736422966097721932031509901 919 3879551696613104343588895231 920 4028082577732400455685052685 921 4182216511424367746022510527 922 4342161761544761217154267538 923 4508134219659332662663298910 924 4680357680325052123809082922 925 4859064126161057479750473293 926 5044494023052533843631873000 927 5236896625842331219080900186 928 5436530294877626909084135112 929 5643662823791356976549873671 930 5858571778911495842531462874 931 6081544850704547522487952460 932 6312880217673881629747299464 933 6552886923147757621045508064 934 6801885265407127209330987698 935 7060207201618504465966428106 936 7328196766053482530307002137 937 7606210503092732265976376363 938 7894617915529721092244527256 939 8193801928706775573813572000 940 8504159371034702990458895401 941 8826101471465778347142937212 942 9160054374509763947975935313 943 9506459673402507885214152910 944 9865774962057883113556186662 945 10238474406455083595952480922 946 10625049336135955314789638510 947 11026008856509763809343139861 948 11441880482687004605572255401 949 11873210795588155526751738150 950 12320566121099121867163607552 951 12784533233071093146702074362 952 13265720080990140236379759620 953 13764756543169637948770625266 954 14282295206348084480450917575 955 14819012172604554975816244853 956 15375607894535514979026492896 957 15952808039668424063140531606 958 16551364385121184955607325063 959 17172055743550374289959351716 960 17815688921467095896955246059 961 18483099711035501435299032018 962 19175153916507360399641754391 963 19892748416484745033578375638 964 20636812263243828157239688473 965 21408307820394121922314000551 966 22208231940191186772588910533 967 23037617181864994365701655215 968 23897533072372783256519903677 969 24789087411032414829500310932 970 25713427619542042980005813792 971 26671742138942296225099643205 972 27665261875130338080477239174 973 28695261694588988854238026890 974 29763061972050844322943243105 975 30870030191874806069327959936 976 32017582604973014476195199823 977 33207185943187561711063972748 978 34440359193081016577598139156 979 35718675431170347634900437526 980 37043763722702834988960932960 981 38417311086142562210971831703 982 39841064525609722217141010797 983 41316833133589715165275783260 984 42846490266307605027059219219 985 44431975794243305008057453290 986 46075298430346724827426396829 987 47778538138597312537100313288 988 49543848625641910104027615580 989 51373459918335796754446481748 990 53269681030107276636339567514 991 55234902719163259696215965558 992 57271600341655159871465343656 993 59382336803028072084298695320 994 61569765610884879889162029202 995 63836634032807562182448579215 996 66185786362693922969292344284 997 68620167299286026388049665627 998 71142825440690319387572011633 999 73756916898815416960228458179 1000 76465709037785480223980910055