0 0 1 1 2 2 3 3 4 28 5 125 6 366 7 847 8 1688 9 3033 10 5050 11 7931 12 11892 13 17173 14 24038 15 32775 16 43696 17 57137 18 73458 19 93043 20 116300 21 143661 22 175582 23 212543 24 255048 25 303625 26 358826 27 421227 28 491428 29 570053 30 657750 31 755191 32 863072 33 982113 34 1113058 35 1256675 36 1413756 37 1585117 38 1771598 39 1974063 40 2193400 41 2430521 42 2686362 43 2961883 44 3258068 45 3575925 46 3916486 47 4280807 48 4669968 49 5085073 50 5527250 51 5997651 52 6497452 53 7027853 54 7590078 55 8185375 56 8815016 57 9480297 58 10182538 59 10923083 60 11703300 61 12524581 62 13388342 63 14296023 64 15249088 65 16249025 66 17297346 67 18395587 68 19545308 69 20748093 70 22005550 71 23319311 72 24691032 73 26122393 74 27615098 75 29170875 76 30791476 77 32478677 78 34234278 79 36060103 80 37958000 81 39929841 82 41977522 83 44102963 84 46308108 85 48594925 86 50965406 87 53421567 88 55965448 89 58599113 90 61324650 91 64144171 92 67059812 93 70073733 94 73188118 95 76405175 96 79727136 97 83156257 98 86694818 99 90345123 100 94109500 101 97990301 102 101989902 103 106110703 104 110355128 105 114725625 106 119224666 107 123854747 108 128618388 109 133518133 110 138556550 111 143736231 112 149059792 113 154529873 114 160149138 115 165920275 116 171845996 117 177929037 118 184172158 119 190578143 120 197149800 121 203889961 122 210801482 123 217887243 124 225150148 125 232593125 126 240219126 127 248031127 128 256032128 129 264225153 130 272613250 131 281199491 132 289986972 133 298978813 134 308178158 135 317588175 136 327212056 137 337053017 138 347114298 139 357399163 140 367910900 141 378652821 142 389628262 143 400840583 144 412293168 145 423989425 146 435932786 147 448126707 148 460574668 149 473280173 150 486246750 151 499477951 152 512977352 153 526748553 154 540795178 155 555120875 156 569729316 157 584624197 158 599809238 159 615288183 160 631064800 161 647142881 162 663526242 163 680218723 164 697224188 165 714546525 166 732189646 167 750157487 168 768454008 169 787083193 170 806049050 171 825355611 172 845006932 173 865007093 174 885360198 175 906070375 176 927141776 177 948578577 178 970384978 179 992565203 180 1015123500 181 1038064141 182 1061391422 183 1085109663 184 1109223208 185 1133736425 186 1158653706 187 1183979467 188 1209718148 189 1235874213 190 1262452150 191 1289456471 192 1316891712 193 1344762433 194 1373073218 195 1401828675 196 1431033436 197 1460692157 198 1490809518 199 1521390223 200 1552439000 201 1583960601 202 1615959802 203 1648441403 204 1681410228 205 1714871125 206 1748828966 207 1783288647 208 1818255088 209 1853733233 210 1889728050 211 1926244531 212 1963287692 213 2000862573 214 2038974238 215 2077627775 216 2116828296 217 2156580937 218 2196890858 219 2237763243 220 2279203300 221 2321216261 222 2363807382 223 2406981943 224 2450745248 225 2495102625 226 2540059426 227 2585621027 228 2631792828 229 2678580253 230 2725988750 231 2774023791 232 2822690872 233 2871995513 234 2921943258 235 2972539675 236 3023790356 237 3075700917 238 3128276998 239 3181524263 240 3235448400 241 3290055121 242 3345350162 243 3401339283 244 3458028268 245 3515422925 246 3573529086 247 3632352607 248 3691899368 249 3752175273 250 3813186250 251 3874938251 252 3937437252 253 4000689253 254 4064700278 255 4129476375 256 4195023616 257 4261348097 258 4328455938 259 4396353283 260 4465046300 261 4534541181 262 4604844142 263 4675961423 264 4747899288 265 4820664025 266 4894261946 267 4968699387 268 5043982708 269 5120118293 270 5197112550 271 5274971911 272 5353702832 273 5433311793 274 5513805298 275 5595189875 276 5677472076 277 5760658477 278 5844755678 279 5929770303 280 6015709000 281 6102578441 282 6190385322 283 6279136363 284 6368838308 285 6459497925 286 6551122006 287 6643717367 288 6737290848 289 6831849313 290 6927399650 291 7023948771 292 7121503612 293 7220071133 294 7319658318 295 7420272175 296 7521919736 297 7624608057 298 7728344218 299 7833135323 300 7938988500 301 8045910901 302 8153909702 303 8262992103 304 8373165328 305 8484436625 306 8596813266 307 8710302547 308 8824911788 309 8940648333 310 9057519550 311 9175532831 312 9294695592 313 9415015273 314 9536499338 315 9659155275 316 9782990596 317 9908012837 318 10034229558 319 10161648343 320 10290276800 321 10420122561 322 10551193282 323 10683496643 324 10817040348 325 10951832125 326 11087879726 327 11225190927 328 11363773528 329 11503635353 330 11644784250 331 11787228091 332 11930974772 333 12076032213 334 12222408358 335 12370111175 336 12519148656 337 12669528817 338 12821259698 339 12974349363 340 13128805900 341 13284637421 342 13441852062 343 13600457983 344 13760463368 345 13921876425 346 14084705386 347 14248958507 348 14414644068 349 14581770373 350 14750345750 351 14920378551 352 15091877152 353 15264849953 354 15439305378 355 15615251875 356 15792697916 357 15971651997 358 16152122638 359 16334118383 360 16517647800 361 16702719481 362 16889342042 363 17077524123 364 17267274388 365 17458601525 366 17651514246 367 17846021287 368 18042131408 369 18239853393 370 18439196050 371 18640168211 372 18842778732 373 19047036493 374 19252950398 375 19460529375 376 19669782376 377 19880718377 378 20093346378 379 20307675403 380 20523714500 381 20741472741 382 20960959222 383 21182183063 384 21405153408 385 21629879425 386 21856370306 387 22084635267 388 22314683548 389 22546524413 390 22780167150 391 23015621071 392 23252895512 393 23491999833 394 23732943418 395 23975735675 396 24220386036 397 24466903957 398 24715298918 399 24965580423 400 25217758000 401 25471841201 402 25727839602 403 25985762803 404 26245620428 405 26507422125 406 26771177566 407 27036896447 408 27304588488 409 27574263433 410 27845931050 411 28119601131 412 28395283492 413 28672987973 414 28952724438 415 29234502775 416 29518332896 417 29804224737 418 30092188258 419 30382233443 420 30674370300 421 30968608861 422 31264959182 423 31563431343 424 31864035448 425 32166781625 426 32471680026 427 32778740827 428 33087974228 429 33399390453 430 33712999750 431 34028812391 432 34346838672 433 34667088913 434 34989573458 435 35314302675 436 35641286956 437 35970536717 438 36302062398 439 36635874463 440 36971983400 441 37310399721 442 37651133962 443 37994196683 444 38339598468 445 38687349925 446 39037461686 447 39389944407 448 39744808768 449 40102065473 450 40461725250 451 40823798851 452 41188297052 453 41555230653 454 41924610478 455 42296447375 456 42670752216 457 43047535897 458 43426809338 459 43808583483 460 44192869300 461 44579677781 462 44969019942 463 45360906823 464 45755349488 465 46152359025 466 46551946546 467 46954123187 468 47358900108 469 47766288493 470 48176299550 471 48588944511 472 49004234632 473 49422181193 474 49842795498 475 50266088875 476 50692072676 477 51120758277 478 51552157078 479 51986280503 480 52423140000 481 52862747041 482 53305113122 483 53750249763 484 54198168508 485 54648880925 486 55102398606 487 55558733167 488 56017896248 489 56479899513 490 56944754650 491 57412473371 492 57883067412 493 58356548533 494 58832928518 495 59312219175 496 59794432336 497 60279579857 498 60767673618 499 61258725523 500 61752747500 501 62249751501 502 62749749502 503 63252753503 504 63758775528 505 64267827625 506 64779921866 507 65295070347 508 65813285188 509 66334578533 510 66858962550 511 67386449431 512 67917051392 513 68450780673 514 68987649538 515 69527670275 516 70070855196 517 70617216637 518 71166766958 519 71719518543 520 72275483800 521 72834675161 522 73397105082 523 73962786043 524 74531730548 525 75103951125 526 75679460326 527 76258270727 528 76840394928 529 77425845553 530 78014635250 531 78606776691 532 79202282572 533 79801165613 534 80403438558 535 81009114175 536 81618205256 537 82230724617 538 82846685098 539 83466099563 540 84088980900 541 84715342021 542 85345195862 543 85978555383 544 86615433568 545 87255843425 546 87899797986 547 88547310307 548 89198393468 549 89853060573 550 90511324750 551 91173199151 552 91838696952 553 92507831353 554 93180615578 555 93857062875 556 94537186516 557 95220999797 558 95908516038 559 96599748583 560 97294710800 561 97993416081 562 98695877842 563 99402109523 564 100112124588 565 100825936525 566 101543558846 567 102265005087 568 102990288808 569 103719423593 570 104452423050 571 105189300811 572 105930070532 573 106674745893 574 107423340598 575 108175868375 576 108932342976 577 109692778177 578 110457187778 579 111225585603 580 111997985500 581 112774401341 582 113554847022 583 114339336463 584 115127883608 585 115920502425 586 116717206906 587 117518011067 588 118322928948 589 119131974613 590 119945162150 591 120762505671 592 121584019312 593 122409717233 594 123239613618 595 124073722675 596 124912058636 597 125754635757 598 126601468318 599 127452570623 600 128307957000 601 129167641801 602 130031639402 603 130899964203 604 131772630628 605 132649653125 606 133531046166 607 134416824247 608 135307001888 609 136201593633 610 137100614050 611 138004077731 612 138911999292 613 139824393373 614 140741274638 615 141662657775 616 142588557496 617 143518988537 618 144453965658 619 145393503643 620 146337617300 621 147286321461 622 148239630982 623 149197560743 624 150160125648 625 151127340625 626 152099220626 627 153075780627 628 154057035628 629 155043000653 630 156033690750 631 157029120991 632 158029306472 633 159034262313 634 160044003658 635 161058545675 636 162077903556 637 163102092517 638 164131127798 639 165165024663 640 166203798400 641 167247464321 642 168296037762 643 169349534083 644 170407968668 645 171471356925 646 172539714286 647 173613056207 648 174691398168 649 175774755673 650 176863144250 651 177956579451 652 179055076852 653 180158652053 654 181267320678 655 182381098375 656 183500000816 657 184624043697 658 185753242738 659 186887613683 660 188027172300 661 189171934381 662 190321915742 663 191477132223 664 192637599688 665 193803334025 666 194974351146 667 196150666987 668 197332297508 669 198519258693 670 199711566550 671 200909237111 672 202112286432 673 203320730593 674 204534585698 675 205753867875 676 206978593276 677 208208778077 678 209444438478 679 210685590703 680 211932251000 681 213184435641 682 214442160922 683 215705443163 684 216974298708 685 218248743925 686 219528795206 687 220814468967 688 222105781648 689 223402749713 690 224705389650 691 226013717971 692 227327751212 693 228647505933 694 229972998718 695 231304246175 696 232641264936 697 233984071657 698 235332683018 699 236687115723 700 238047386500 701 239413512101 702 240785509302 703 242163394903 704 243547185728 705 244936898625 706 246332550466 707 247734158147 708 249141738588 709 250555308733 710 251974885550 711 253400486031 712 254832127192 713 256269826073 714 257713599738 715 259163465275 716 260619439796 717 262081540437 718 263549784358 719 265024188743 720 266504770800 721 267991547761 722 269484536882 723 270983755443 724 272489220748 725 274000950125 726 275518960926 727 277043270527 728 278573896328 729 280110855753 730 281654166250 731 283203845291 732 284759910372 733 286322379013 734 287891268758 735 289466597175 736 291048381856 737 292636640417 738 294231390498 739 295832649763 740 297440435900 741 299054766621 742 300675659662 743 302303132783 744 303937203768 745 305577890425 746 307225210586 747 308879182107 748 310539822868 749 312207150773 750 313881183750 751 315561939751 752 317249436752 753 318943692753 754 320644725778 755 322352553875 756 324067195116 757 325788667597 758 327516989438 759 329252178783 760 330994253800 761 332743232681 762 334499133642 763 336261974923 764 338031774788 765 339808551525 766 341592323446 767 343383108887 768 345180926208 769 346985793793 770 348797730050 771 350616753411 772 352442882332 773 354276135293 774 356116530798 775 357964087375 776 359818823576 777 361680757977 778 363549909178 779 365426295803 780 367309936500 781 369200849941 782 371099054822 783 373004569863 784 374917413808 785 376837605425 786 378765163506 787 380700106867 788 382642454348 789 384592224813 790 386549437150 791 388514110271 792 390486263112 793 392465914633 794 394453083818 795 396447789675 796 398450051236 797 400459887557 798 402477317718 799 404502360823 800 406535036000 801 408575362401 802 410623359202 803 412679045603 804 414742440828 805 416813564125 806 418892434766 807 420979072047 808 423073495288 809 425175723833 810 427285777050 811 429403674331 812 431529435092 813 433663078773 814 435804624838 815 437954092775 816 440111502096 817 442276872337 818 444450223058 819 446631573843 820 448820944300 821 451018354061 822 453223822782 823 455437370143 824 457659015848 825 459888779625 826 462126681226 827 464372740427 828 466626977028 829 468889410853 830 471160061750 831 473438949591 832 475726094272 833 478021515713 834 480325233858 835 482637268675 836 484957640156 837 487286368317 838 489623473198 839 491968974863 840 494322893400 841 496685248921 842 499056061562 843 501435351483 844 503823138868 845 506219443925 846 508624286886 847 511037688007 848 513459667568 849 515890245873 850 518329443250 851 520777280051 852 523233776652 853 525698953453 854 528172830878 855 530655429375 856 533146769416 857 535646871497 858 538155756138 859 540673443883 860 543199955300 861 545735310981 862 548279531542 863 550832637623 864 553394649888 865 555965589025 866 558545475746 867 561134330787 868 563732174908 869 566339028893 870 568954913550 871 571579849711 872 574213858232 873 576856959993 874 579509175898 875 582170526875 876 584841033876 877 587520717877 878 590209599878 879 592907700903 880 595615042000 881 598331644241 882 601057528722 883 603792716563 884 606537228908 885 609291086925 886 612054311806 887 614826924767 888 617608947048 889 620400399913 890 623201304650 891 626011682571 892 628831555012 893 631660943333 894 634499868918 895 637348353175 896 640206417536 897 643074083457 898 645951372418 899 648838305923 900 651734905500 901 654641192701 902 657557189102 903 660482916303 904 663418395928 905 666363649625 906 669318699066 907 672283565947 908 675258271988 909 678242838933 910 681237288550 911 684241642631 912 687255922992 913 690280151473 914 693314349938 915 696358540275 916 699412744396 917 702476984237 918 705551281758 919 708635658943 920 711730137800 921 714834740361 922 717949488682 923 721074404843 924 724209510948 925 727354829125 926 730510381526 927 733676190327 928 736852277728 929 740038665953 930 743235377250 931 746442433891 932 749659858172 933 752887672413 934 756125898958 935 759374560175 936 762633678456 937 765903276217 938 769183375898 939 772473999963 940 775775170900 941 779086911221 942 782409243462 943 785742190183 944 789085773968 945 792440017425 946 795804943186 947 799180573907 948 802566932268 949 805964040973 950 809371922750 951 812790600351 952 816220096552 953 819660434153 954 823111635978 955 826573724875 956 830046723716 957 833530655397 958 837025542838 959 840531408983 960 844048276800 961 847576169281 962 851115109442 963 854665120323 964 858226224988 965 861798446525 966 865381808046 967 868976332687 968 872582043608 969 876198963993 970 879827117050 971 883466526011 972 887117214132 973 890779204693 974 894452520998 975 898137186375 976 901833224176 977 905540657777 978 909259510578 979 912989806003 980 916731567500 981 920484818541 982 924249582622 983 928025883263 984 931813744008 985 935613188425 986 939424240106 987 943246922667 988 947081259748 989 950927275013 990 954784992150 991 958654434871 992 962535626912 993 966428592033 994 970333354018 995 974249936675 996 978178363836 997 982118659357 998 986070847118 999 990034951023 1000 994010995000