0 1 1 18 2 112 3 403 4 1071 5 2356 6 4558 7 8037 8 13213 9 20566 10 30636 11 44023 12 61387 13 83448 14 110986 15 144841 16 185913 17 235162 18 293608 19 362331 20 442471 21 535228 22 641862 23 763693 24 902101 25 1058526 26 1234468 27 1431487 28 1651203 29 1895296 30 2165506 31 2463633 32 2791537 33 3151138 34 3544416 35 3973411 36 4440223 37 4947012 38 5495998 39 6089461 40 6729741 41 7419238 42 8160412 43 8955783 44 9807931 45 10719496 46 11693178 47 12731737 48 13837993 49 15014826 50 16265176 51 17592043 52 18998487 53 20487628 54 22062646 55 23726781 56 25483333 57 27335662 58 29287188 59 31341391 60 33501811 61 35772048 62 38155762 63 40656673 64 43278561 65 46025266 66 48900688 67 51908787 68 55053583 69 58339156 70 61769646 71 65349253 72 69082237 73 72972918 74 77025676 75 81244951 76 85635243 77 90201112 78 94947178 79 99878121 80 104998681 81 110313658 82 115827912 83 121546363 84 127473991 85 133615836 86 139976998 87 146562637 88 153377973 89 160428286 90 167718916 91 175255263 92 183042787 93 191087008 94 199393506 95 207967921 96 216815953 97 225943362 98 235355968 99 245059651 100 255060351 101 265364068 102 275976862 103 286904853 104 298154221 105 309731206 106 321642108 107 333893287 108 346491163 109 359442216 110 372752986 111 386430073 112 400480137 113 414909898 114 429726136 115 444935691 116 460545463 117 476562412 118 492993558 119 509845981 120 527126821 121 544843278 122 563002612 123 581612143 124 600679251 125 620211376 126 640216018 127 660700737 128 681673153 129 703140946 130 725111856 131 747593683 132 770594287 133 794121588 134 818183566 135 842788261 136 867943773 137 893658262 138 919939948 139 946797111 140 974238091 141 1002271288 142 1030905162 143 1060148233 144 1090009081 145 1120496346 146 1151618728 147 1183384987 148 1215803943 149 1248884476 150 1282635526 151 1317066093 152 1352185237 153 1388002078 154 1424525796 155 1461765631 156 1499730883 157 1538430912 158 1577875138 159 1618073041 160 1659034161 161 1700768098 162 1743284512 163 1786593123 164 1830703711 165 1875626116 166 1921370238 167 1967946037 168 2015363533 169 2063632806 170 2112763996 171 2162767303 172 2213652987 173 2265431368 174 2318112826 175 2371707801 176 2426226793 177 2481680362 178 2538079128 179 2595433771 180 2653755031 181 2713053708 182 2773340662 183 2834626813 184 2896923141 185 2960240686 186 3024590548 187 3089983887 188 3156431923 189 3223945936 190 3292537266 191 3362217313 192 3432997537 193 3504889458 194 3577904656 195 3652054771 196 3727351503 197 3803806612 198 3881431918 199 3960239301 200 4040240701 201 4121448118 202 4203873612 203 4287529303 204 4372427371 205 4458580056 206 4545999658 207 4634698537 208 4724689113 209 4815983866 210 4908595336 211 5002536123 212 5097818887 213 5194456348 214 5292461286 215 5391846541 216 5492625013 217 5594809662 218 5698413508 219 5803449631 220 5909931171 221 6017871328 222 6127283362 223 6238180593 224 6350576401 225 6464484226 226 6579917568 227 6696889987 228 6815415103 229 6935506596 230 7057178206 231 7180443733 232 7305317037 233 7431812038 234 7559942716 235 7689723111 236 7821167323 237 7954289512 238 8089103898 239 8225624761 240 8363866441 241 8503843338 242 8645569912 243 8789060683 244 8934330231 245 9081393196 246 9230264278 247 9380958237 248 9533489893 249 9687874126 250 9844125876 251 10002260143 252 10162291987 253 10324236528 254 10488108946 255 10653924481 256 10821698433 257 10991446162 258 11163183088 259 11336924691 260 11512686511 261 11690484148 262 11870333262 263 12052249573 264 12236248861 265 12422346966 266 12610559788 267 12800903287 268 12993393483 269 13188046456 270 13384878346 271 13583905353 272 13785143737 273 13988609818 274 14194319976 275 14402290651 276 14612538343 277 14825079612 278 15039931078 279 15257109421 280 15476631381 281 15698513758 282 15922773412 283 16149427263 284 16378492291 285 16609985536 286 16843924098 287 17080325137 288 17319205873 289 17560583586 290 17804475616 291 18050899363 292 18299872287 293 18551411908 294 18805535806 295 19062261621 296 19321607053 297 19583589862 298 19848227868 299 20115538951 300 20385541051 301 20658252168 302 20933690362 303 21211873753 304 21492820521 305 21776548906 306 22063077208 307 22352423787 308 22644607063 309 22939645516 310 23237557686 311 23538362173 312 23842077637 313 24148722798 314 24458316436 315 24770877391 316 25086424563 317 25404976912 318 25726553458 319 26051173281 320 26378855521 321 26709619378 322 27043484112 323 27380469043 324 27720593551 325 28063877076 326 28410339118 327 28759999237 328 29112877053 329 29468992246 330 29828364556 331 30191013783 332 30556959787 333 30926222488 334 31298821866 335 31674777961 336 32054110873 337 32436840762 338 32822987848 339 33212572411 340 33605614791 341 34002135388 342 34402154662 343 34805693133 344 35212771381 345 35623410046 346 36037629828 347 36455451487 348 36876895843 349 37301983776 350 37730736226 351 38163174193 352 38599318737 353 39039190978 354 39482812096 355 39930203331 356 40381385983 357 40836381412 358 41295211038 359 41757896341 360 42224458861 361 42694920198 362 43169302012 363 43647626023 364 44129914011 365 44616187816 366 45106469338 367 45600780537 368 46099143433 369 46601580106 370 47108112696 371 47618763403 372 48133554487 373 48652508268 374 49175647126 375 49702993501 376 50234569893 377 50770398862 378 51310503028 379 51854905071 380 52403627731 381 52956693808 382 53514126162 383 54075947713 384 54642181441 385 55212850386 386 55787977648 387 56367586387 388 56951699823 389 57540341236 390 58133533966 391 58731301413 392 59333667037 393 59940654358 394 60552286956 395 61168588471 396 61789582603 397 62415293112 398 63045743818 399 63680958601 400 64320961401 401 64965776218 402 65615427112 403 66269938203 404 66929333671 405 67593637756 406 68262874758 407 68937069037 408 69616245013 409 70300427166 410 70989640036 411 71683908223 412 72383256387 413 73087709248 414 73797291586 415 74512028241 416 75231944113 417 75957064162 418 76687413408 419 77423016931 420 78163899871 421 78910087428 422 79661604862 423 80418477493 424 81180730701 425 81948389926 426 82721480668 427 83500028487 428 84284059003 429 85073597896 430 85868670906 431 86669303833 432 87475522537 433 88287352938 434 89104821016 435 89927952811 436 90756774423 437 91591312012 438 92431591798 439 93277640061 440 94129483141 441 94987147438 442 95850659412 443 96720045583 444 97595332531 445 98476546896 446 99363715378 447 100256864737 448 101156021793 449 102061213426 450 102972466576 451 103889808243 452 104813265487 453 105742865428 454 106678635246 455 107620602181 456 108568793533 457 109523236662 458 110483958988 459 111450987991 460 112424351211 461 113404076248 462 114390190762 463 115382722473 464 116381699161 465 117387148666 466 118399098888 467 119417577787 468 120442613383 469 121474233756 470 122512467046 471 123557341453 472 124608885237 473 125667126718 474 126732094276 475 127803816351 476 128882321443 477 129967638112 478 131059794978 479 132158820721 480 133264744081 481 134377593858 482 135497398912 483 136624188163 484 137757990591 485 138898835236 486 140046751198 487 141201767637 488 142363913773 489 143533218886 490 144709712316 491 145893423463 492 147084381787 493 148282616808 494 149488158106 495 150701035321 496 151921278153 497 153148916362 498 154383979768 499 155626498251 500 156876501751 501 158134020268 502 159399083862 503 160671722653 504 161951966821 505 163239846606 506 164535392308 507 165838634287 508 167149602963 509 168468328816 510 169794842386 511 171129174273 512 172471355137 513 173821415698 514 175179386736 515 176545299091 516 177919183663 517 179301071412 518 180690993358 519 182088980581 520 183495064221 521 184909275478 522 186331645612 523 187762205943 524 189200987851 525 190648022776 526 192103342218 527 193566977737 528 195038960953 529 196519323546 530 198008097256 531 199505313883 532 201011005287 533 202525203388 534 204047940166 535 205579247661 536 207119157973 537 208667703262 538 210224915748 539 211790827711 540 213365471491 541 214948879488 542 216541084162 543 218142118033 544 219752013681 545 221370803746 546 222998520928 547 224635197987 548 226280867743 549 227935563076 550 229599316926 551 231272162293 552 232954132237 553 234645259878 554 236345578396 555 238055121031 556 239773921083 557 241502011912 558 243239426938 559 244986199641 560 246742363561 561 248507952298 562 250282999512 563 252067538923 564 253861604311 565 255665229516 566 257478448438 567 259301295037 568 261133803333 569 262976007406 570 264827941396 571 266689639503 572 268561135987 573 270442465168 574 272333661426 575 274234759201 576 276145792993 577 278066797362 578 279997806928 579 281938856371 580 283889980431 581 285851213908 582 287822591662 583 289804148613 584 291795919741 585 293797940086 586 295810244748 587 297832868887 588 299865847723 589 301909216536 590 303963010666 591 306027265513 592 308102016537 593 310187299258 594 312283149256 595 314389602171 596 316506693703 597 318634459612 598 320772935718 599 322922157901 600 325082162101 601 327252984318 602 329434660612 603 331627227103 604 333830719971 605 336045175456 606 338270629858 607 340507119537 608 342754680913 609 345013350466 610 347283164736 611 349564160323 612 351856373887 613 354159842148 614 356474601886 615 358800689941 616 361138143213 617 363486998662 618 365847293308 619 368219064231 620 370602348571 621 372997183528 622 375403606362 623 377821654393 624 380251365001 625 382692775626 626 385145923768 627 387610846987 628 390087582903 629 392576169196 630 395076643606 631 397589043933 632 400113408037 633 402649773838 634 405198179316 635 407758662511 636 410331261523 637 412916014512 638 415512959698 639 418122135361 640 420743579841 641 423377331538 642 426023428912 643 428681910483 644 431352814831 645 434036180596 646 436732046478 647 439440451237 648 442161433693 649 444895032726 650 447641287276 651 450400236343 652 453171918987 653 455956374328 654 458753641546 655 461563759881 656 464386768633 657 467222707162 658 470071614888 659 472933531291 660 475808495911 661 478696548348 662 481597728262 663 484512075373 664 487439629461 665 490380430366 666 493334517988 667 496301932287 668 499282713283 669 502276901056 670 505284535746 671 508305657553 672 511340306737 673 514388523618 674 517450348576 675 520525822051 676 523614984543 677 526717876612 678 529834538878 679 532965012021 680 536109336781 681 539267553958 682 542439704412 683 545625829063 684 548825968891 685 552040164936 686 555268458298 687 558510890137 688 561767501673 689 565038334186 690 568323429016 691 571622827563 692 574936571287 693 578264701708 694 581607260406 695 584964289021 696 588335829253 697 591721922862 698 595122611668 699 598537937551 700 601967942451 701 605412668368 702 608872157362 703 612346451553 704 615835593121 705 619339624306 706 622858587408 707 626392524787 708 629941478863 709 633505492116 710 637084607086 711 640678866373 712 644288312637 713 647912988598 714 651552937036 715 655208200791 716 658878822763 717 662564845912 718 666266313258 719 669983267881 720 673715752921 721 677463811578 722 681227487112 723 685006822843 724 688801862151 725 692612648476 726 696439225318 727 700281636237 728 704139924853 729 708014134846 730 711904309956 731 715810493983 732 719732730787 733 723671064288 734 727625538466 735 731596197361 736 735583085073 737 739586245762 738 743605723648 739 747641563011 740 751693808191 741 755762503588 742 759847693662 743 763949422933 744 768067735981 745 772202677446 746 776354292028 747 780522624487 748 784707719643 749 788909622376 750 793128377626 751 797364030393 752 801616625737 753 805886208778 754 810172824696 755 814476518731 756 818797336183 757 823135322412 758 827490522838 759 831862982941 760 836252748261 761 840659864398 762 845084377012 763 849526331823 764 853985774611 765 858462751216 766 862957307538 767 867469489537 768 871999343233 769 876546914706 770 881112250096 771 885695395603 772 890296397487 773 894915302068 774 899552155726 775 904207004901 776 908879896093 777 913570875862 778 918279990828 779 923007287671 780 927752813131 781 932516614008 782 937298737162 783 942099229513 784 946918138041 785 951755509786 786 956611391848 787 961485831387 788 966378875623 789 971290571836 790 976220967366 791 981170109613 792 986138046037 793 991124824158 794 996130491556 795 1001155095871 796 1006198684803 797 1011261306112 798 1016343007618 799 1021443837201 800 1026563842801 801 1031703072418 802 1036861574112 803 1042039396003 804 1047236586271 805 1052453193156 806 1057689264958 807 1062944850037 808 1068219996813 809 1073514753766 810 1078829169436 811 1084163292423 812 1089517171387 813 1094890855048 814 1100284392186 815 1105697831641 816 1111131222313 817 1116584613162 818 1122058053208 819 1127551591531 820 1133065277271 821 1138599159628 822 1144153287862 823 1149727711293 824 1155322479301 825 1160937641326 826 1166573246868 827 1172229345487 828 1177905986803 829 1183603220496 830 1189321096306 831 1195059664033 832 1200818973537 833 1206599074738 834 1212400017616 835 1218221852211 836 1224064628623 837 1229928397012 838 1235813207598 839 1241719110661 840 1247646156541 841 1253594395638 842 1259563878412 843 1265554655383 844 1271566777131 845 1277600294296 846 1283655257578 847 1289731717737 848 1295829725593 849 1301949332026 850 1308090587976 851 1314253544443 852 1320438252487 853 1326644763228 854 1332873127846 855 1339123397581 856 1345395623733 857 1351689857662 858 1358006150788 859 1364344554591 860 1370705120611 861 1377087900448 862 1383492945762 863 1389920308273 864 1396370039761 865 1402842192066 866 1409336817088 867 1415853966787 868 1422393693183 869 1428956048356 870 1435541084446 871 1442148853653 872 1448779408237 873 1455432800518 874 1462109082876 875 1468808307751 876 1475530527643 877 1482275795112 878 1489044162778 879 1495835683321 880 1502650409481 881 1509488394058 882 1516349689912 883 1523234349963 884 1530142427191 885 1537073974636 886 1544029045398 887 1551007692637 888 1558009969573 889 1565035929486 890 1572085625716 891 1579159111663 892 1586256440787 893 1593377666608 894 1600522842706 895 1607692022721 896 1614885260353 897 1622102609362 898 1629344123568 899 1636609856851 900 1643899863151 901 1651214196468 902 1658552910862 903 1665916060453 904 1673303699421 905 1680715882006 906 1688152662508 907 1695614095287 908 1703100234763 909 1710611135416 910 1718146851786 911 1725707438473 912 1733292950137 913 1740903441498 914 1748538967336 915 1756199582491 916 1763885341863 917 1771596300412 918 1779332513158 919 1787094035181 920 1794880921621 921 1802693227678 922 1810531008612 923 1818394319743 924 1826283216451 925 1834197754176 926 1842137988418 927 1850103974737 928 1858095768753 929 1866113426146 930 1874157002656 931 1882226554083 932 1890322136287 933 1898443805188 934 1906591616766 935 1914765627061 936 1922965892173 937 1931192468262 938 1939445411548 939 1947724778311 940 1956030624891 941 1964363007688 942 1972721983162 943 1981107607833 944 1989519938281 945 1997959031146 946 2006424943128 947 2014917730987 948 2023437451543 949 2031984161676 950 2040557918326 951 2049158778493 952 2057786799237 953 2066442037678 954 2075124550996 955 2083834396431 956 2092571631283 957 2101336312912 958 2110128498738 959 2118948246241 960 2127795612961 961 2136670656498 962 2145573434512 963 2154504004723 964 2163462424911 965 2172448752916 966 2181463046638 967 2190505364037 968 2199575763133 969 2208674302006 970 2217801038796 971 2226956031703 972 2236139338987 973 2245351018968 974 2254591130026 975 2263859730601 976 2273156879193 977 2282482634362 978 2291837054728 979 2301220198971 980 2310632125831 981 2320072894108 982 2329542562662 983 2339041190413 984 2348568836341 985 2358125559486 986 2367711418948 987 2377326473887 988 2386970783523 989 2396644407136 990 2406347404066 991 2416079833713 992 2425841755537 993 2435633229058 994 2445454313856 995 2455305069571 996 2465185555903 997 2475095832612 998 2485035959518 999 2495005996501 1000 2505006003501