1 1 2 6 3 9 4 13 5 19 6 37 7 58 8 97 9 143 10 227 11 328 12 492 13 688 14 992 15 1364 16 1903 17 2551 18 3473 19 4586 20 6097 21 7911 22 10333 23 13226 24 16988 25 21454 26 27172 27 33938 28 42437 29 52423 30 64833 31 79354 32 97130 33 117824 34 142930 35 172018 36 206925 37 247179 38 295105 39 350154 40 415124 41 489414 42 576540 43 675794 44 791345 45 922483 46 1074325 47 1246034 48 1443675 49 1666409 50 1921549 51 2208184 52 2534870 53 2900714 54 3315970 55 3779668 56 4303685 57 4887189 58 5544215 59 6273874 60 7092385 61 7999055 62 9012833 63 10133110 64 11381593 65 12757967 66 14287467 67 15969932 68 17834062 69 19880242 70 22141526 71 24618572 72 27348872 73 30333812 74 33616232 75 37198092 76 41127678 77 45407930 78 50093798 79 55189020 80 60755196 81 66797520 82 73385628 83 80525820 84 88295958 85 96704202 86 105838062 87 115707372 88 126409512 89 137956692 90 150457992 91 163927788 92 178486950 93 194153058 94 211060830 95 229230636 96 248811405 97 269827473 98 292444095 99 316689378 100 342745323 101 370644933 102 400589595 103 432616998 104 466948185 105 503627091 106 542897355 107 584808708 108 629628010 109 677412538 110 728455398 111 782821248 112 840830155 113 902555863 114 968349085 115 1038292486 116 1112767975 117 1191869393 118 1276013915 119 1365306118 120 1460199444 121 1560811714 122 1667636828 123 1780805774 124 1900854043 125 2027928265 126 2162610527 127 2305063046 128 2455915462 129 2615348736 130 2784045550 131 2962205246 132 3150565067 133 3349346221 134 3559346167 135 3780808070 136 4014591308 137 4260964474 138 4520855508 139 4794558574 140 5083071695 141 5386718909 142 5706575563 143 6042995374 144 6397133223 145 6769377225 146 7160969257 147 7572332196 148 8004797372 149 8458827156 150 8935850976 151 9436371152 152 9961917485 153 10513037977 154 11091372175 155 11697513854 156 12333215415 157 12999122657 158 13697110495 159 14427877522 160 15193424597 161 15994509407 162 16833269815 163 17710523512 164 18628548620 165 19588230324 166 20591998940 167 21640807672 168 22737243280 169 23882335112 170 25078838672 171 26327860792 172 27632330380 173 28993439972 174 30414305820 175 31896207704 176 33442453720 177 35054420512 178 36735623000 179 38487535832 180 40313886428 181 42216257828 182 44198605388 183 46262622648 184 48412499088 185 50650049288 186 52979714192 187 55403431800 188 57925900572 189 60549194100 190 63278286924 191 66115390200 192 69065761977 193 72131764065 194 75318957147 195 78629856798 196 82070334393 197 85643072583 198 89354274753 199 93206794098 200 97207173969 201 101358453303 202 105667538163 203 110137656288 204 114776086008 205 119586260148 206 124575852732 207 129748506060 208 135112300167 209 140671103415 210 146433427785 211 152403372546 212 158589891885 213 164997334731 214 171635125065 215 178507865922 216 185625463180 217 192992794006 218 200620274580 219 208513062186 220 216682096321 221 225132834811 222 233876771725 223 242919671986 224 252273597250 225 261944642432 226 271945469930 227 282282510826 228 292969043385 229 304011859231 230 315424886621 231 327215285666 232 339397650820 233 351979535566 234 364976237900 235 378395713322 236 392253979645 237 406559422071 238 421328817745 239 436570989866 240 452303493587 241 468535619497 242 485285741413 243 502563627632 244 520388490578 245 538770606286 246 557730070062 247 577277676844 248 597434424917 249 618211661309 250 639631334023 251 661705353034 252 684456638877 253 707897699619 254 732052476397 255 756934088526 256 782567522033 257 808966543407 258 836157235683 259 864154026692 260 892984121018 261 922662647302 262 953217986578 263 984665982212 264 1017036219288 265 1050345297596 266 1084624062712 267 1119889887364 268 1156174906922 269 1193497309694 270 1231890581794 271 1271373744820 272 1311981665300 273 1353734244720 274 1396667794100 275 1440803112340 276 1486177988050 277 1532814166670 278 1580750980250 279 1630011141220 280 1680635560120 281 1732647966620 282 1786090920600 283 1840989190820 284 1897387022050 285 1955310276790 286 2014804959050 287 2075898046820 288 2138637342725 289 2203050997745 290 2269188689495 291 2337079766970 292 2406775824375 293 2478307467545 294 2551728289175 295 2627070178590 296 2704388769225 297 2783717297595 298 2865113523675 299 2948612057820 300 3034272833046 301 3122131900446 302 3212251454178 303 3304669016376 304 3399449091363 305 3496630740759 306 3596280873237 307 3698440122078 308 3803177850147 309 3910536336213 310 4020587495847 311 4133375285598 312 4248974228292 313 4367430035658 314 4488819938892 315 4613191441254 316 4740624539703 317 4871168608221 318 5004906517323 319 5141889550206 320 5282203509342 321 5425901672256 322 5573072885958 323 5723772461046 324 5878092352663 325 6036089993569 326 6197860562547 327 6363463657758 328 6532997748412 329 6706524689218 330 6884146362628 331 7065926925574 332 7251971741755 333 7442347367969 334 7637162777255 335 7836486972358 336 8040432609375 337 8249071239049 338 8462519331905 339 8680851037724 340 8904186718744 341 9132603228184 342 9366224959340 343 9605131522664 344 9849451421245 345 10099267134273 346 10354711419775 347 10615869680054 348 10882879013075 349 11155827860629 350 11434857809419 351 11720060400554 352 12011581798445 353 12309516762559 354 12614016192495 355 12925178129008 356 13243158297560 357 13568058146984 358 13900038392440 359 14239203954544 360 14585720635680 361 14939696960400 362 15301303986208 363 15670653911280 364 16047923150168 365 16433227709832 366 16826749539192 367 17228608527152 368 17638992260912 369 18058024654912 370 18485899118896 371 18922743666992 372 19368757642872 373 19824073309832 374 20288896134232 375 20763362709232 376 21247684740128 377 21742003302800 378 22246536540448 379 22761430096240 380 23286908669816 381 23823122633640 382 24370303450328 383 24928606307440 384 25498269557233 385 26079453370817 386 26672403201587 387 27277284297142 388 27894349344037 389 28523768838587 390 29165802923037 391 29820627439658 392 30488510121025 393 31169632337503 394 31864269642755 395 32572609033976 396 33294934029380 397 34031437442168 398 34782410991320 399 35548053412548 400 36328664774943 401 37124449930103 402 37935717545345 403 38762678699418 404 39605650810185 405 40464851387631 406 41340606857205 407 42233141273178 408 43142790230460 409 44069784539358 410 45014469227268 411 45977081982018 412 46957977431805 413 47957400358383 414 48975715266585 415 50013174158826 416 51070151588250 417 52146907005888 418 53243825298690 419 54361173495138 420 55499346997989 421 56658620649459 422 57839400660153 423 59041969823994 424 60266745348468 425 61514018220630 426 62784216950652 427 64077640862466 428 65394729961737 429 66735792163131 430 68101279284045 431 69491507976066 432 70906942072267 433 72347907224041 434 73814879603517 435 75308194017960 436 76828339190158 437 78375659351794 438 79950656114458 439 81553683296644 440 83185255614565 441 84845736755429 442 86535654889463 443 88255383737794 444 90005465152473 445 91786283180215 446 93598393712057 447 95442191296166 448 97318246098697 449 99226963467151 450 101168928215771 451 103144556674172 452 105154448545510 453 107199031453722 454 109278920375950 455 111394554416444 456 113546564080040 457 115735400274052 458 117961709424520 459 120225954439292 460 122528797928342 461 124870715129602 462 127252385247390 463 129674296054732 464 132137143618220 465 134641428590864 466 137187864324940 467 139776964562092 468 142409460222030 469 145085878491282 470 147806968289542 471 150573270469212 472 153385552241480 473 156244368488292 474 159150505162920 475 162104531406044 476 165107252210270 477 168159251355082 478 171261353336950 479 174414156807452 480 177618506078973 481 180875015067473 482 184184548375663 483 187547735430418 484 190965461447363 485 194438371764653 486 197967372704467 487 201553125771670 488 205196558723897 489 208898349650595 490 212659448253419 491 216480549466420 492 220362625280002 493 224306387903810 494 228312832136222 495 232382687736688 496 236516972667643 497 240716434678103 498 244982115434253 499 249314780958518 500 253715496983839 501 258185048264473 502 262724525155763 503 267334731432758 504 272016782453108 505 276771501485138 506 281600029455932 507 286503209431230 508 291482208299667 509 296537889406385 510 301671446190455 511 306883762590966 512 312176058997110 513 317549240443776 514 323004554876190 515 328542928745262 516 334165637969955 517 339873630934101 518 345668212148655 519 351550352266806 520 357521384822316 521 363582303264906 522 369734470792500 523 375978903999006 524 382316996185575 525 388749787638597 526 395278702421955 527 401904804868446 528 408629550262935 529 415454027549001 530 422379723905241 531 429407753257236 532 436539635149620 533 443776509065436 534 451119927612600 535 458571056214912 536 466131481024845 537 473802394004841 538 481585415568495 539 489481764607086 540 497493096297007 541 505620657073417 542 513866137606263 543 522230812283202 544 530716407784453 545 539324227077151 546 548056033608487 547 556913159346664 548 565897405032292 549 575010132285404 550 584253179917268 551 593627939628904 552 603136288850352 553 612779650032664 554 622559940017072 555 632478612453416 556 642537624158308 557 652738460662252 558 663083119577108 559 673573118776712 560 684210497242888 561 694996805899872 562 705934125941128 563 717024041812232 564 728268677515988 565 739669651745836 566 751229132171812 567 762948772226984 568 774830783863472 569 786876855994264 570 799089245740464 571 811469678001640 572 824020455694100 573 836743340470940 574 849640681953700 575 862714279064680 576 875966528781225 577 889399268082465 578 903014942228875 579 916815426794190 580 930803215990865 581 944980224789615 582 959348997312825 583 973911488481890 584 988670293010225 585 1003627406600455 586 1018785475539475 587 1034146536874640 588 1049713289173200 589 1065487811679740 590 1081472856242740 591 1097670544890940 592 1114083683480375 593 1130714437692215 594 1147565668423225 595 1164639585610930 596 1181939105932325 597 1199466484479315 598 1217224694768225 599 1235216037659890 600 1253443544276716 601 1271909562169766 602 1290617181146228 603 1309568796086746 604 1328767556270713 605 1348215904846499 606 1367917051678437 607 1387873488840098 608 1408088487582322 609 1428564589873408 610 1449305129490842 611 1470312698966618 612 1491590695435217 613 1513141762986503 614 1534969363272917 615 1557076192637394 616 1579465778102628 617 1602140869276766 618 1625105059749548 619 1648361153108826 620 1671912810378837 621 1695762890172351 622 1719915122173833 623 1744372420747866 624 1769138585136963 625 1794216586528809 626 1819610294971797 627 1845322739231328 628 1871357861082762 629 1897718747959638 630 1924409414649798 631 1951433008030044 632 1978793616838005 633 2006494448518989 634 2034539667076455 635 2062932541312698 636 2091677311466325 637 2120777308849419 638 2150236851275205 639 2180059333383294 640 2210249151555489 641 2240809764932079 642 2271745649842515 643 2303060330767284 644 2334758364994770 645 2366843343555438 646 2399319906107850 647 2432191711086324 648 2465463481564600 649 2499138944619724 650 2533222908176664 651 2567719168839924 652 2602632620456770 653 2637967130419654 654 2673727679975770 655 2709918208213348 656 2746543784869060 657 2783608422025904 658 2821117279421540 659 2859074443056964 660 2897485163795850 661 2936353602886870 662 2975685103857458 663 3015483904159700 664 3055755441137368 665 3096504029798572 666 3137735202884792 667 3179453353940372 668 3221664112276762 669 3264371951367582 670 3307582598711266 671 3351300608707412 672 3395531808250997 673 3440280834092977 674 3485553614169607 675 3531354868614122 676 3577690627642703 677 3624565696220545 678 3671986208534223 679 3719957055437710 680 3768484476347561 681 3817573449498635 682 3867230321265403 683 3917460158338060 684 3968269415347758 685 4019663248966182 686 4071648223838362 687 4124229587727912 688 4177414016623187 689 4231206850931607 690 4285614879789957 691 4340643537387278 692 4396299727360475 693 4452588979276573 694 4509518313117055 695 4567093354983566 696 4625321242594980 697 4684207700219738 698 4743759985189420 699 4803983921133718 700 4864886886422063 701 4926474805704773 702 4988755180314595 703 5051734037145838 704 5115419001943310 705 5179816205551296 706 5244933400093430 707 5310776821607398 708 5377354350087535 709 5444672328508553 710 5512738766734763 711 5581560115961038 712 5651144517447580 713 5721498532381778 714 5792630435471460 715 5864546899210166 716 5937256333304275 717 6010765523374633 718 6085083016221215 719 6160215711927158 720 6236172295982159 721 6312959784792329 722 6390587004666353 723 6469061089709964 724 6548391008682768 725 6628584015281120 726 6709649222899652 727 6791594006234136 728 6874427624972637 729 6958157576752401 730 7042793269784415 731 7128342326078886 732 7214814304075467 733 7302216952140861 734 7390559981208867 735 7479851267477850 736 7570100676119133 737 7661316213178239 738 7753507900386783 739 7846683875146464 740 7940854317520560 741 8036027498335824 742 8132213758357488 743 8229421503370464 744 8327661236662848 745 8426941501090080 746 8527272964871232 747 8628664309511136 748 8731126370020272 749 8834667968698896 750 8939300109816816 751 9045031758084192 752 9151874088920160 753 9259836211646592 754 9368929475349600 755 9479163135602784 756 9590548717101040 757 9703095623917072 758 9816815558911920 759 9931718076345312 760 10047815059227712 761 10165116214288672 762 10283633607307840 763 10403377099209952 764 10524358940558320 765 10646589148813904 766 10770080161995440 767 10894842155852512 768 11020887757927905 769 11148227304648577 770 11276873615794787 771 11406837190273382 772 11538131042214205 773 11670765835429987 774 11804754781178645 775 11940108710020634 776 12076841032486945 777 12214962748372527 778 12354487470314275 779 12495426369212072 780 12637793262010268 781 12781599493250368 782 12926859087060688 783 13073583563547188 784 13221787156269263 785 13371481563473143 786 13522681231093617 787 13675398037481290 788 13829646643228097 789 13985439109428215 790 14142790314331789 791 14301712503770890 792 14462220775994652 793 14624327564264430 794 14788048189875172 795 14953395275566578 796 15120384368067893 797 15289028282329623 798 15459342793632753 799 15631340911230938 800 15805038641381834 801 15980449190440768 802 16157588798818738 803 16336470872096978 804 16517111887326333 805 16699525452167003 806 16883728283534257 807 17069734193348650 808 17257560140926292 809 17447220145344230 810 17638731411617500 811 17832108168206386 812 18027367868399585 813 18224524953005571 814 18423597126946565 815 18624599045639602 816 18827548668279355 817 19032460867913321 818 19239353861418605 819 19448242741793176 820 19659145986287686 821 19872078910917626 822 20087060256793650 823 20304105565316276 824 20523233844187525 825 20744460863331637 826 20967805900592855 827 21193284956822066 828 21420917582803985 829 21650720013514271 830 21882712076281361 831 22116910242670806 832 22353334619407545 833 22592001917892431 834 22832932527929675 835 23076143403270252 836 23321655219692670 837 23569485176617986 838 23819654239548870 839 24072179856128556 840 24327083284548552 841 24584382224056212 842 24844098229336488 843 25106249253857772 844 25370857151820078 845 25637940134344266 846 25907520359032662 847 26179616297327484 848 26454250413299292 849 26731441442220624 850 27011212158587388 851 27293581564210524 852 27578572747149702 853 27866204979327834 854 28156501666382622 855 28449482353124556 856 28745170765967208 857 29043586726233972 858 29344754285214408 859 29648693543574732 860 29955428880724758 861 30264980680379442 862 30577373654241678 863 30892628471946252 864 31210770180808813 865 31531819740157201 866 31855802537152287 867 32182739823756354 868 32512657330357147 869 32845576605378709 870 33181523726757259 871 33520520542376710 872 33862593481152025 873 34207764694338035 874 34556060966225675 875 34907504754482020 876 35262123202282650 877 35619939077688010 878 35980979887217750 879 36345268712440160 880 36712833426792235 881 37083697429387735 882 37457888965132925 883 37835431753860710 884 38216354415570775 885 38600680994939745 886 38988440491691275 887 39379657278564710 888 39774360738713300 889 40172575577136610 890 40574331565112860 891 40979653743196910 892 41388572274564875 893 41801112539583385 894 42217305098117775 895 42637175673703270 896 43060755226720550 897 43488069828220160 898 43919150843971150 899 44354024695943710 900 44792723159206011 901 45235273011070461 902 45681706440844903 903 46132050584667366 904 46586338050066188 905 47044596336489114 906 47506858474725012 907 47973152331079118 908 48443511363637247 909 48917963810139853 910 49396543561094587 911 49879279229274638 912 50366205141733767 913 50857350290934473 914 51352749445671817 915 51852431981777284 916 52356433113984428 917 52864782606214436 918 53377516124437648 919 53894663824411696 920 54416261827598957 921 54942340686411321 922 55472936983189583 923 56008081670798686 924 56547811796804263 925 57092158719424049 926 57641159956908047 927 58194847276710898 928 58753258672189237 929 59316426325001183 930 59884388709176343 931 60457178424530264 932 61034834430248380 933 61617389749370884 934 62204883831896780 935 62797350128099288 936 63394828583368400 937 63997353080362664 938 64604964065596880 939 65217695858211864 940 65835589410503484 941 66458679483316724 942 67087007540572940 943 67720608788990904 944 68359525208836920 945 69003792458029728 946 69653453039119800 947 70308543065452344 948 70969105566679500 949 71635177116987444 950 72306801279148284 951 72984015092507544 952 73666862657856720 953 74355381485187624 954 75049616219443920 955 75749604845657688 956 76455392557890060 957 77167017821808324 958 77884526386822140 959 78607957203687384 960 79337356582229145 961 80072763963978465 962 80814226225489083 963 81561783303615870 964 82315482646793193 965 83075364692961687 966 83841477468868017 967 84613861918165842 968 85392566651134737 969 86177633123015127 970 86969110534153011 971 87767040856064832 972 88571473884488872 973 89382452113186372 974 90200025939906732 975 91024238385444012 976 91855140454972903 977 92692775702367415 978 93537195746968873 979 94388444680600930 980 95246574742257181 981 96111630567873755 982 96983665022943353 983 97862723292448930 984 98748858873976908 985 99642117507818422 986 100542553330589012 987 101450212642924682 988 102365150226156337 989 103287412947607627 990 104217056240386877 991 105154127543626898 992 106098682947974050 993 107050770470832768 994 108010446867558730 995 108977760739016906 996 109952769511145705 997 110935522374835183 998 111926077433869645 999 112924484474459138 1000 113930802284202308