1 2 2 9 3 27 4 66 5 141 6 273 7 490 8 828 9 1332 10 2057 11 3069 12 4446 13 6279 14 8673 15 11748 16 15640 17 20502 18 26505 19 33839 20 42714 21 53361 22 66033 23 81006 24 98580 25 119080 26 142857 27 170289 28 201782 29 237771 30 278721 31 325128 32 377520 33 436458 34 502537 35 576387 36 658674 37 750101 38 851409 39 963378 40 1086828 41 1222620 42 1371657 43 1534885 44 1713294 45 1907919 46 2119841 47 2350188 48 2600136 49 2870910 50 3163785 51 3480087 52 3821194 53 4188537 54 4583601 55 5007926 56 5463108 57 5950800 58 6472713 59 7030617 60 7626342 61 8261779 62 8938881 63 9659664 64 10426208 65 11240658 66 12105225 67 13022187 68 13993890 69 15022749 70 16111249 71 17261946 72 18477468 73 19760516 74 21113865 75 22540365 76 24042942 77 25624599 78 27288417 79 29037556 80 30875256 81 32804838 82 34829705 83 36953343 84 39179322 85 41511297 86 43953009 87 46508286 88 49181044 89 51975288 90 54895113 91 57944705 92 61128342 93 64450395 94 67915329 95 71527704 96 75292176 97 79213498 98 83296521 99 87546195 100 91967570 101 96565797 102 101346129 103 106313922 104 111474636 105 116833836 106 122397193 107 128170485 108 134159598 109 140370527 110 146809377 111 153482364 112 160395816 113 167556174 114 174969993 115 182643943 116 190584810 117 198799497 118 207295025 119 216078534 120 225157284 121 234538656 122 244230153 123 254239401 124 264574150 125 275242275 126 286251777 127 297610784 128 309327552 129 321410466 130 333868041 131 346708923 132 359941890 133 373575853 134 387619857 135 402083082 136 416974844 137 432304596 138 448081929 139 464316573 140 481018398 141 498197415 142 515863777 143 534027780 144 552699864 145 571890614 146 591610761 147 611871183 148 632682906 149 654057105 150 676005105 151 698538382 152 721668564 153 745407432 154 769766921 155 794759121 156 820396278 157 846690795 158 873655233 159 901302312 160 929644912 161 958696074 162 988469001 163 1018977059 164 1050233778 165 1082252853 166 1115048145 167 1148633682 168 1183023660 169 1218232444 170 1254274569 171 1291164741 172 1328917838 173 1367548911 174 1407073185 175 1447506060 176 1488863112 177 1531160094 178 1574412937 179 1618637751 180 1663850826 181 1710068633 182 1757307825 183 1805585238 184 1854917892 185 1905322992 186 1956817929 187 2009420281 188 2063147814 189 2118018483 190 2174050433 191 2231262000 192 2289671712 193 2349298290 194 2410160649 195 2472277899 196 2535669346 197 2600354493 198 2666353041 199 2733684890 200 2802370140 201 2872429092 202 2943882249 203 3016750317 204 3091054206 205 3166815031 206 3244054113 207 3322792980 208 3403053368 209 3484857222 210 3568226697 211 3653184159 212 3739752186 213 3827953569 214 3917811313 215 4009348638 216 4102588980 217 4197555992 218 4294273545 219 4392765729 220 4493056854 221 4595171451 222 4699134273 223 4804970296 224 4912704720 225 5022362970 226 5133970697 227 5247553779 228 5363138322 229 5480750661 230 5600417361 231 5722165218 232 5846021260 233 5972012748 234 6100167177 235 6230512277 236 6363076014 237 6497886591 238 6634972449 239 6774362268 240 6916084968 241 7060169710 242 7206645897 243 7355543175 244 7506891434 245 7660720809 246 7817061681 247 7975944678 248 8137400676 249 8301460800 250 8468156425 251 8637519177 252 8809580934 253 8984373827 254 9161930241 255 9342282816 256 9525464448 257 9711508290 258 9900447753 259 10092316507 260 10287148482 261 10484977869 262 10685839121 263 10889766954 264 11096796348 265 11306962548 266 11520301065 267 11736847677 268 11956638430 269 12179709639 270 12406097889 271 12635840036 272 12868973208 273 13105534806 274 13345562505 275 13589094255 276 13836168282 277 14086823089 278 14341097457 279 14599030446 280 14860661396 281 15126029928 282 15395175945 283 15668139633 284 15944961462 285 16225682187 286 16510342849 287 16798984776 288 17091649584 289 17388379178 290 17689215753 291 17994201795 292 18303380082 293 18616793685 294 18934485969 295 19256500594 296 19582881516 297 19913672988 298 20248919561 299 20588666085 300 20932957710 301 21281839887 302 21635358369 303 21993559212 304 22356488776 305 22724193726 306 23096721033 307 23474117975 308 23856432138 309 24243711417 310 24636004017 311 25033358454 312 25435823556 313 25843448464 314 26256282633 315 26674375833 316 27097778150 317 27526539987 318 27960712065 319 28400345424 320 28845491424 321 29296201746 322 29752528393 323 30214523691 324 30682240290 325 31155731165 326 31635049617 327 32120249274 328 32611384092 329 33108508356 330 33611676681 331 34120944013 332 34636365630 333 35157997143 334 35685894497 335 36220113972 336 36760712184 337 37307746086 338 37861272969 339 38421350463 340 38988036538 341 39561389505 342 40141468017 343 40728331070 344 41322038004 345 41922648504 346 42530222601 347 43144820673 348 43766503446 349 44395331995 350 45031367745 351 45674672472 352 46325308304 353 46983337722 354 47648823561 355 48321829011 356 49002417618 357 49690653285 358 50386600273 359 51090323202 360 51801887052 361 52521357164 362 53248799241 363 53984279349 364 54727863918 365 55479619743 366 56239613985 367 57007914172 368 57784588200 369 58569704334 370 59363331209 371 60165537831 372 60976393578 373 61795968201 374 62624331825 375 63461554950 376 64307708452 377 65162863584 378 66027091977 379 66900465641 380 67783056966 381 68674938723 382 69576184065 383 70486866528 384 71407060032 385 72336838882 386 73276277769 387 74225451771 388 75184436354 389 76153307373 390 77132141073 391 78121014090 392 79120003452 393 80129186580 394 81148641289 395 82178445789 396 83218678686 397 84269418983 398 85330746081 399 86402739780 400 87485480280 401 88579048182 402 89683524489 403 90798990607 404 91925528346 405 93063219921 406 94212147953 407 95372395470 408 96544045908 409 97727183112 410 98921891337 411 100128255249 412 101346359926 413 102576290859 414 103818133953 415 105071975528 416 106337902320 417 107616001482 418 108906360585 419 110209067619 420 111524210994 421 112851879541 422 114192162513 423 115545149586 424 116910930860 425 118289596860 426 119681238537 427 121085947269 428 122503814862 429 123934933551 430 125379396001 431 126837295308 432 128308725000 433 129793779038 434 131292551817 435 132805138167 436 134331633354 437 135872133081 438 137426733489 439 138995531158 440 140578623108 441 142176106800 442 143788080137 443 145414641465 444 147055889574 445 148711923699 446 150382843521 447 152068749168 448 153769741216 449 155485920690 450 157217389065 451 158964248267 452 160726600674 453 162504549117 454 164298196881 455 166107647706 456 167933005788 457 169774375780 458 171631862793 459 173505572397 460 175395610622 461 177302083959 462 179225099361 463 181164764244 464 183121186488 465 185094474438 466 187084736905 467 189092083167 468 191116622970 469 193158466529 470 195217724529 471 197294508126 472 199388928948 473 201501099096 474 203631131145 475 205779138145 476 207945233622 477 210129531579 478 212332146497 479 214553193336 480 216792787536 481 219051045018 482 221328082185 483 223624015923 484 225938963602 485 228273043077 486 230626372689 487 232999071266 488 235391258124 489 237803053068 490 240234576393 491 242685948885 492 245157291822 493 247648726975 494 250160376609 495 252692363484 496 255244810856 497 257817842478 498 260411582601 499 263026155975 500 265661687850 501 268318303977 502 270996130609 503 273695294502 504 276415922916 505 279158143616 506 281922084873 507 284707875465 508 287515644678 509 290345522307 510 293197638657 511 296072124544 512 298969111296 513 301888730754 514 304831115273 515 307796397723 516 310784711490 517 313796190477 518 316830969105 519 319889182314 520 322970965564 521 326076454836 522 329205786633 523 332359097981 524 335536526430 525 338738210055 526 341964287457 527 345214897764 528 348490180632 529 351790276246 530 355115325321 531 358465469103 532 361840849370 533 365241608433 534 368667889137 535 372119834862 536 375597589524 537 379101297576 538 382631104009 539 386187154353 540 389769594678 541 393378571595 542 397014232257 543 400676724360 544 404366196144 545 408082796394 546 411826674441 547 415597980163 548 419396863986 549 423223476885 550 427077970385 551 430960496562 552 434871208044 553 438810258012 554 442777800201 555 446773988901 556 450798978958 557 454852925775 558 458935985313 559 463048314092 560 467190069192 561 471361408254 562 475562489481 563 479793471639 564 484054514058 565 488345776633 566 492667419825 567 497019604662 568 501402492740 569 505816246224 570 510261027849 571 514737000921 572 519244329318 573 523783177491 574 528353710465 575 532956093840 576 537590493792 577 542257077074 578 546956011017 579 551687463531 580 556451603106 581 561248598813 582 566078620305 583 570941837818 584 575838422172 585 580768544772 586 585732377609 587 590730093261 588 595761864894 589 600827866263 590 605928271713 591 611063256180 592 616232995192 593 621437664870 594 626677441929 595 631952503679 596 637263028026 597 642609193473 598 647991179121 599 653409164670 600 658863330420 601 664353857272 602 669880926729 603 675444720897 604 681045422486 605 686683214811 606 692358281793 607 698070807960 608 703820978448 609 709608979002 610 715434995977 611 721299216339 612 727201827666 613 733143018149 614 739122976593 615 745141892418 616 751199955660 617 757297356972 618 763434287625 619 769610939509 620 775827505134 621 782084177631 622 788381150753 623 794718618876 624 801096777000 625 807515820750 626 813975946377 627 820477350759 628 827020231402 629 833604786441 630 840231214641 631 846899715398 632 853610488740 633 860363735328 634 867159656457 635 873998454057 636 880880330694 637 887805489571 638 894774134529 639 901786470048 640 908842701248 641 915943033890 642 923087674377 643 930276829755 644 937510707714 645 944789516589 646 952113465361 647 959482763658 648 966897621756 649 974358250580 650 981864861705 651 989417667357 652 997016880414 653 1004662714407 654 1012355383521 655 1020095102596 656 1027882087128 657 1035716553270 658 1043598717833 659 1051528798287 660 1059507012762 661 1067533580049 662 1075608719601 663 1083732651534 664 1091905596628 665 1100127776328 666 1108399412745 667 1116720728657 668 1125091947510 669 1133513293419 670 1141984991169 671 1150507266216 672 1159080344688 673 1167704453386 674 1176379819785 675 1185106672035 676 1193885238962 677 1202715750069 678 1211598435537 679 1220533526226 680 1229521253676 681 1238561850108 682 1247655548425 683 1256802582213 684 1266003185742 685 1275257593967 686 1284566042529 687 1293928767756 688 1303346006664 689 1312817996958 690 1322344977033 691 1331927185975 692 1341564863562 693 1351258250265 694 1361007587249 695 1370813116374 696 1380675080196 697 1390593721968 698 1400569285641 699 1410602015865 700 1420692157990 701 1430839958067 702 1441045662849 703 1451309519792 704 1461631777056 705 1472012683506 706 1482452488713 707 1492951442955 708 1503509797218 709 1514127803197 710 1524805713297 711 1535543780634 712 1546342259036 713 1557201403044 714 1568121467913 715 1579102709613 716 1590145384830 717 1601249750967 718 1612416066145 719 1623644589204 720 1634935579704 721 1646289297926 722 1657706004873 723 1669185962271 724 1680729432570 725 1692336678945 726 1704007965297 727 1715743556254 728 1727543717172 729 1739408714136 730 1751338813961 731 1763334284193 732 1775395393110 733 1787522409723 734 1799715603777 735 1811975245752 736 1824301606864 737 1836694959066 738 1849155575049 739 1861683728243 740 1874279692818 741 1886943743685 742 1899676156497 743 1912477207650 744 1925347174284 745 1938286334284 746 1951294966281 747 1964373349653 748 1977521764526 749 1990740491775 750 2004029813025 751 2017390010652 752 2030821367784 753 2044324168302 754 2057898696841 755 2071545238791 756 2085264080298 757 2099055508265 758 2112919810353 759 2126857274982 760 2140868191332 761 2154952849344 762 2169111539721 763 2183344553929 764 2197652184198 765 2212034723523 766 2226492465665 767 2241025705152 768 2255634737280 769 2270319858114 770 2285081364489 771 2299919554011 772 2314834725058 773 2329827176781 774 2344897209105 775 2360045122730 776 2375271219132 777 2390575800564 778 2405959170057 779 2421421631421 780 2436963489246 781 2452585048903 782 2468286616545 783 2484068499108 784 2499931004312 785 2515874440662 786 2531899117449 787 2548005344751 788 2564193433434 789 2580463695153 790 2596816442353 791 2613251988270 792 2629770646932 793 2646372733160 794 2663058562569 795 2679828451569 796 2696682717366 797 2713621677963 798 2730645652161 799 2747754959560 800 2764949920560 801 2782230856362 802 2799598088969 803 2817051941187 804 2834592736626 805 2852220799701 806 2869936455633 807 2887740030450 808 2905631850988 809 2923612244892 810 2941681540617 811 2959840067429 812 2978088155406 813 2996426135439 814 3014854339233 815 3033373099308 816 3051982749000 817 3070683622462 818 3089476054665 819 3108360381399 820 3127336939274 821 3146406065721 822 3165568098993 823 3184823378166 824 3204172243140 825 3223615034640 826 3243152094217 827 3262783764249 828 3282510387942 829 3302332309331 830 3322249873281 831 3342263425488 832 3362373312480 833 3382579881618 834 3402883481097 835 3423284459947 836 3443783168034 837 3464379956061 838 3485075175569 839 3505869178938 840 3526762319388 841 3547754950980 842 3568847428617 843 3590040108045 844 3611333345854 845 3632727499479 846 3654222927201 847 3675819988148 848 3697519042296 849 3719320450470 850 3741224574345 851 3763231776447 852 3785342420154 853 3807556869697 854 3829875490161 855 3852298647486 856 3874826708468 857 3897460040760 858 3920199012873 859 3943043994177 860 3965995354902 861 3989053466139 862 4012218699841 863 4035491428824 864 4058872026768 865 4082360868218 866 4105958328585 867 4129664784147 868 4153480612050 869 4177406190309 870 4201441897809 871 4225588114306 872 4249845220428 873 4274213597676 874 4298693628425 875 4323285695925 876 4347990184302 877 4372807478559 878 4397737964577 879 4422782029116 880 4447940059816 881 4473212445198 882 4498599574665 883 4524101838503 884 4549719627882 885 4575453334857 886 4601303352369 887 4627270074246 888 4653353895204 889 4679555210848 890 4705874417673 891 4732311913065 892 4758868095302 893 4785543363555 894 4812338117889 895 4839252759264 896 4866287689536 897 4893443311458 898 4920720028681 899 4948118245755 900 4975638368130 901 5003280802157 902 5031045955089 903 5058934235082 904 5086946051196 905 5115081813396 906 5143341932553 907 5171726820445 908 5200236889758 909 5228872554087 910 5257634227937 911 5286522326724 912 5315537266776 913 5344679465334 914 5373949340553 915 5403347311503 916 5432873798170 917 5462529221457 918 5492314003185 919 5522228566094 920 5552273333844 921 5582448731016 922 5612755183113 923 5643193116561 924 5673762958710 925 5704465137835 926 5735300083137 927 5766268224744 928 5797369993712 929 5828605822026 930 5859976142601 931 5891481389283 932 5923121996850 933 5954898401013 934 5986811038417 935 6018860346642 936 6051046764204 937 6083370730556 938 6115832686089 939 6148433072133 940 6181172330958 941 6214050905775 942 6247069240737 943 6280227780940 944 6313526972424 945 6346967262174 946 6380549098121 947 6414272929143 948 6448139205066 949 6482148376665 950 6516300895665 951 6550597214742 952 6585037787524 953 6619623068592 954 6654353513481 955 6689229578681 956 6724251721638 957 6759420400755 958 6794736075393 959 6830199205872 960 6865810253472 961 6901569680434 962 6937477949961 963 6973535526219 964 7009742874338 965 7046100460413 966 7082608751505 967 7119268215642 968 7156079321820 969 7193042540004 970 7230158341129 971 7267427197101 972 7304849580798 973 7342425966071 974 7380156827745 975 7418042641620 976 7456083884472 977 7494281034054 978 7532634569097 979 7571144969311 980 7609812715386 981 7648638288993 982 7687622172785 983 7726764850398 984 7766066806452 985 7805528526552 986 7845150497289 987 7884933206241 988 7924877141974 989 7964982794043 990 8005250652993 991 8045681210360 992 8086274958672 993 8127032391450 994 8167954003209 995 8209040289459 996 8250291746706 997 8291708872453 998 8333292165201 999 8375042124450 1000 8416959250700