0 0 1 1 2 22 3 183 4 820 5 2605 6 6666 7 14707 8 29128 9 53145 10 90910 11 147631 12 229692 13 344773 14 501970 15 711915 16 986896 17 1340977 18 1790118 19 2352295 20 3047620 21 3898461 22 4929562 23 6168163 24 7644120 25 9390025 26 11441326 27 13836447 28 16616908 29 19827445 30 23516130 31 27734491 32 32537632 33 37984353 34 44137270 35 51062935 36 58831956 37 67519117 38 77203498 39 87968595 40 99902440 41 113097721 42 127651902 43 143667343 44 161251420 45 180516645 46 201580786 47 224566987 48 249603888 49 276825745 50 306372550 51 338390151 52 373030372 53 410451133 54 450816570 55 494297155 56 541069816 57 591318057 58 645232078 59 703008895 60 764852460 61 830973781 62 901591042 63 976929723 64 1057222720 65 1142710465 66 1233641046 67 1330270327 68 1432862068 69 1541688045 70 1657028170 71 1779170611 72 1908411912 73 2045057113 74 2189419870 75 2341822575 76 2502596476 77 2672081797 78 2850627858 79 3038593195 80 3236345680 81 3444262641 82 3662730982 83 3892147303 84 4132918020 85 4385459485 86 4650198106 87 4927570467 88 5218023448 89 5522014345 90 5840010990 91 6172491871 92 6519946252 93 6882874293 94 7261787170 95 7657207195 96 8069667936 97 8499714337 98 8947902838 99 9414801495 100 9900990100 101 10407060301 102 10933615722 103 11481272083 104 12050657320 105 12642411705 106 13257187966 107 13895651407 108 14558480028 109 15246364645 110 15960009010 111 16700129931 112 17467457392 113 18262734673 114 19086718470 115 19940179015 116 20823900196 117 21738679677 118 22685329018 119 23664673795 120 24677553720 121 25724822761 122 26807349262 123 27926016063 124 29081720620 125 30275375125 126 31507906626 127 32780257147 128 34093383808 129 35448258945 130 36845870230 131 38287220791 132 39773329332 133 41305230253 134 42883973770 135 44510626035 136 46186269256 137 47912001817 138 49688938398 139 51518210095 140 53400964540 141 55338366021 142 57331595602 143 59381851243 144 61490347920 145 63658317745 146 65887010086 147 68177691687 148 70531646788 149 72950177245 150 75434602650 151 77986260451 152 80606506072 153 83296713033 154 86058273070 155 88892596255 156 91801111116 157 94785264757 158 97846522978 159 100986370395 160 104206310560 161 107507866081 162 110892578742 163 114362009623 164 117917739220 165 121561367565 166 125294514346 167 129118819027 168 133035940968 169 137047559545 170 141155374270 171 145361104911 172 149666491612 173 154073295013 174 158583296370 175 163198297675 176 167920121776 177 172750612497 178 177691634758 179 182745074695 180 187912839780 181 193196858941 182 198599082682 183 204121483203 184 209766054520 185 215534812585 186 221429795406 187 227453063167 188 233606698348 189 239892805845 190 246313513090 191 252870970171 192 259567349952 193 266404848193 194 273385683670 195 280512098295 196 287786357236 197 295210749037 198 302787585738 199 310519202995 200 318407960200 201 326456240601 202 334666451422 203 343041023983 204 351582413820 205 360293100805 206 369175589266 207 378232408107 208 387466110928 209 396879276145 210 406474507110 211 416254432231 212 426221705092 213 436379004573 214 446729034970 215 457274526115 216 468018233496 217 478962938377 218 490111447918 219 501466595295 220 513031239820 221 524808267061 222 536800588962 223 549011143963 224 561442897120 225 574098840225 226 586981991926 227 600095397847 228 613442130708 229 627025290445 230 640848004330 231 654913427091 232 669224741032 233 683785156153 234 698597910270 235 713666269135 236 728993526556 237 744583004517 238 760438053298 239 776562051595 240 792958406640 241 809630554321 242 826581959302 243 843816115143 244 861336544420 245 879146798845 246 897250459386 247 915651136387 248 934352469688 249 953358128745 250 972671812750 251 992297250751 252 1012238201772 253 1032498454933 254 1053081829570 255 1073992175355 256 1095233372416 257 1116809331457 258 1138723993878 259 1160981331895 260 1183585348660 261 1206540078381 262 1229849586442 263 1253517969523 264 1277549355720 265 1301947904665 266 1326717807646 267 1351863287727 268 1377388599868 269 1403298031045 270 1429595900370 271 1456286559211 272 1483374391312 273 1510863812913 274 1538759272870 275 1567065252775 276 1595786267076 277 1624926863197 278 1654491621658 279 1684485156195 280 1714912113880 281 1745777175241 282 1777085054382 283 1808840499103 284 1841048291020 285 1873713245685 286 1906840212706 287 1940434075867 288 1974499753248 289 2009042197345 290 2044066395190 291 2079577368471 292 2115580173652 293 2152079902093 294 2189081680170 295 2226590669395 296 2264612066536 297 2303151103737 298 2342213048638 299 2381803204495 300 2421926910300 301 2462589540901 302 2503796507122 303 2545553255883 304 2587865270320 305 2630738069905 306 2674177210566 307 2718188284807 308 2762776921828 309 2807948787645 310 2853709585210 311 2900065054531 312 2947020972792 313 2994583154473 314 3042757451470 315 3091549753215 316 3140965986796 317 3191012117077 318 3241694146818 319 3293018116795 320 3344990105920 321 3397616231361 322 3450902648662 323 3504855551863 324 3559481173620 325 3614785785325 326 3670775697226 327 3727457258547 328 3784836857608 329 3842920921945 330 3901715918430 331 3961228353391 332 4021464772732 333 4082431762053 334 4144135946770 335 4206583992235 336 4269782603856 337 4333738527217 338 4398458548198 339 4463949493095 340 4530218228740 341 4597271662621 342 4665116743002 343 4733760459043 344 4803209840920 345 4873471959945 346 4944553928686 347 5016462901087 348 5089206072588 349 5162790680245 350 5237224002850 351 5312513361051 352 5388666117472 353 5465689676833 354 5543591486070 355 5622379034455 356 5702059853716 357 5782641518157 358 5864131644778 359 5946537893395 360 6029867966760 361 6114129610681 362 6199330614142 363 6285478809423 364 6372582072220 365 6460648321765 366 6549685520946 367 6639701676427 368 6730704838768 369 6822703102545 370 6915704606470 371 7009717533511 372 7104750111012 373 7200810610813 374 7297907349370 375 7396048687875 376 7495243032376 377 7595498833897 378 7696824588558 379 7799228837695 380 7902720167980 381 8007307211541 382 8112998646082 383 8219803195003 384 8327729627520 385 8436786758785 386 8546983450006 387 8658328608567 388 8770831188148 389 8884500188845 390 8999344657290 391 9115373686771 392 9232596417352 393 9351022035993 394 9470659776670 395 9591518920495 396 9713608795836 397 9836938778437 398 9961518291538 399 10087356805995 400 10214463840400 401 10342848961201 402 10472521782822 403 10603491967783 404 10735769226820 405 10869363319005 406 11004284051866 407 11140541281507 408 11278144912728 409 11417104899145 410 11557431243310 411 11699133996831 412 11842223260492 413 11986709184373 414 12132601967970 415 12279911860315 416 12428649160096 417 12578824215777 418 12730447425718 419 12883529238295 420 13038080152020 421 13194110715661 422 13351631528362 423 13510653239763 424 13671186550120 425 13833242210425 426 13996831022526 427 14161963839247 428 14328651564508 429 14496905153445 430 14666735612530 431 14838153999691 432 15011171424432 433 15185799047953 434 15362048083270 435 15539929795335 436 15719455501156 437 15900636569917 438 16083484423098 439 16268010534595 440 16454226430840 441 16642143690921 442 16831773946702 443 17023128882943 444 17216220237420 445 17411059801045 446 17607659417986 447 17806030985787 448 18006186455488 449 18208137831745 450 18411897172950 451 18617476591351 452 18824888253172 453 19034144378733 454 19245257242570 455 19458239173555 456 19673102555016 457 19889859824857 458 20108523475678 459 20329106054895 460 20551620164860 461 20776078462981 462 21002493661842 463 21230878529323 464 21461245888720 465 21693608618865 466 21927979654246 467 22164371985127 468 22402798657668 469 22643272774045 470 22885807492570 471 23130416027811 472 23377111650712 473 23625907688713 474 23876817525870 475 24129854602975 476 24385032417676 477 24642364524597 478 24901864535458 479 25163546119195 480 25427423002080 481 25693508967841 482 25961817857782 483 26232363570903 484 26505160064020 485 26780221351885 486 27057561507306 487 27337194661267 488 27619135003048 489 27903396780345 490 28189994299390 491 28478941925071 492 28770254081052 493 29063945249893 494 29360029973170 495 29658522851595 496 29959438545136 497 30262791773137 498 30568597314438 499 30876870007495 500 31187624750500 501 31500876501501 502 31816640278522 503 32134931159683 504 32455764283320 505 32779154848105 506 33105118113166 507 33433669398207 508 33764824083628 509 34098597610645 510 34435005481410 511 34774063259131 512 35115786568192 513 35460191094273 514 35807292584470 515 36157106847415 516 36509649753396 517 36864937234477 518 37222985284618 519 37583809959795 520 37947427378120 521 38313853719961 522 38683105228062 523 39055198207663 524 39430149026620 525 39807974115525 526 40188689967826 527 40572313139947 528 40958860251408 529 41348347984945 530 41740793086630 531 42136212365991 532 42534622696132 533 42936041013853 534 43340484319770 535 43747969678435 536 44158514218456 537 44572135132617 538 44988849677998 539 45408675176095 540 45831629012940 541 46257728639221 542 46686991570402 543 47119435386843 544 47555077733920 545 47993936322145 546 48436028927286 547 48881373390487 548 49329987618388 549 49781889583245 550 50237097323050 551 50695628941651 552 51157502608872 553 51622736560633 554 52091349099070 555 52563358592655 556 53038783476316 557 53517642251557 558 53999953486578 559 54485735816395 560 54975007942960 561 55467788635281 562 55964096729542 563 56463951129223 564 56967370805220 565 57474374795965 566 57984982207546 567 58499212213827 568 59017084056568 569 59538617045545 570 60063830558670 571 60592744042111 572 61125377010412 573 61661749046613 574 62201879802370 575 62745788998075 576 63293496422976 577 63845021935297 578 64400385462358 579 64959607000695 580 65522706616180 581 66089704444141 582 66660620689482 583 67235475626803 584 67814289600520 585 68397083024985 586 68983876384606 587 69574690233967 588 70169545197948 589 70768461971845 590 71371461321490 591 71978564083371 592 72589791164752 593 73205163543793 594 73824702269670 595 74448428462695 596 75076363314436 597 75708528087837 598 76344944117338 599 76985632808995 600 77630615640600 601 78279914161801 602 78933549994222 603 79591544831583 604 80253920439820 605 80920698657205 606 81591901394466 607 82267550634907 608 82947668434528 609 83632276922145 610 84321398299510 611 85015054841431 612 85713268895892 613 86416062884173 614 87123459300970 615 87835480714515 616 88552149766696 617 89273489173177 618 89999521723518 619 90730270281295 620 91465757784220 621 92206007244261 622 92951041747762 623 93700884455563 624 94455558603120 625 95215087500625 626 95979494533126 627 96748803160647 628 97523036918308 629 98302219416445 630 99086374340730 631 99875525452291 632 100669696587832 633 101468911659753 634 102273194656270 635 103082569641535 636 103897060755756 637 104716692215317 638 105541488312898 639 106371473417595 640 107206671975040 641 108047108507521 642 108892807614102 643 109743793970743 644 110600092330420 645 111461727523245 646 112328724456586 647 113201108115187 648 114078903561288 649 114962135934745 650 115850830453150 651 116745012411951 652 117644707184572 653 118549940222533 654 119460737055570 655 120377123291755 656 121299124617616 657 122226766798257 658 123160075677478 659 124099077177895 660 125043797301060 661 125994262127581 662 126950497817242 663 127912530609123 664 128880386821720 665 129854092853065 666 130833675180846 667 131819160362527 668 132810575035468 669 133807945917045 670 134811299804770 671 135820663576411 672 136836064190112 673 137857528684513 674 138885084178870 675 139918757873175 676 140958577048276 677 142004569065997 678 143056761369258 679 144115181482195 680 145179857010280 681 146250815640441 682 147328085141182 683 148411693362703 684 149501668237020 685 150598037778085 686 151700830081906 687 152810073326667 688 153925795772848 689 155048025763345 690 156176791723590 691 157312122161671 692 158454045668452 693 159602590917693 694 160757786666170 695 161919661753795 696 163088245103736 697 164263565722537 698 165445652700238 699 166634535210495 700 167830242510700 701 169032803942101 702 170242248929922 703 171458606983483 704 172681907696320 705 173912180746305 706 175149455895766 707 176393762991607 708 177645131965428 709 178903592833645 710 180169175697610 711 181441910743731 712 182721828243592 713 184008958554073 714 185303332117470 715 186604979461615 716 187913931199996 717 189230218031877 718 190553870742418 719 191884920202795 720 193223397370320 721 194569333288561 722 195922759087462 723 197283705983463 724 198652205279620 725 200028288365725 726 201411986718426 727 202803331901347 728 204202355565208 729 205609089447945 730 207023565374830 731 208445815258591 732 209875871099532 733 211313764985653 734 212759529092770 735 214213195684635 736 215674797113056 737 217144365818017 738 218621934327798 739 220107535259095 740 221601201317140 741 223102965295821 742 224612860077802 743 226130918634643 744 227657174026920 745 229191659404345 746 230734408005886 747 232285453159887 748 233844828284188 749 235412566886245 750 236988702563250 751 238573269002251 752 240166299980272 753 241767829364433 754 243377891112070 755 244996519270855 756 246623747978916 757 248259611464957 758 249904144048378 759 251557380139395 760 253219354239160 761 254890100939881 762 256569654924942 763 258258050969023 764 259955323938220 765 261661508790165 766 263376640574146 767 265100754431227 768 266833885594368 769 268576069388545 770 270327341230870 771 272087736630711 772 273857291189812 773 275636040602413 774 277424020655370 775 279221267228275 776 281027816293576 777 282843703916697 778 284668966256158 779 286503639563695 780 288347760184380 781 290201364556741 782 292064489212882 783 293937170778603 784 295819445973520 785 297711351611185 786 299612924599206 787 301524201939367 788 303445220727748 789 305376018154845 790 307316631505690 791 309267098159971 792 311227455592152 793 313197741371593 794 315177993162670 795 317168248724895 796 319168545913036 797 321178922677237 798 323199417063138 799 325230067211995 800 327270911360800 801 329321987842401 802 331383335085622 803 333454991615383 804 335536996052820 805 337629387115405 806 339732203617066 807 341845484468307 808 343969268676328 809 346103595345145 810 348248503675710 811 350404032966031 812 352570222611292 813 354747112103973 814 356934741033970 815 359133149088715 816 361342376053296 817 363562461810577 818 365793446341318 819 368035369724295 820 370288272136420 821 372552193852861 822 374827175247162 823 377113256791363 824 379410479056120 825 381718882710825 826 384038508523726 827 386369397362047 828 388711590192108 829 391065128079445 830 393430052188930 831 395806403784891 832 398194224231232 833 400593554991553 834 403004437629270 835 405426913807735 836 407861025290356 837 410306813940717 838 412764321722698 839 415233590700595 840 417714663039240 841 420207581004121 842 422712386961502 843 425229123378543 844 427757832823420 845 430298557965445 846 432851341575186 847 435416226524587 848 437993255787088 849 440582472437745 850 443183919653350 851 445797640712551 852 448423678995972 853 451062077986333 854 453712881268570 855 456376132529955 856 459051875560216 857 461740154251657 858 464441012599278 859 467154494700895 860 469880644757260 861 472619507072181 862 475371126052642 863 478135546208923 864 480912812154720 865 483702968607265 866 486506060387446 867 489322132419927 868 492151229733268 869 494993397460045 870 497848680836970 871 500717125205011 872 503598776009512 873 506493678800313 874 509401879231870 875 512323423063375 876 515258356158876 877 518206724487397 878 521168574123058 879 524143951245195 880 527132902138480 881 530135473193041 882 533151710904582 883 536181661874503 884 539225372810020 885 542282890524285 886 545354261936506 887 548439534072067 888 551538754062648 889 554651969146345 890 557779226667790 891 560920574078271 892 564076058935852 893 567245728905493 894 570429631759170 895 573627815375995 896 576840327742336 897 580067216951937 898 583308531206038 899 586564318813495 900 589834628190900 901 593119507862701 902 596419006461322 903 599733172727283 904 603062055509320 905 606405703764505 906 609764166558366 907 613137493065007 908 616525732567228 909 619928934456645 910 623347148233810 911 626780423508331 912 630228809998992 913 633692357533873 914 637171116050470 915 640665135595815 916 644174466326596 917 647699158509277 918 651239262520218 919 654794828845795 920 658365908082520 921 661952550937161 922 665554808226862 923 669172730879263 924 672806369932620 925 676455776535925 926 680121001949026 927 683802097542747 928 687499114799008 929 691212105310945 930 694941120783030 931 698686213031191 932 702447433982932 933 706224835677453 934 710018470265770 935 713828390010835 936 717654647287656 937 721497294583417 938 725356384497598 939 729231969742095 940 733124103141340 941 737032837632421 942 740958226265202 943 744900322202443 944 748859178719920 945 752834849206545 946 756827387164486 947 760836846209287 948 764863280069988 949 768906742589245 950 772967287723450 951 777044969542851 952 781139842231672 953 785251960088233 954 789381377525070 955 793528149069055 956 797692329361516 957 801873973158357 958 806073135330178 959 810289870862395 960 814524234855360 961 818776282524481 962 823046069200342 963 827333650328823 964 831639081471220 965 835962418304365 966 840303716620746 967 844663032328627 968 849040421452168 969 853435940131545 970 857849644623070 971 862281591299311 972 866731836649212 973 871200437278213 974 875687449908370 975 880192931378475 976 884716938644176 977 889259528778097 978 893820758969958 979 898400686526695 980 902999368872580 981 907616863549341 982 912253228216282 983 916908520650403 984 921582798746520 985 926276120517385 986 930988544093806 987 935720127724767 988 940470929777548 989 945241008737845 990 950030423209890 991 954839231916571 992 959667493699552 993 964515267519393 994 969382612455670 995 974269587707095 996 979176252591636 997 984102666546637 998 989048889128938 999 994014980014995 1000 999000999001000