1 1 2 15 3 111 4 561 5 2211 6 7293 7 21021 8 54483 9 129558 10 286858 11 598026 12 1184118 13 2242266 14 4083366 15 7184166 16 12257850 17 20348031 18 32951985 19 52179985 20 80958735 21 123288165 22 184562235 23 271965915 24 394962165 25 565884540 26 800652996 27 1119632580 28 1548656956 29 2120241156 30 2875010556 31 3863375868 32 5147486916 33 6803501133 34 8924206083 35 11622038883 36 15032549181 37 19318356343 38 24673655721 39 31329333321 40 39558752871 41 49684284210 42 62084647086 43 77203149870 44 95556908370 45 117747135870 46 144470601730 47 176532362370 48 214859875230 49 260518613355 50 314729305605 51 378886935141 52 454581636795 53 543621642201 54 648058430151 55 770214248551 56 912712183593 57 1078508961336 58 1270930676808 59 1493711656008 60 1751036666808 61 2047586705736 62 2388588598968 63 2779868667576 64 3227910719176 65 3739918640601 66 4323883879095 67 4988658112791 68 5744031424905 69 6600816310155 70 7570937856405 71 8667530459445 72 9905041444155 73 11299341981070 74 12867845703570 75 14629635447570 76 16605598552686 77 18818571181410 78 21293492130846 79 24057566630046 80 27140440634946 81 30574386152343 82 34394498144281 83 38638903584633 84 43348983260583 85 48569606933133 86 54349382492691 87 60740919768243 88 67801109671581 89 75591419381556 90 84178204297356 91 93633037514380 92 104033057601396 93 115461335483340 94 128007261260340 95 141766951820340 96 156843680130060 97 173348327116965 98 191399857083435 99 211125817623435 100 232662865041685 101 256157316305631 102 281765728591425 103 309655507516641 104 340005545184591 105 373006889197866 106 408863443832118 107 447792704595126 108 490026527430858 109 535811933863558 110 585411953412858 111 639106504647546 112 697193316282918 113 759988889764611 114 827829504820461 115 901072269501261 116 980096216271315 117 1065303445750401 118 1157120319750175 119 1255998705290175 120 1362417271321425 121 1476882839929200 122 1599931793830800 123 1732131542029200 124 1874082045529200 125 2026417405069200 126 2189807512868976 127 2364959770441840 128 2552620874568336 129 2753578673578161 130 2968664096137311 131 3198753154788543 132 3444769026545121 133 3707684212890483 134 3988522781589933 135 4288362692774733 136 4608338211814051 137 4949642411546118 138 5313529766496666 139 5701318841770266 140 6114395079358566 141 6554213684668650 142 7022302616134806 143 7520265680837910 144 8049785739118410 145 8612628021231535 146 9210643559156865 147 9845772736738785 148 10520048961399615 149 11235602460733365 150 11994664207355115 151 12799569975448971 152 13652764532526405 153 14556805969976556 154 15514370176060756 155 16528255455075156 156 17601387296477868 157 18736823297850516 158 19937758245638508 159 21207529357689708 160 22549621691687508 161 23967673723651581 162 25465483100757843 163 27047012572808371 164 28716396106762221 165 30477945188819271 166 32336155318631385 167 34295712700298361 168 36361501134890295 169 38538609119323170 170 40832337156500670 171 43248205281722430 172 45791960810447170 173 48469586312588430 174 51287307818610930 175 54251603262786930 176 57369211169064366 177 60647139585091995 178 64092675270041301 179 67713393141960501 180 71517165990492651 181 75512174460887593 182 79706917315336311 183 84110221977756183 184 88731255368256633 185 93579535033616808 186 98664940580210136 187 103997725415914968 188 109588528807655976 189 115448388261327576 190 121588752230958376 191 128021493164084520 192 134758920890409816 193 141813796360941705 194 149199345744904455 195 156929274891844455 196 165017784166457145 197 173479583663780955 198 182329908812520645 199 191584536374380645 200 201259800847408395 201 211372611281468286 202 221940468514088610 203 232981482835046946 204 244514392088183646 205 256558580219058546 206 269134096277192718 207 282261673881765006 208 295962751159762258 209 310259491165712583 210 325174802792262633 211 340732362180992841 212 356956634642998743 213 373872897098901981 214 391507261048091331 215 409886696077132131 216 429039053917421805 217 448993093062309796 218 469778503954042140 219 491425934751034140 220 513967017686119140 221 537434396026567260 222 561861751646815140 223 587283833224996260 224 613736485074511260 225 641256676622028885 226 669882532543460731 227 699653363569606875 228 730609697973324741 229 762793313750230191 230 796247271505097841 231 831015948056286993 232 867145070770680351 233 904681752641784858 234 943674528123807558 235 984173389734684358 236 1026229825441205946 237 1069896856839552918 238 1115229078144721386 239 1162282696002490986 240 1211115570137759286 241 1261787254853240115 242 1314359041392698301 243 1368894001183069725 244 1425457029969993475 245 1484114892861462225 246 1544936270294477775 247 1607991804939780975 248 1673354149559909025 249 1741098015836018400 250 1811300224179098400 251 1884039754541388576 252 1959397798244003040 253 2037457810836955936 254 2118305566007975136 255 2202029210556685536 256 2288719320450939168 257 2378468957982266721 258 2471373730037623983 259 2567531847504807183 260 2667044185829113233 261 2770014346739024451 262 2876548721158902493 263 2986756553326882941 264 3100750006136370291 265 3218644227719742966 266 3340557419293089450 267 3466610904281009706 268 3596929198740730710 269 3731640083105001210 270 3870874675263448710 271 4014767505002301190 272 4163456589822597210 273 4317083512157230815 274 4475793498007402065 275 4639735497019270065 276 4809062264021833071 277 4983930442047289605 278 5164500646855365531 279 5350937552983324731 280 5543409981343615381 281 5742090988391339868 282 5947157956883974116 283 6158792688256001508 284 6377181496631367708 285 6602515304496905508 286 6834989740060123356 287 7074805236314997468 288 7322167131839655396 289 7577285773350088621 290 7840376620034283171 291 8111660349691410435 292 8391362966700975261 293 8679715911847075095 294 8976956174023182345 295 9283326403843122345 296 9599075029184181255 297 9924456372688541970 298 10259730771249511630 299 10605164697509271630 300 10961030883395150130 301 11327608445721687966 302 11705183013886041570 303 12094046859684541026 304 12494499029278497726 305 12906845477337634251 306 13331399203389789093 307 13768480390405830661 308 14218416545648998683 309 14681542643818176633 310 15158201272514886183 311 15648742780064083911 312 16153525425719131593 313 16672915532281604376 314 17207287641166895976 315 17757024669946876776 316 18322518072401159320 317 18904168001108826216 318 19502383472612777880 319 20117582535189161880 320 20750192439254651880 321 21400649810444652345 322 22069400825395815255 323 22756901390266567095 324 23463617322029658345 325 24190024532571063595 326 24936609215629878261 327 25703868036614177685 328 26492308325328126171 329 27302448271645947246 330 28134817124168692146 331 28989955391900071218 332 29868415048977942606 333 30770759742498384258 334 31697565003469608958 335 32649418460933317758 336 33626920059291424866 337 34630682278876426743 338 35661330359804029881 339 36719502529146995481 340 37805850231469505031 341 38921038362761698605 342 40065745507814387571 343 41240664181074295315 344 42446501071020533565 345 43683977288103377940 346 44953828616286764460 347 46256805768236288940 348 47593674644194853460 349 48965216594588468460 350 50372228686405085460 351 51815523973389703956 352 53295931770099366700 353 54814297929862030341 354 56371485126683673291 355 57968373141148379691 356 59605859150356517493 357 61284858021946509951 358 63006302612246083233 359 64771144068599258433 360 66580352135915743983 361 68434915467489774346 362 70335841940135832918 363 72284158973689091286 364 74280913854918793386 365 76327174065903211686 366 78424027616915203290 367 80572583383867796826 368 82773971450369646150 369 85029343454440594275 370 87339872939938000525 371 89706755712744895725 372 92131210201771444275 373 94614477824821608225 374 97157823359377326975 375 99762535318352946975 376 102429926330873058801 377 105161333528127324240 378 107958118934356303536 379 110821669863022722736 380 113753399318223053136 381 116754746401394709168 382 119827176723374607696 383 122972182821865270608 384 126191284584365093808 385 129486029676619849233 386 132857993976652932351 387 136308782014432315743 388 139840027417232619841 389 143453393360751164691 390 147150573026037321741 391 150933290062294942125 392 154803299055618097731 393 158762386003720833510 394 162812368796722094010 395 166955097704047454010 396 171192455867509752390 397 175526359800631200010 398 179958759894270006390 399 184491640928615046390 400 189127022591612566890 401 193866960003889414671 402 198713544250237750305 403 203668902917726698881 404 208735200640506876831 405 213914639651374224981 406 219209460340160071243 407 224621941819014842091 408 230154402494653340133 409 235809200647630005708 410 241588735018713083508 411 247495445402427120756 412 253531813247833731468 413 259700362266621071796 414 266003659048572984396 415 272444313684489285196 416 279024980396629183860 417 285748358176750349661 418 292617191431816657395 419 299634270637448173395 420 306802432999187469645 421 314124563121656884455 422 321603593685681881145 423 329242506133456191705 424 337044331361824970455 425 345012150423762723330 426 353149095238123321566 427 361458349307739954270 428 369943148445953422626 429 378606781511647729326 430 387452591152872470226 431 396483974559132091218 432 405704384222422631886 433 415117328707097138683 434 424726373428641494133 435 434535141441442974933 436 444547314235634420811 437 454766632543097467593 438 465196897152708872151 439 475841969734914533751 440 486705773675716395801 441 497792294920157994120 442 509105582825395002616 443 520649751023437714680 444 532428978293652988680 445 544447509445113778680 446 556709656208884966920 447 569219798140334812680 448 581982383531561932920 449 595001930334028333545 450 608283027091489616295 451 621830333883314095111 452 635648583278283167385 453 649742581298965899771 454 664117208396761405221 455 678777420437703207621 456 693728249699120412843 457 708974805877251130206 458 724522277105904216258 459 740375930986266043458 460 756541115627949629758 461 773023260701384101266 462 789827878501643099118 463 806960565023811383406 464 824427001049989531506 465 842232953248037275431 466 860384275282156672905 467 878886908935416959721 468 897746885244323586615 469 916970325645534602365 470 936563443134828206115 471 956532543438425956035 472 976884026196776788365 473 997624386160907670660 474 1018760214401447385660 475 1040298199530430617660 476 1062245128935990191556 477 1084607890030045995900 478 1107393471509099805316 479 1130608964628245904516 480 1154261564488508105916 481 1178358571337614445493 482 1202907391884321537051 483 1227915540626401263483 484 1253390641192403184933 485 1279340427697306747983 486 1305772746112178087121 487 1332695555647946919793 488 1360116930153419749311 489 1388045059527646305786 490 1416488251146756874086 491 1445454931305388879590 492 1474953646672821827226 493 1504993065763940416950 494 1535581980425146389450 495 1566729307335340389450 496 1598444089522095870550 497 1630735497893147805075 498 1663612832783319704925 499 1697085525517013204925 500 1731163139986385208675 501 1765855374245338348401 502 1801172062119451264815 503 1837123174831975970511 504 1873718822646030320961 505 1910969256523114380736 506 1948884869798080239168 507 1987476199870685599296 508 2026753929913862236608 509 2066728890598831199808 510 2107412061837197404608 511 2148814574540157053376 512 2190947712394952098368 513 2233822913658706754241 514 2277451772969781856591 515 2321846043176783657391 516 2367017637185364445425 517 2412978629822953180131 518 2459741259721555130685 519 2507317931218760318685 520 2555721216277101372435 521 2604963856421902213590 522 2655058764697759812810 523 2706019027643802070090 524 2757857907287865697590 525 2810588843159738808090 526 2864225454323613740646 527 2918781541429896486630 528 2974271088786519914106 529 3030708266449908826431 530 3088107432335745732081 531 3146483134349687046993 532 3205850112538180298191 533 3266223301259533748133 534 3327617831375390713083 535 3390049032462761705883 536 3453532435046768393781 537 3518083772854254225468 538 3583718985088417448196 539 3650454218724623105796 540 3718305830827551481596 541 3787290390889841326660 542 3857424683192387093436 543 3928725709186450277820 544 4001210689897745858820 545 4074897068352665714445 546 4149802512026801785155 547 4225944915315932652195 548 4303342402029638097405 549 4382013327907707113655 550 4461976283159505740905 551 4543250095026472012041 552 4625853830367906205095 553 4709806798270225514226 554 4795128552679853170926 555 4881838895059912969326 556 4969957877070901075218 557 5059505803275507927486 558 5150503233867763973058 559 5242970987426683912258 560 5336930143694585070558 561 5432402046380256455211 562 5529408305987156001093 563 5627970802666814459301 564 5728111689097625334651 565 5829853393389201234201 566 5933218622012477948295 567 6038230362755748548391 568 6144911887706810752105 569 6253286756261411775480 570 6363378818158175865480 571 6475212216540200682120 572 6588811391043509679480 573 6704201080912548618120 574 6821406328142915328120 575 6940452480651512832120 576 7061365195474316931336 577 7184170441991950354585 578 7308894505183256570871 579 7435563988907067370071 580 7564205819212359323721 581 7694847247676995248843 582 7827515854775247812181 583 7962239553274303430133 584 8099046591659945641083 585 8237965557591618151758 586 8379025381387068787666 587 8522255339536776609618 588 8667685058248365493806 589 8815344517021208511906 590 8965264052251428490206 591 9117474360867501172830 592 9272006503996668463746 593 9428891910662370275415 594 9588162381512904568665 595 9749850092581526228665 596 9913987599078196485735 597 10080607839213195657165 598 10249744138052813057235 599 10421430211407328997235 600 10595700169751504875485 601 10772588522177798439156 602 10952130180382522385100 603 11134360462685165555916 604 11319315098081097080116 605 11507030230327874901516 606 11697542422065381242868 607 11890888658970008652276 608 12087106353943121388108 609 12286233351334018008933 610 12488307931197622149483 611 12693368813587129581771 612 12901455162881840782293 613 13112606592150409351711 614 13326863167549737762561 615 13544265412759753043361 616 13764854313454296144015 617 13988671321808359867626 618 14215758361041911397750 619 14446157830000536597750 620 14679912607773144410250 621 14917066058346970839750 622 15157662035300123160250 623 15401744886531906152250 624 15649359459031173339750 625 15900551103682947367875 626 16155365680113554835501 627 16413849561574522074765 628 16676049639865479550611 629 16942013330296323738561 630 17211788576688886527711 631 17485423856418363388543 632 17762968185494752741521 633 18044471123684560162608 634 18329982779673022265808 635 18619553816267106310608 636 18913235455639542793776 637 19211079484614149500368 638 19513138259992706708016 639 19819464713923644461616 640 20130112359312804062416 641 20445135295276537146225 642 20764588212637406960031 643 21088526399462757684735 644 21417005746646418893985 645 21750082753533813485235 646 22087814533590738669165 647 22430258820116090857485 648 22777473971998806546915 649 23129518979519292558790 650 23486453470195620259290 651 23848337714674759654746 652 24215232632669130529830 653 24587199798938749073706 654 24964301449319249720406 655 25346600486796063214806 656 25734160487625033204618 657 26127045707499754951791 658 26525321087765921053633 659 26929052261682960364833 660 27338305560733257616383 661 27753148020979242536181 662 28173647389468638588843 663 28599872130688162768971 664 29031891433065969202821 665 29469775215523130637996 666 29913594134074453229460 667 30363419588478921362836 668 30819323728940070592620 669 31281379462856588113620 670 31749660461623441528620 671 32224241167483838023980 672 32705196800432317417620 673 33192603365169283900605 674 33686537658107282654355 675 34187077274429328890355 676 34694300615199598228141 677 35208286894526788700295 678 35729116146780466050201 679 36256869233860705369401 680 36791627852521343506551 681 37333474541747158069218 682 37882492690185290233086 683 38438766543631229970558 684 39002381212569683712258 685 39573422679770645860558 686 40151977807940996983986 687 40738134347431952935218 688 41331980944002690553326 689 41933607146640477033051 690 42543103415437631470101 691 43160561129525648521845 692 43786072595066815557291 693 44419731053303656108905 694 45061630688666533881655 695 45711866636939753021655 696 46370534993486491797945 697 47037732821532908306280 698 47713558160511758263320 699 48398110034465866423320 700 49091488460511794617320 701 49793794457364050886936 702 50505130053920185661160 703 51225598297907122405096 704 51955303264589071654296 705 52694350065537378837321 706 53442844857462657782343 707 54200894851109563301031 708 54968608320214557744633 709 55746094610527027933083 710 56533464148894110368133 711 57330828452409584155941 712 58138300137627192583243 713 58955992929838755814206 714 59784021672417438702306 715 60622502336226539243106 716 61471552029094164729630 717 62331289005354164212146 718 63201832675453687408590 719 64083303615627741760590 720 64975823577641120883090 721 65879515498598079212935 722 66794503510820129223465 723 67720912951792339138185 724 68658870374178510646935 725 69608503555905617702685 726 70569941510317889056131 727 71543314496400918768675 728 72528754029076190532141 729 73526392889566403215716 730 74536365135831986657116 731 75558806113079198315868 732 76593852464340193011876 733 77641642141125459582108 734 78702314414149019902308 735 79776009884126787339108 736 80862870492648483320796 737 81963039533123512342293 738 83076661661801197351611 739 84203882908865779101211 740 85344850689606584688261 741 86499713815663772152815 742 87668622506350059652401 743 88851728400048849385425 744 90049184565689158094175 745 91261145514297767641050 746 92487767210629010818950 747 93729207084872609228550 748 94985624044439981731450 749 96257178485829443668950 750 97544032306570718721450 751 98846348917249186973226 752 100164293253610294441590 753 101498031788744551028211 754 102847732545353545553661 755 104213565108097408244061 756 105595700636024152751043 757 106994311875081331503121 758 108409573170710439907983 759 109841660480524506651183 760 111290751387069309067233 761 112757025110668654294176 762 114240662522354168662368 763 115741846156880039512416 764 117260760225823155386016 765 118797590630769092286816 766 120352524976584395466400 767 121925752584775607953056 768 123517464506935498808160 769 125127853538276945866785 770 126757114231254929495535 771 128405442909277095681615 772 130073037680503348552785 773 131760098451734934218115 774 133466826942393479614365 775 135193426698590451842365 776 136940103107287505281971 777 138707063410548185583030 778 140494516719881461443306 779 142302674030677556902506 780 144131748236736558704406 781 145981954144890275106618 782 147853508489717824349766 783 149746629948355432834758 784 151661539155400924898458 785 153598458717913387924383 786 155557613230508498376081 787 157539229290549996196593 788 159543535513437796877871 789 161570762547993232369221 790 163621143091941913863771 791 165694911907494711376635 792 167792305837027346907861 793 169913563818859099867420 794 172058926903131125328420 795 174228638267784887568420 796 176422943234641213257180 797 178642089285580470552420 798 180886326078824382273180 799 183155905465319983233180 800 185451081505226233734180 801 187772110484503803141741 802 190119250931608539392995 803 192492763634289142218051 804 194892911656489559793501 805 197319960355356630488151 806 199774177398353493307593 807 202255832780479292595561 808 204765198841595704506183 809 207302550283860814722258 810 209868164189270878860558 811 212462320037310498975886 812 215085299722711751551218 813 217737387573322804341726 814 220418870368086561425826 815 223130037355129877806626 816 225871180269963886902270 817 228642593353795986263691 818 231444573371954028863205 819 234277419632423269307205 820 237141434004496616340955 821 240036920937538745033145 822 242964187479864624052455 823 245923543297733015477895 824 248915300694455506619145 825 251939774629621635362520 826 254997282738440672602536 827 258088145351200627368360 828 261212685512845042308696 829 264371229002668149257896 830 267564104354128956670296 831 270791642874784842778968 832 274054178666345230409256 833 277352048644845921456633 834 280685592560944671122583 835 284055153020338584091383 836 287461075504303916924841 837 290903708390358873051243 838 294383402973049978828981 839 297900513484862631274581 840 301455397117256410159131 841 305048414041825749296430 842 308679927431586563970546 843 312350303482389433579890 844 316059911434459940709390 845 319809123594066769981890 846 323598315355318172184510 847 327427865222087401315390 848 331298154830067734351010 849 335209568968957685694135 850 339162495604777030427385 851 343157325902314252667481 852 347194454247706037490375 853 351274278271149427077741 854 355397198869747263920691 855 359563620230487546107091 856 363773949853357321914493 857 368028598574591753131476 858 372327980590058978736108 859 376672513478781412771308 860 381062618226594112473108 861 385498719249940854929196 862 389981244419808562771668 863 394510625085800721639636 864 399087296100350434384236 865 403711695843073759230661 866 408384266245263981359115 867 413105452814527469619051 868 417875704659561772348725 869 422695474515076608534975 870 427565218766858412816225 871 432485397476979095105025 872 437456474409149677884975 873 442478917054219476520650 874 447553196655821490208150 875 452679788236164673488150 876 457859170621973760542826 877 463091826470577316802790 878 468378242296144694700186 879 473718908496072572719386 880 479114319377521759217286 881 484564973184104944811043 882 490071372122726089462221 883 495634022390572132722733 884 501253434202257717949683 885 506930121817123623643233 886 512664603566689597413951 887 518457401882262290443743 888 524309043322698992667441 889 530220058602327871270416 890 536190982619025417471216 891 542222354482451808937200 892 548314717542444897565456 893 554468619417573534750960 894 560684612023850948658960 895 566963251603608890418960 896 573305098754533268563440 897 579710718458861993445585 898 586180680112745755786815 899 592715557555772465926815 900 599315929100656082776065 901 605982377563090563903571 902 612715490291769670630605 903 619515859198573364444781 904 626384080788921533497731 905 633320756192295790404006 906 640326491192930085018618 907 647401896260670878335866 908 654547586582007626122758 909 661764182091274323376458 910 669052307502022863176758 911 676412592338568965991606 912 683845670967711437986218 913 691352182630625519384271 914 698932771474931086433121 915 706588086586936473033921 916 714318782024058680611935 917 722125516847420747322261 918 730008955154627050211595 919 737969766112717316487595 920 746008623991300122583845 921 754126208195866662250380 922 762323203301285567447220 923 770600299085479568371380 924 778958190563284781506380 925 787397578020493417147380 926 795919167048080700424716 927 804523668576616802423820 928 813211798910864580580276 929 821984279764563930115101 930 830841838295403550867251 931 839785207140180936477843 932 848815124450151395483661 933 857932333926566916486183 934 867137584856405692176633 935 876431632148293119617433 936 885815236368615096805911 937 895289163777824438177218 938 904854186366941234340126 939 914511081894247983981726 940 924260633922180328525026 941 934103631854414222777070 942 944040870973150377464466 943 954073152476596812218130 944 964201283516650360239630 945 974426077236777968557755 946 984748352810098640465845 947 995168935477666869418005 948 1005688656586958416355595 949 1016308353630559285134345 950 1027028870285058753427095 951 1037851056450147319187511 952 1048775768287920425476185 953 1059803868262388829172296 954 1070936225179196481821496 955 1082173714225546793603896 956 1093517217010338154144968 957 1104967621604509586636856 958 1116525822581597414488008 959 1128192721058503822475208 960 1139969224736478197134008 961 1151856247942312133891241 962 1163854711669749001216743 963 1175965543621108954850631 964 1188189678249130297947481 965 1200528056799028085769531 966 1212981627350770876357605 967 1225551344861576531410821 968 1238238171208627974414315 969 1251043075232009815868190 970 1263967032777866758290690 971 1277011026741784696494210 972 1290176047112395431464190 973 1303463091015205919008210 974 1316873162756652977185710 975 1330407273868384379377710 976 1344066443151767262710706 977 1357851696722624784409575 978 1371764068056201961520841 979 1385804598032361632320041 980 1399974334981011480595191 981 1414274334727763066882493 982 1428705660639823813620451 983 1443269383672122894084483 984 1457966582413671977865933 985 1472798343134161788567108 986 1487765759830795432297596 987 1502869934275359458476668 988 1518111976061533617372036 989 1533493002652440281736636 990 1549014139428434502842436 991 1564676519735135674153540 992 1580481284931701778830076 993 1596429584439347200209525 994 1612522575790105077373275 995 1628761424675835190873275 996 1645147304997478366666725 997 1661681398914558389285775 998 1678364896894932418254225 999 1695198997764790904754225 1000 1712184908758908008542975