1 1 2 6 3 15 4 19 5 24 6 42 7 73 8 127 9 208 10 337 11 528 12 827 13 1263 14 1902 15 2819 16 4133 17 5986 18 8578 19 12146 20 17057 21 23711 22 32708 23 44726 24 60713 25 81800 26 109468 27 145526 28 192288 29 252521 30 329792 31 428316 32 553478 33 711596 34 910563 35 1159790 36 1470798 37 1857286 38 2335838 39 2926061 40 3651688 41 4540502 42 5625896 43 6946852 44 8549811 45 10489000 46 12828386 47 15642512 48 19018801 49 23058592 50 27880409 51 33620962 52 40439466 53 48518887 54 58071136 55 69339435 56 82603981 57 98185407 58 116451566 59 137822002 60 162776820 61 191861488 62 225698134 63 264991658 64 310543169 65 363258495 66 424163289 67 494414528 68 575318409 69 668344278 70 775147106 71 897583523 72 1037739424 73 1197949303 74 1380828864 75 1589300106 76 1826628340 77 2096453541 78 2402833860 79 2750283376 80 3143824951 81 3589033421 82 4092099110 83 4659879456 84 5299973135 85 6020783302 86 6831602040 87 7742687246 88 8765360835 89 9912099026 90 11196649017 91 12634132852 92 14241184898 93 16036073167 94 18038858328 95 20271538787 96 22758231298 97 25525342322 98 28601776143 99 32019134092 100 35811957459 101 40017954538 102 44678282676 103 49837810973 104 55545443326 105 61854425127 106 68822708806 107 76513310728 108 84994728396 109 94341349533 110 104633932530 111 115960070658 112 128414743011 113 142100844543 114 157129811796 115 173622233538 116 191708554947 117 211529777216 118 233238254852 119 256998490896 120 282988044596 121 311398426537 122 342436129020 123 376323639842 124 413300603355 125 453624972989 126 497574310830 127 545447095132 128 597564180575 129 654270270172 130 715935562392 131 782957399012 132 855762118360 133 934806904877 134 1020581862990 135 1113612100940 136 1214460039361 137 1323727752085 138 1442059542846 139 1570144562670 140 1708719692923 141 1858572456156 142 2020544235824 143 2195533522226 144 2384499492514 145 2588465636011 146 2808523718934 147 3045837827426 148 3301648765779 149 3577278545421 150 3874135272230 151 4193718113642 152 4537622720557 153 4907546729262 154 5305295756062 155 5732789501816 156 6192068358052 157 6685300167357 158 7214787511922 159 7782975178402 160 8392458207812 161 9045990111168 162 9746491748255 163 10497060380008 164 11300979434320 165 12161728486392 166 13082993972166 167 14068680179641 168 15122921010051 169 16250092048721 170 17454823485533 171 18742013341186 172 20116841644246 173 21584784928836 174 23151631755356 175 24823498612719 176 26606846873052 177 28508500211654 178 30535663136402 179 32695940032654 180 34997355421369 181 37448374735100 182 40057926443690 183 42835424728690 184 45790793602810 185 48934491660125 186 52277538321370 187 55831540826220 188 59608722798115 189 63621953625885 190 67884779559776 191 72411455642806 192 77216979531128 193 82317126197631 194 87728484656953 195 93468495690056 196 99555491661649 197 106008737488899 198 112848473815484 199 120095961440199 200 127773528133613 201 135904616744740 202 144513835926782 203 153627012231500 204 163271244994927 205 173474962746157 206 184267982516252 207 195681570874850 208 207748508017252 209 220503153718975 210 233981516584245 211 248221325230236 212 263262103057885 213 279145245070791 214 295914098513780 215 313614045771203 216 332292591233801 217 351999450689384 218 372786644891226 219 394708595846564 220 417822227593447 221 442187069801925 222 467865366243284 223 494922186250710 224 523425541347584 225 553446505142915 226 585059338607385 227 618341618964788 228 653374374237825 229 690242221669363 230 729033512203688 231 769840479006423 232 812759392521185 233 857890719793148 234 905339290724590 235 955214468965312 236 1007630330018391 237 1062705844423921 238 1120565068526996 239 1181337340675986 240 1245157485516385 241 1312166023945248 242 1382509391770012 243 1456340164347058 244 1533817290426882 245 1615106332450843 246 1700379716441622 247 1789816988918888 248 1883605083883312 249 1981938597282528 250 2085020072201983 251 2193060291867844 252 2306278584131270 253 2424903134187644 254 2549171309426490 255 2679329993130989 256 2815635930811981 257 2958356086112577 258 3107768009969531 259 3264160219947342 260 3427832593647950 261 3599096772737138 262 3778276581999504 263 3965708459578253 264 4161741903057954 265 4366739927509456 266 4581079540044170 267 4805152227247386 268 5039364459909815 269 5284138211405186 270 5539911494400392 271 5807138911816502 272 6086292227295498 273 6377860950651667 274 6682352943863988 275 7000295043046278 276 7332233701808179 277 7678735651733725 278 8040388585262954 279 8417801856678620 280 8811607206773389 281 9222459506410486 282 9651037525223162 283 10098044720165336 284 10564210050484702 285 11050288813785545 286 11557063509610998 287 12085344725542934 288 12635972052085713 289 13209815021306959 290 13807774075853606 291 14430781562760550 292 15079802759414571 293 15755836925523770 294 16459918388848396 295 17193117658494062 296 17956542573342462 297 18751339479799603 298 19578694446275652 299 20439834508548118 300 21336028953802079 301 22268590636872985 302 23238877337353738 303 24248293150450340 304 25298289920672693 305 26390368711192258 306 27526081317774538 307 28707031820548940 308 29934878182319798 309 31211333886652365 310 32538169624894482 311 33917215024661306 312 35350360429901721 313 36839558724354631 314 38386827209019946 315 39994249525395170 316 41663977634878943 317 43398233846581362 318 45199312903741408 319 47069584120961022 320 49011493582946619 321 51027566396176828 322 53120409005295871 323 55292711564843708 324 57547250378666616 325 59886890397560573 326 62314587787270612 327 64833392557949741 328 67446451266950532 329 70157009786022406 330 72968416145370851 331 75884123444767792 332 78907692845385705 333 82042796631644272 334 85293221357385980 335 88662871065605705 336 92155770595777086 337 95776068968623785 338 99528042862132616 339 103416100168624560 340 107444783647306564 341 111618774661136617 342 115942897013820632 343 120422120874771212 344 125061566808536247 345 129866509896462307 346 134842383966833688 347 139994785921949580 348 145329480178076743 349 150852403206710650 350 156569668193818682 351 162487569804405336 352 168612589070599091 353 174951398389489486 354 181510866649721381 355 188298064473007314 356 195320269589235892 357 202584972332119739 358 210099881273765752 359 217872928985080599 360 225912277941181385 361 234226326557517381 362 242823715377610418 363 251713333396889166 364 260904324544389178 365 270406094306725466 366 280228316515788714 367 290380940285445494 368 300874197118331579 369 311718608167991619 370 322924991678374413 371 334504470584602680 372 346468480298917677 373 358828776664362900 374 371597444101110282 375 384786903927922599 376 398409922883266074 377 412479621829540821 378 427009484664591544 379 442013367423941626 380 457505507598893730 381 473500533652473337 382 490013474760500252 383 507059770758271872 384 524655282321213442 385 542816301359911662 386 561559561657508143 387 580902249730949910 388 600862015943648228 389 621456985851023440 390 642705771807623438 391 664627484815683057 392 687241746646133374 393 710568702210292442 394 734629032214482004 395 759443966075733264 396 785035295130368915 397 811425386114826030 398 838637194950095150 399 866694280809124740 400 895620820499777452 401 925441623140924927 402 956182145166880416 403 987868505635965212 404 1020527501879722661 405 1054186625468512051 406 1088874078529555882 407 1124618790394499400 408 1161450434612060172 409 1199399446302821545 410 1238497039893140115 411 1278775227203294166 412 1320266835929667985 413 1363005528494144641 414 1407025821302008520 415 1452363104381470529 416 1499053661445588012 417 1547134690351159197 418 1596644323994888987 419 1647621651621407202 420 1700106740584915998 421 1754140658536950959 422 1809765496085194238 423 1867024389893693329 424 1925961546271026163 425 1986622265216713677 426 2049052964971912504 427 2113301207046304952 428 2179415721766649274 429 2247446434318922062 430 2317444491331209216 431 2389462287966994168 432 2463553495579406092 433 2539773089893763958 434 2618177379770803162 435 2698824036517874720 436 2781772123799899654 437 2867082128119147114 438 2954815989915074504 439 3045037135253325974 440 3137810508156923314 441 3233202603546270276 442 3331281500844801640 443 3432116898214385816 444 3535780147479247730 445 3642344289702489358 446 3751884091473397016 447 3864476081871563624 448 3980198590165369276 449 4099131784210893534 450 4221357709610844218 451 4346960329596894696 452 4476025565699092862 453 4608641339163016466 454 4744897613180532312 455 4884886435894812710 456 5028701984244782018 457 5176440608611789044 458 5328200878333063688 459 5484083628044816104 460 5644192004921701442 461 5808631516772611166 462 5977510081064039144 463 6150938074828046696 464 6329028385528398284 465 6511896462841889678 466 6699660371427792746 467 6892440844644779512 468 7090361339287522726 469 7293548091302424842 470 7502130172557118880 471 7716239548620064998 472 7936011137629737354 473 8161582870206558788 474 8393095750489697304 475 8630693918251898752 476 8874524712173704066 477 9124738734232785814 478 9381489915289068616 479 9644935581821480184 480 9915236523899586213 481 10192557064342591471 482 10477065129154319637 483 10768932319183243086 484 11068333983098948347 485 11375449291634150050 486 11690461313182918578 487 12013557090707026839 488 12344927720040274113 489 12684768429542837604 490 13033278661198424337 491 13390662153102653016 492 13757127023441168709 493 14132885855902258461 494 14518155786625580934 495 14913158592631845123 496 15318120781834206321 497 15733273684579257912 498 16158853546817631996 499 16595101624852267002 500 17042264281767434271 501 17500593085482698409 502 17970344908541214252 503 18451782029572602444 504 18945172236543093267 505 19450788931733284596 506 19968911238555413508 507 20499824110153795902 508 21043818439899449058 509 21601191173722772367 510 22172245424398750320 511 22757290587724391124 512 23356642460709596514 513 23970623361716966394 514 24599562252675408309 515 25243794863303192334 516 25903663817464395996 517 26579518761597979320 518 27271716495342612966 519 27980621104296763275 520 28706604095040800514 521 29450044532356183002 522 30211329178775869632 523 30990852636396510252 524 31789017491090443197 525 32606234459048232318 526 33442922535788919114 527 34299509147572623288 528 35176430305351705629 529 36074130761195446758 530 36993064167328518027 531 37933693237713440634 532 38896489912325176272 533 39881935524043237809 534 40890520968313777992 535 41922746875507275657 536 42979123786123278039 537 44060172328772049555 538 45166423401083705334 539 46298418353475053370 540 47456709175929007966 541 48641858687711729398 542 49854440730190955358 543 51095040362675549778 544 52364254061444286253 545 53662689921884179605 546 54990967863905468859 547 56349719840558143816 548 57739590050016088039 549 59161235150854172296 550 60615324480789134386 551 62102540278804175553 552 63623577910837253330 553 65179146098947545003 554 66769967154145106520 555 68396777212798548698 556 70060326476804691902 557 71761379457439972819 558 73500715223076630652 559 75279127650683960024 560 77097425681302674395 561 78956433579406923491 562 80856991196351982848 563 82799954237816352296 564 84786194535441595973 565 86816600322579084632 566 88892076514346010880 567 91013544991905182612 568 93181944891169878045 569 95398232895848863862 570 97663383535038414329 571 99978389485270331244 572 102344261877233384036 573 104762030607071007749 574 107232744652478553216 575 109757472393503424851 576 112337301938270279598 577 114973341453540394240 578 117666719500326401873 579 120418585374472187780 580 123230109452424994873 581 126102483542103058412 582 129036921239097328364 583 132034658288104063387 584 135096952949833035744 585 138225086373288720835 586 141420362973668217086 587 144684110815779484208 588 148017682003222510966 589 151422453073237789483 590 154899825397471159682 591 158451225588552542890 592 162078105912749822607 593 165781944708588471205 594 169564246811704988782 595 173426543985825439794 596 177370395360135993289 597 181397387872943446746 598 185509136721891646844 599 189707285820632680726 600 193993508262225537702 601 198369506789153865709 602 202837014270248748388 603 207397794184400803514 604 212053641111354690413 605 216806381229471124587 606 221657872820748475974 607 226610006782996247972 608 231664707149451352059 609 236823931615730494362 610 242089672074417057122 611 247463955157168124924 612 252948842784654029830 613 258546432724208335039 614 264258859155508493430 615 270088293244166014866 616 276036943723545201043 617 282107057484697018953 618 288300920174726176278 619 294620856803479121638 620 301069232358878879101 621 307648452430786352810 622 314360963843729154824 623 321209255298369428730 624 328195858022059983134 625 335323346428361261641 626 342594338785867460496 627 350011497896222622746 628 357577531781673857241 629 365295194382043811831 630 373167286261478154630 631 381196655324841666208 632 389386197544134691847 633 397738857694794957538 634 406257630102265547862 635 414945559398695243240 636 423805741290150840214 637 432841323334216564499 638 442055505728359231434 639 451451542108935720874 640 461032740361230461160 641 470802463440390513022 642 480764130203663218833 643 490921216253794954112 644 501277254794005444798 645 511835837494397546034 646 522600615370215983230 647 533575299671824495063 648 544763662786813738725 649 556169539154111037573 650 567796826190514216125 651 579649485229511157450 652 591731542472825552256 653 604047089954540956050 654 616600286518253996916 655 629395358807110383663 656 642436602267173419368 657 655728382163988894236 658 669275134612795156028 659 683081367622244057286 660 697151662152091950695 661 711490673184716516614 662 726103130810938227042 663 740993841329992227464 664 756167688364140327252 665 771629633987770607657 666 787384719871473445554 667 803438068440952399300 668 819794884051257674789 669 836460454176202657075 670 853440150613462544640 671 870739430705205158702 672 888363838574773653220 673 906319006379260711037 674 924610655578505808315 675 943244598220357065512 676 962226738242728207423 677 981563072792303845141 678 1001259693560422792068 679 1021322788135994891541 680 1041758641375992935479 681 1062573636793364240568 682 1083774257962925710934 683 1105367089945075954628 684 1127358820727900714089 685 1149756242687507347267 686 1172566254067163842836 687 1195795860475090593914 688 1219452176401479439536 689 1243542426754590711669 690 1268073948416515711079 691 1293054191818443922052 692 1318490722536045805315 693 1344391222904798968257 694 1370763493655882065420 695 1397615455572466638161 696 1424955151167030304147 697 1452790746379534844028 698 1481130532297091932322 699 1509982926894962835628 700 1539356476799528362865 701 1569259859073063437931 702 1599701883020977711196 703 1630691492021344539166 704 1662237765377393905036 705 1694349920192794293945 706 1727037313270398488523 707 1760309443034292517612 708 1794175951475821899663 709 1828646626123437487397 710 1863731402037049749320 711 1899440363826721298389 712 1935783747696412931299 713 1972771943512600409904 714 2010415496898492598934 715 2048725111353671166240 716 2087711650399881691617 717 2127386139752811552143 718 2167759769520583972412 719 2208843896428806985498 720 2250650046072922083445 721 2293189915197678266246 722 2336475374004504578246 723 2380518468486593706106 724 2425331422792485805336 725 2470926641617968422285 726 2517316712627081293918 727 2564514408902058040062 728 2612532691422992918938 729 2661384711577068381492 730 2711083813698148271135 731 2761643537636558798764 732 2813077621359891875864 733 2865400003584639248754 734 2918624826439509410674 735 2972766438160239363245 736 3027839395816752676537 737 3083858468072493109983 738 3140838637976785050077 739 3198795105790054109718 740 3257743291842776597300 741 3317698839427977030436 742 3378677617728174210296 743 3440695724776580764571 744 3503769490453474878436 745 3567915479517553127500 746 3633150494673183042338 747 3699491579673382599362 748 3766956022459444941313 749 3835561358337039998512 750 3905325373189730180376 751 3976266106729717056990 752 4048401855786789574582 753 4121751177635275883385 754 4196332893359988983102 755 4272166091260972657574 756 4349270130298037683049 757 4427664643574914225271 758 4507369541864010559794 759 4588405017171608922146 760 4670791546344508363567 761 4754549894717930081754 762 4839701119805730740498 763 4926266575032723815424 764 5014267913510175040688 765 5103727091854276819559 766 5194666374048667962366 767 5287108335350824261598 768 5381075866243386298941 769 5476592176430255347453 770 5573680798878545058272 771 5672365593906203855550 772 5772670753316433096377 773 5874620804578699892780 774 5978240615057491813492 775 6083555396288617644580 776 6190590708304201600320 777 6299372464006197091639 778 6409926933589568027420 779 6522280749014969584254 780 6636460908532098685777 781 6752494781253529594407 782 6870410111780244693874 783 6990235024878659228572 784 7111998030210373248849 785 7235728027114455304720 786 7361454309443491887876 787 7489206570453230430548 788 7619014907747050345276 789 7750909828275096268263 790 7884922253389331971618 791 8021083523954331954016 792 8159425405515110904755 793 8299980093521790814331 794 8442780218612430850530 795 8587858851953826070610 796 8735249510641600757233 797 8884986163159427124840 798 9037103234898696293048 799 9191635613738479181670 800 9348618655687129281599 801 9508088190585347193818 802 9670080527872103323137 803 9834632462413220756228 804 10001781280394040752022 805 10171564765275979747255 806 10344021203818401626204 807 10519189392165640304619 808 10697108642000597422454 809 10877818786764757700474 810 11061360187946073690515 811 11247773741434544089352 812 11437100883946983846483 813 11629383599520791759662 814 11824664426078241761028 815 12022986462061111054185 816 12224393373137172570106 817 12428929398978392611471 818 12636639360112362903746 819 12847568664846816055976 820 13061763316268781788626 821 13279269919318213924819 822 13500135687937694941520 823 13724408452298028974834 824 13952136666101359283425 825 14183369413961629183391 826 14418156418864024472208 827 14656548049703245679828 828 14898595328902249881273 829 15144349940111319231568 830 15393864235989126148586 831 15647191246065632664160 832 15904384684688545578399 833 16165498959053145212060 834 16430589177317240708359 835 16699711156801078485122 836 16972921432273958778402 837 17250277264327417916029 838 17531836647836733785712 839 17817658320510621670069 840 18107801771530909433267 841 18402327250282038974713 842 18701295775172237834794 843 19004769142546187508038 844 19312809935691065041364 845 19625481533935794016912 846 19942848121845384327586 847 20264974698510229667534 848 20591927086932244671431 849 20923771943507720935929 850 21260576767608817630959 851 21602409911263545036752 852 21949340588936214087555 853 22301438887408189282702 854 22658775775760953039090 855 23021423115461329165877 856 23389453670550876394388 857 23762941117939334342601 858 24141960057804136277488 859 24526586024095882182546 860 24916895495151821732460 861 25312965904417219164559 862 25714875651276710496532 863 26122704111995503466504 864 26536531650772567153182 865 26956439630905672819028 866 27382510426070436735505 867 27814827431713263185678 868 28253475076560341892690 869 28698538834242610071778 870 29150105235038871048686 871 29608261877736957496351 872 30073097441615194770864 873 30544701698544030169246 874 31023165525210122618684 875 31508580915462770661344 876 32001040992784977119757 877 32500640022889067025420 878 33007473426439161697382 879 33521637791900438473980 880 34043230888517518305952 881 34572351679421887949653 882 35109100334870766268106 883 35653578245617298527028 884 36205888036414528888251 885 36766133579653047980245 886 37334420009134770692514 887 37910853733982781927822 888 38495542452689710070134 889 39088595167304579819197 890 39690122197760646143603 891 40300235196344137614270 892 40919047162306481108483 893 41546672456619912684055 894 42183226816879090049408 895 42828827372348625420321 896 43483592659159159260856 897 44147642635651936809179 898 44821098697874513642701 899 45504083695227567130074 900 46196721946265483805620 901 46899139254650675528673 902 47611462925264368769078 903 48333821780473795803903 904 49066346176558577447173 905 49809168020296241154761 906 50562420785709670389600 907 51326239530976474546544 908 52100760915503081246660 909 52886123217163556361324 910 53682466349706000277632 911 54489931880326501165632 912 55308663047413571252904 913 56138804778463022205612 914 56980503708166253879604 915 57833908196671928716032 916 58699168348024012513308 917 59576436028776201766884 918 60465864886785725508688 919 61367610370186559067244 920 62281829746545086342628 921 63208682122198222835032 922 64148328461777117924192 923 65100931607916423375792 924 66066656301152296851892 925 67045669200009144785004 926 68038138901278281187120 927 69044235960488557228416 928 70064132912572145608040 929 71098004292725553024796 930 72146026657469096602004 931 73208378605904891810064 932 74285240801176673099404 933 75376795992131468958644 934 76483229035186506137584 935 77604726916401383383020 936 78741478773758897496932 937 79893675919654615235928 938 81061511863598582729792 939 82245182335129285714128 940 83444885306943306251476 941 84660821018240762910092 942 85893191998290070188624 943 87142203090212077763552 944 88408061474987181087464 945 89690976695685483894556 946 90991160681923613701012 947 92308827774548326812336 948 93644194750550513121372 949 94997480848209758387236 950 96368907792473131711488 951 97758699820568329017804 952 99167083707854934122836 953 100594288793913901271704 954 102040547008879079983616 955 103506092900010907471232 956 104991163658516099395284 957 106495999146613523105148 958 108020841924850094912144 959 109565937279666908174688 960 111131533251219493541625 961 112717880661452390733437 962 114325233142432032202631 963 115953847164938090585302 964 117603982067317351979641 965 119275900084600289851068 966 120969866377884413165434 967 122686149063984625482821 968 124425019245354679813539 969 126186751040279990153896 970 127971621613345948041537 971 129779911206181977122464 972 131611903168485577126303 973 133467883989326562285339 974 135348143328735811095838 975 137252974049578756912595 976 139182672249717948306637 977 141137537294464973794126 978 143117871849326092824182 979 145123981913041893447746 980 147156176850925384678573 981 149214769428498815564739 982 151300075845433737571156 983 153412415769794573837474 984 155552112372590280072701 985 157719492362634386786992 986 159914886021718021477244 987 162138627240096268890758 988 164391053552292481472884 989 166672506173220925662213 990 168983330034632446305440 991 171323873821883505985212 992 173694490011033394508846 993 176095534906269936451112 994 178527368677668564294951 995 180990355399285112938478 996 183484863087587217535994 997 186011263740224742339066 998 188569933375144137935534 999 191161252070047183895881 1000 193785604002199087229948