0 -1 1 0 2 21 3 182 4 819 5 2604 6 6665 7 14706 8 29127 9 53144 10 90909 11 147630 12 229691 13 344772 14 501969 15 711914 16 986895 17 1340976 18 1790117 19 2352294 20 3047619 21 3898460 22 4929561 23 6168162 24 7644119 25 9390024 26 11441325 27 13836446 28 16616907 29 19827444 30 23516129 31 27734490 32 32537631 33 37984352 34 44137269 35 51062934 36 58831955 37 67519116 38 77203497 39 87968594 40 99902439 41 113097720 42 127651901 43 143667342 44 161251419 45 180516644 46 201580785 47 224566986 48 249603887 49 276825744 50 306372549 51 338390150 52 373030371 53 410451132 54 450816569 55 494297154 56 541069815 57 591318056 58 645232077 59 703008894 60 764852459 61 830973780 62 901591041 63 976929722 64 1057222719 65 1142710464 66 1233641045 67 1330270326 68 1432862067 69 1541688044 70 1657028169 71 1779170610 72 1908411911 73 2045057112 74 2189419869 75 2341822574 76 2502596475 77 2672081796 78 2850627857 79 3038593194 80 3236345679 81 3444262640 82 3662730981 83 3892147302 84 4132918019 85 4385459484 86 4650198105 87 4927570466 88 5218023447 89 5522014344 90 5840010989 91 6172491870 92 6519946251 93 6882874292 94 7261787169 95 7657207194 96 8069667935 97 8499714336 98 8947902837 99 9414801494 100 9900990099 101 10407060300 102 10933615721 103 11481272082 104 12050657319 105 12642411704 106 13257187965 107 13895651406 108 14558480027 109 15246364644 110 15960009009 111 16700129930 112 17467457391 113 18262734672 114 19086718469 115 19940179014 116 20823900195 117 21738679676 118 22685329017 119 23664673794 120 24677553719 121 25724822760 122 26807349261 123 27926016062 124 29081720619 125 30275375124 126 31507906625 127 32780257146 128 34093383807 129 35448258944 130 36845870229 131 38287220790 132 39773329331 133 41305230252 134 42883973769 135 44510626034 136 46186269255 137 47912001816 138 49688938397 139 51518210094 140 53400964539 141 55338366020 142 57331595601 143 59381851242 144 61490347919 145 63658317744 146 65887010085 147 68177691686 148 70531646787 149 72950177244 150 75434602649 151 77986260450 152 80606506071 153 83296713032 154 86058273069 155 88892596254 156 91801111115 157 94785264756 158 97846522977 159 100986370394 160 104206310559 161 107507866080 162 110892578741 163 114362009622 164 117917739219 165 121561367564 166 125294514345 167 129118819026 168 133035940967 169 137047559544 170 141155374269 171 145361104910 172 149666491611 173 154073295012 174 158583296369 175 163198297674 176 167920121775 177 172750612496 178 177691634757 179 182745074694 180 187912839779 181 193196858940 182 198599082681 183 204121483202 184 209766054519 185 215534812584 186 221429795405 187 227453063166 188 233606698347 189 239892805844 190 246313513089 191 252870970170 192 259567349951 193 266404848192 194 273385683669 195 280512098294 196 287786357235 197 295210749036 198 302787585737 199 310519202994 200 318407960199 201 326456240600 202 334666451421 203 343041023982 204 351582413819 205 360293100804 206 369175589265 207 378232408106 208 387466110927 209 396879276144 210 406474507109 211 416254432230 212 426221705091 213 436379004572 214 446729034969 215 457274526114 216 468018233495 217 478962938376 218 490111447917 219 501466595294 220 513031239819 221 524808267060 222 536800588961 223 549011143962 224 561442897119 225 574098840224 226 586981991925 227 600095397846 228 613442130707 229 627025290444 230 640848004329 231 654913427090 232 669224741031 233 683785156152 234 698597910269 235 713666269134 236 728993526555 237 744583004516 238 760438053297 239 776562051594 240 792958406639 241 809630554320 242 826581959301 243 843816115142 244 861336544419 245 879146798844 246 897250459385 247 915651136386 248 934352469687 249 953358128744 250 972671812749 251 992297250750 252 1012238201771 253 1032498454932 254 1053081829569 255 1073992175354 256 1095233372415 257 1116809331456 258 1138723993877 259 1160981331894 260 1183585348659 261 1206540078380 262 1229849586441 263 1253517969522 264 1277549355719 265 1301947904664 266 1326717807645 267 1351863287726 268 1377388599867 269 1403298031044 270 1429595900369 271 1456286559210 272 1483374391311 273 1510863812912 274 1538759272869 275 1567065252774 276 1595786267075 277 1624926863196 278 1654491621657 279 1684485156194 280 1714912113879 281 1745777175240 282 1777085054381 283 1808840499102 284 1841048291019 285 1873713245684 286 1906840212705 287 1940434075866 288 1974499753247 289 2009042197344 290 2044066395189 291 2079577368470 292 2115580173651 293 2152079902092 294 2189081680169 295 2226590669394 296 2264612066535 297 2303151103736 298 2342213048637 299 2381803204494 300 2421926910299 301 2462589540900 302 2503796507121 303 2545553255882 304 2587865270319 305 2630738069904 306 2674177210565 307 2718188284806 308 2762776921827 309 2807948787644 310 2853709585209 311 2900065054530 312 2947020972791 313 2994583154472 314 3042757451469 315 3091549753214 316 3140965986795 317 3191012117076 318 3241694146817 319 3293018116794 320 3344990105919 321 3397616231360 322 3450902648661 323 3504855551862 324 3559481173619 325 3614785785324 326 3670775697225 327 3727457258546 328 3784836857607 329 3842920921944 330 3901715918429 331 3961228353390 332 4021464772731 333 4082431762052 334 4144135946769 335 4206583992234 336 4269782603855 337 4333738527216 338 4398458548197 339 4463949493094 340 4530218228739 341 4597271662620 342 4665116743001 343 4733760459042 344 4803209840919 345 4873471959944 346 4944553928685 347 5016462901086 348 5089206072587 349 5162790680244 350 5237224002849 351 5312513361050 352 5388666117471 353 5465689676832 354 5543591486069 355 5622379034454 356 5702059853715 357 5782641518156 358 5864131644777 359 5946537893394 360 6029867966759 361 6114129610680 362 6199330614141 363 6285478809422 364 6372582072219 365 6460648321764 366 6549685520945 367 6639701676426 368 6730704838767 369 6822703102544 370 6915704606469 371 7009717533510 372 7104750111011 373 7200810610812 374 7297907349369 375 7396048687874 376 7495243032375 377 7595498833896 378 7696824588557 379 7799228837694 380 7902720167979 381 8007307211540 382 8112998646081 383 8219803195002 384 8327729627519 385 8436786758784 386 8546983450005 387 8658328608566 388 8770831188147 389 8884500188844 390 8999344657289 391 9115373686770 392 9232596417351 393 9351022035992 394 9470659776669 395 9591518920494 396 9713608795835 397 9836938778436 398 9961518291537 399 10087356805994 400 10214463840399 401 10342848961200 402 10472521782821 403 10603491967782 404 10735769226819 405 10869363319004 406 11004284051865 407 11140541281506 408 11278144912727 409 11417104899144 410 11557431243309 411 11699133996830 412 11842223260491 413 11986709184372 414 12132601967969 415 12279911860314 416 12428649160095 417 12578824215776 418 12730447425717 419 12883529238294 420 13038080152019 421 13194110715660 422 13351631528361 423 13510653239762 424 13671186550119 425 13833242210424 426 13996831022525 427 14161963839246 428 14328651564507 429 14496905153444 430 14666735612529 431 14838153999690 432 15011171424431 433 15185799047952 434 15362048083269 435 15539929795334 436 15719455501155 437 15900636569916 438 16083484423097 439 16268010534594 440 16454226430839 441 16642143690920 442 16831773946701 443 17023128882942 444 17216220237419 445 17411059801044 446 17607659417985 447 17806030985786 448 18006186455487 449 18208137831744 450 18411897172949 451 18617476591350 452 18824888253171 453 19034144378732 454 19245257242569 455 19458239173554 456 19673102555015 457 19889859824856 458 20108523475677 459 20329106054894 460 20551620164859 461 20776078462980 462 21002493661841 463 21230878529322 464 21461245888719 465 21693608618864 466 21927979654245 467 22164371985126 468 22402798657667 469 22643272774044 470 22885807492569 471 23130416027810 472 23377111650711 473 23625907688712 474 23876817525869 475 24129854602974 476 24385032417675 477 24642364524596 478 24901864535457 479 25163546119194 480 25427423002079 481 25693508967840 482 25961817857781 483 26232363570902 484 26505160064019 485 26780221351884 486 27057561507305 487 27337194661266 488 27619135003047 489 27903396780344 490 28189994299389 491 28478941925070 492 28770254081051 493 29063945249892 494 29360029973169 495 29658522851594 496 29959438545135 497 30262791773136 498 30568597314437 499 30876870007494 500 31187624750499 501 31500876501500 502 31816640278521 503 32134931159682 504 32455764283319 505 32779154848104 506 33105118113165 507 33433669398206 508 33764824083627 509 34098597610644 510 34435005481409 511 34774063259130 512 35115786568191 513 35460191094272 514 35807292584469 515 36157106847414 516 36509649753395 517 36864937234476 518 37222985284617 519 37583809959794 520 37947427378119 521 38313853719960 522 38683105228061 523 39055198207662 524 39430149026619 525 39807974115524 526 40188689967825 527 40572313139946 528 40958860251407 529 41348347984944 530 41740793086629 531 42136212365990 532 42534622696131 533 42936041013852 534 43340484319769 535 43747969678434 536 44158514218455 537 44572135132616 538 44988849677997 539 45408675176094 540 45831629012939 541 46257728639220 542 46686991570401 543 47119435386842 544 47555077733919 545 47993936322144 546 48436028927285 547 48881373390486 548 49329987618387 549 49781889583244 550 50237097323049 551 50695628941650 552 51157502608871 553 51622736560632 554 52091349099069 555 52563358592654 556 53038783476315 557 53517642251556 558 53999953486577 559 54485735816394 560 54975007942959 561 55467788635280 562 55964096729541 563 56463951129222 564 56967370805219 565 57474374795964 566 57984982207545 567 58499212213826 568 59017084056567 569 59538617045544 570 60063830558669 571 60592744042110 572 61125377010411 573 61661749046612 574 62201879802369 575 62745788998074 576 63293496422975 577 63845021935296 578 64400385462357 579 64959607000694 580 65522706616179 581 66089704444140 582 66660620689481 583 67235475626802 584 67814289600519 585 68397083024984 586 68983876384605 587 69574690233966 588 70169545197947 589 70768461971844 590 71371461321489 591 71978564083370 592 72589791164751 593 73205163543792 594 73824702269669 595 74448428462694 596 75076363314435 597 75708528087836 598 76344944117337 599 76985632808994 600 77630615640599 601 78279914161800 602 78933549994221 603 79591544831582 604 80253920439819 605 80920698657204 606 81591901394465 607 82267550634906 608 82947668434527 609 83632276922144 610 84321398299509 611 85015054841430 612 85713268895891 613 86416062884172 614 87123459300969 615 87835480714514 616 88552149766695 617 89273489173176 618 89999521723517 619 90730270281294 620 91465757784219 621 92206007244260 622 92951041747761 623 93700884455562 624 94455558603119 625 95215087500624 626 95979494533125 627 96748803160646 628 97523036918307 629 98302219416444 630 99086374340729 631 99875525452290 632 100669696587831 633 101468911659752 634 102273194656269 635 103082569641534 636 103897060755755 637 104716692215316 638 105541488312897 639 106371473417594 640 107206671975039 641 108047108507520 642 108892807614101 643 109743793970742 644 110600092330419 645 111461727523244 646 112328724456585 647 113201108115186 648 114078903561287 649 114962135934744 650 115850830453149 651 116745012411950 652 117644707184571 653 118549940222532 654 119460737055569 655 120377123291754 656 121299124617615 657 122226766798256 658 123160075677477 659 124099077177894 660 125043797301059 661 125994262127580 662 126950497817241 663 127912530609122 664 128880386821719 665 129854092853064 666 130833675180845 667 131819160362526 668 132810575035467 669 133807945917044 670 134811299804769 671 135820663576410 672 136836064190111 673 137857528684512 674 138885084178869 675 139918757873174 676 140958577048275 677 142004569065996 678 143056761369257 679 144115181482194 680 145179857010279 681 146250815640440 682 147328085141181 683 148411693362702 684 149501668237019 685 150598037778084 686 151700830081905 687 152810073326666 688 153925795772847 689 155048025763344 690 156176791723589 691 157312122161670 692 158454045668451 693 159602590917692 694 160757786666169 695 161919661753794 696 163088245103735 697 164263565722536 698 165445652700237 699 166634535210494 700 167830242510699 701 169032803942100 702 170242248929921 703 171458606983482 704 172681907696319 705 173912180746304 706 175149455895765 707 176393762991606 708 177645131965427 709 178903592833644 710 180169175697609 711 181441910743730 712 182721828243591 713 184008958554072 714 185303332117469 715 186604979461614 716 187913931199995 717 189230218031876 718 190553870742417 719 191884920202794 720 193223397370319 721 194569333288560 722 195922759087461 723 197283705983462 724 198652205279619 725 200028288365724 726 201411986718425 727 202803331901346 728 204202355565207 729 205609089447944 730 207023565374829 731 208445815258590 732 209875871099531 733 211313764985652 734 212759529092769 735 214213195684634 736 215674797113055 737 217144365818016 738 218621934327797 739 220107535259094 740 221601201317139 741 223102965295820 742 224612860077801 743 226130918634642 744 227657174026919 745 229191659404344 746 230734408005885 747 232285453159886 748 233844828284187 749 235412566886244 750 236988702563249 751 238573269002250 752 240166299980271 753 241767829364432 754 243377891112069 755 244996519270854 756 246623747978915 757 248259611464956 758 249904144048377 759 251557380139394 760 253219354239159 761 254890100939880 762 256569654924941 763 258258050969022 764 259955323938219 765 261661508790164 766 263376640574145 767 265100754431226 768 266833885594367 769 268576069388544 770 270327341230869 771 272087736630710 772 273857291189811 773 275636040602412 774 277424020655369 775 279221267228274 776 281027816293575 777 282843703916696 778 284668966256157 779 286503639563694 780 288347760184379 781 290201364556740 782 292064489212881 783 293937170778602 784 295819445973519 785 297711351611184 786 299612924599205 787 301524201939366 788 303445220727747 789 305376018154844 790 307316631505689 791 309267098159970 792 311227455592151 793 313197741371592 794 315177993162669 795 317168248724894 796 319168545913035 797 321178922677236 798 323199417063137 799 325230067211994 800 327270911360799 801 329321987842400 802 331383335085621 803 333454991615382 804 335536996052819 805 337629387115404 806 339732203617065 807 341845484468306 808 343969268676327 809 346103595345144 810 348248503675709 811 350404032966030 812 352570222611291 813 354747112103972 814 356934741033969 815 359133149088714 816 361342376053295 817 363562461810576 818 365793446341317 819 368035369724294 820 370288272136419 821 372552193852860 822 374827175247161 823 377113256791362 824 379410479056119 825 381718882710824 826 384038508523725 827 386369397362046 828 388711590192107 829 391065128079444 830 393430052188929 831 395806403784890 832 398194224231231 833 400593554991552 834 403004437629269 835 405426913807734 836 407861025290355 837 410306813940716 838 412764321722697 839 415233590700594 840 417714663039239 841 420207581004120 842 422712386961501 843 425229123378542 844 427757832823419 845 430298557965444 846 432851341575185 847 435416226524586 848 437993255787087 849 440582472437744 850 443183919653349 851 445797640712550 852 448423678995971 853 451062077986332 854 453712881268569 855 456376132529954 856 459051875560215 857 461740154251656 858 464441012599277 859 467154494700894 860 469880644757259 861 472619507072180 862 475371126052641 863 478135546208922 864 480912812154719 865 483702968607264 866 486506060387445 867 489322132419926 868 492151229733267 869 494993397460044 870 497848680836969 871 500717125205010 872 503598776009511 873 506493678800312 874 509401879231869 875 512323423063374 876 515258356158875 877 518206724487396 878 521168574123057 879 524143951245194 880 527132902138479 881 530135473193040 882 533151710904581 883 536181661874502 884 539225372810019 885 542282890524284 886 545354261936505 887 548439534072066 888 551538754062647 889 554651969146344 890 557779226667789 891 560920574078270 892 564076058935851 893 567245728905492 894 570429631759169 895 573627815375994 896 576840327742335 897 580067216951936 898 583308531206037 899 586564318813494 900 589834628190899 901 593119507862700 902 596419006461321 903 599733172727282 904 603062055509319 905 606405703764504 906 609764166558365 907 613137493065006 908 616525732567227 909 619928934456644 910 623347148233809 911 626780423508330 912 630228809998991 913 633692357533872 914 637171116050469 915 640665135595814 916 644174466326595 917 647699158509276 918 651239262520217 919 654794828845794 920 658365908082519 921 661952550937160 922 665554808226861 923 669172730879262 924 672806369932619 925 676455776535924 926 680121001949025 927 683802097542746 928 687499114799007 929 691212105310944 930 694941120783029 931 698686213031190 932 702447433982931 933 706224835677452 934 710018470265769 935 713828390010834 936 717654647287655 937 721497294583416 938 725356384497597 939 729231969742094 940 733124103141339 941 737032837632420 942 740958226265201 943 744900322202442 944 748859178719919 945 752834849206544 946 756827387164485 947 760836846209286 948 764863280069987 949 768906742589244 950 772967287723449 951 777044969542850 952 781139842231671 953 785251960088232 954 789381377525069 955 793528149069054 956 797692329361515 957 801873973158356 958 806073135330177 959 810289870862394 960 814524234855359 961 818776282524480 962 823046069200341 963 827333650328822 964 831639081471219 965 835962418304364 966 840303716620745 967 844663032328626 968 849040421452167 969 853435940131544 970 857849644623069 971 862281591299310 972 866731836649211 973 871200437278212 974 875687449908369 975 880192931378474 976 884716938644175 977 889259528778096 978 893820758969957 979 898400686526694 980 902999368872579 981 907616863549340 982 912253228216281 983 916908520650402 984 921582798746519 985 926276120517384 986 930988544093805 987 935720127724766 988 940470929777547 989 945241008737844 990 950030423209889 991 954839231916570 992 959667493699551 993 964515267519392 994 969382612455669 995 974269587707094 996 979176252591635 997 984102666546636 998 989048889128937 999 994014980014994 1000 999000999000999