0 1 1 9 2 32 3 78 4 155 5 271 6 434 7 652 8 933 9 1285 10 1716 11 2234 12 2847 13 3563 14 4390 15 5336 16 6409 17 7617 18 8968 19 10470 20 12131 21 13959 22 15962 23 18148 24 20525 25 23101 26 25884 27 28882 28 32103 29 35555 30 39246 31 43184 32 47377 33 51833 34 56560 35 61566 36 66859 37 72447 38 78338 39 84540 40 91061 41 97909 42 105092 43 112618 44 120495 45 128731 46 137334 47 146312 48 155673 49 165425 50 175576 51 186134 52 197107 53 208503 54 220330 55 232596 56 245309 57 258477 58 272108 59 286210 60 300791 61 315859 62 331422 63 347488 64 364065 65 381161 66 398784 67 416942 68 435643 69 454895 70 474706 71 495084 72 516037 73 537573 74 559700 75 582426 76 605759 77 629707 78 654278 79 679480 80 705321 81 731809 82 758952 83 786758 84 815235 85 844391 86 874234 87 904772 88 936013 89 967965 90 1000636 91 1034034 92 1068167 93 1103043 94 1138670 95 1175056 96 1212209 97 1250137 98 1288848 99 1328350 100 1368651 101 1409759 102 1451682 103 1494428 104 1538005 105 1582421 106 1627684 107 1673802 108 1720783 109 1768635 110 1817366 111 1866984 112 1917497 113 1968913 114 2021240 115 2074486 116 2128659 117 2183767 118 2239818 119 2296820 120 2354781 121 2413709 122 2473612 123 2534498 124 2596375 125 2659251 126 2723134 127 2788032 128 2853953 129 2920905 130 2988896 131 3057934 132 3128027 133 3199183 134 3271410 135 3344716 136 3419109 137 3494597 138 3571188 139 3648890 140 3727711 141 3807659 142 3888742 143 3970968 144 4054345 145 4138881 146 4224584 147 4311462 148 4399523 149 4488775 150 4579226 151 4670884 152 4763757 153 4857853 154 4953180 155 5049746 156 5147559 157 5246627 158 5346958 159 5448560 160 5551441 161 5655609 162 5761072 163 5867838 164 5975915 165 6085311 166 6196034 167 6308092 168 6421493 169 6536245 170 6652356 171 6769834 172 6888687 173 7008923 174 7130550 175 7253576 176 7378009 177 7503857 178 7631128 179 7759830 180 7889971 181 8021559 182 8154602 183 8289108 184 8425085 185 8562541 186 8701484 187 8841922 188 8983863 189 9127315 190 9272286 191 9418784 192 9566817 193 9716393 194 9867520 195 10020206 196 10174459 197 10330287 198 10487698 199 10646700 200 10807301 201 10969509 202 11133332 203 11298778 204 11465855 205 11634571 206 11804934 207 11976952 208 12150633 209 12325985 210 12503016 211 12681734 212 12862147 213 13044263 214 13228090 215 13413636 216 13600909 217 13789917 218 13980668 219 14173170 220 14367431 221 14563459 222 14761262 223 14960848 224 15162225 225 15365401 226 15570384 227 15777182 228 15985803 229 16196255 230 16408546 231 16622684 232 16838677 233 17056533 234 17276260 235 17497866 236 17721359 237 17946747 238 18174038 239 18403240 240 18634361 241 18867409 242 19102392 243 19339318 244 19578195 245 19819031 246 20061834 247 20306612 248 20553373 249 20802125 250 21052876 251 21305634 252 21560407 253 21817203 254 22076030 255 22336896 256 22599809 257 22864777 258 23131808 259 23400910 260 23672091 261 23945359 262 24220722 263 24498188 264 24777765 265 25059461 266 25343284 267 25629242 268 25917343 269 26207595 270 26500006 271 26794584 272 27091337 273 27390273 274 27691400 275 27994726 276 28300259 277 28608007 278 28917978 279 29230180 280 29544621 281 29861309 282 30180252 283 30501458 284 30824935 285 31150691 286 31478734 287 31809072 288 32141713 289 32476665 290 32813936 291 33153534 292 33495467 293 33839743 294 34186370 295 34535356 296 34886709 297 35240437 298 35596548 299 35955050 300 36315951 301 36679259 302 37044982 303 37413128 304 37783705 305 38156721 306 38532184 307 38910102 308 39290483 309 39673335 310 40058666 311 40446484 312 40836797 313 41229613 314 41624940 315 42022786 316 42423159 317 42826067 318 43231518 319 43639520 320 44050081 321 44463209 322 44878912 323 45297198 324 45718075 325 46141551 326 46567634 327 46996332 328 47427653 329 47861605 330 48298196 331 48737434 332 49179327 333 49623883 334 50071110 335 50521016 336 50973609 337 51428897 338 51886888 339 52347590 340 52811011 341 53277159 342 53746042 343 54217668 344 54692045 345 55169181 346 55649084 347 56131762 348 56617223 349 57105475 350 57596526 351 58090384 352 58587057 353 59086553 354 59588880 355 60094046 356 60602059 357 61112927 358 61626658 359 62143260 360 62662741 361 63185109 362 63710372 363 64238538 364 64769615 365 65303611 366 65840534 367 66380392 368 66923193 369 67468945 370 68017656 371 68569334 372 69123987 373 69681623 374 70242250 375 70805876 376 71372509 377 71942157 378 72514828 379 73090530 380 73669271 381 74251059 382 74835902 383 75423808 384 76014785 385 76608841 386 77205984 387 77806222 388 78409563 389 79016015 390 79625586 391 80238284 392 80854117 393 81473093 394 82095220 395 82720506 396 83348959 397 83980587 398 84615398 399 85253400 400 85894601 401 86539009 402 87186632 403 87837478 404 88491555 405 89148871 406 89809434 407 90473252 408 91140333 409 91810685 410 92484316 411 93161234 412 93841447 413 94524963 414 95211790 415 95901936 416 96595409 417 97292217 418 97992368 419 98695870 420 99402731 421 100112959 422 100826562 423 101543548 424 102263925 425 102987701 426 103714884 427 104445482 428 105179503 429 105916955 430 106657846 431 107402184 432 108149977 433 108901233 434 109655960 435 110414166 436 111175859 437 111941047 438 112709738 439 113481940 440 114257661 441 115036909 442 115819692 443 116606018 444 117395895 445 118189331 446 118986334 447 119786912 448 120591073 449 121398825 450 122210176 451 123025134 452 123843707 453 124665903 454 125491730 455 126321196 456 127154309 457 127991077 458 128831508 459 129675610 460 130523391 461 131374859 462 132230022 463 133088888 464 133951465 465 134817761 466 135687784 467 136561542 468 137439043 469 138320295 470 139205306 471 140094084 472 140986637 473 141882973 474 142783100 475 143687026 476 144594759 477 145506307 478 146421678 479 147340880 480 148263921 481 149190809 482 150121552 483 151056158 484 151994635 485 152936991 486 153883234 487 154833372 488 155787413 489 156745365 490 157707236 491 158673034 492 159642767 493 160616443 494 161594070 495 162575656 496 163561209 497 164550737 498 165544248 499 166541750 500 167543251 501 168548759 502 169558282 503 170571828 504 171589405 505 172611021 506 173636684 507 174666402 508 175700183 509 176738035 510 177779966 511 178825984 512 179876097 513 180930313 514 181988640 515 183051086 516 184117659 517 185188367 518 186263218 519 187342220 520 188425381 521 189512709 522 190604212 523 191699898 524 192799775 525 193903851 526 195012134 527 196124632 528 197241353 529 198362305 530 199487496 531 200616934 532 201750627 533 202888583 534 204030810 535 205177316 536 206328109 537 207483197 538 208642588 539 209806290 540 210974311 541 212146659 542 213323342 543 214504368 544 215689745 545 216879481 546 218073584 547 219272062 548 220474923 549 221682175 550 222893826 551 224109884 552 225330357 553 226555253 554 227784580 555 229018346 556 230256559 557 231499227 558 232746358 559 233997960 560 235254041 561 236514609 562 237779672 563 239049238 564 240323315 565 241601911 566 242885034 567 244172692 568 245464893 569 246761645 570 248062956 571 249368834 572 250679287 573 251994323 574 253313950 575 254638176 576 255967009 577 257300457 578 258638528 579 259981230 580 261328571 581 262680559 582 264037202 583 265398508 584 266764485 585 268135141 586 269510484 587 270890522 588 272275263 589 273664715 590 275058886 591 276457784 592 277861417 593 279269793 594 280682920 595 282100806 596 283523459 597 284950887 598 286383098 599 287820100 600 289261901 601 290708509 602 292159932 603 293616178 604 295077255 605 296543171 606 298013934 607 299489552 608 300970033 609 302455385 610 303945616 611 305440734 612 306940747 613 308445663 614 309955490 615 311470236 616 312989909 617 314514517 618 316044068 619 317578570 620 319118031 621 320662459 622 322211862 623 323766248 624 325325625 625 326890001 626 328459384 627 330033782 628 331613203 629 333197655 630 334787146 631 336381684 632 337981277 633 339585933 634 341195660 635 342810466 636 344430359 637 346055347 638 347685438 639 349320640 640 350960961 641 352606409 642 354256992 643 355912718 644 357573595 645 359239631 646 360910834 647 362587212 648 364268773 649 365955525 650 367647476 651 369344634 652 371047007 653 372754603 654 374467430 655 376185496 656 377908809 657 379637377 658 381371208 659 383110310 660 384854691 661 386604359 662 388359322 663 390119588 664 391885165 665 393656061 666 395432284 667 397213842 668 399000743 669 400792995 670 402590606 671 404393584 672 406201937 673 408015673 674 409834800 675 411659326 676 413489259 677 415324607 678 417165378 679 419011580 680 420863221 681 422720309 682 424582852 683 426450858 684 428324335 685 430203291 686 432087734 687 433977672 688 435873113 689 437774065 690 439680536 691 441592534 692 443510067 693 445433143 694 447361770 695 449295956 696 451235709 697 453181037 698 455131948 699 457088450 700 459050551 701 461018259 702 462991582 703 464970528 704 466955105 705 468945321 706 470941184 707 472942702 708 474949883 709 476962735 710 478981266 711 481005484 712 483035397 713 485071013 714 487112340 715 489159386 716 491212159 717 493270667 718 495334918 719 497404920 720 499480681 721 501562209 722 503649512 723 505742598 724 507841475 725 509946151 726 512056634 727 514172932 728 516295053 729 518423005 730 520556796 731 522696434 732 524841927 733 526993283 734 529150510 735 531313616 736 533482609 737 535657497 738 537838288 739 540024990 740 542217611 741 544416159 742 546620642 743 548831068 744 551047445 745 553269781 746 555498084 747 557732362 748 559972623 749 562218875 750 564471126 751 566729384 752 568993657 753 571263953 754 573540280 755 575822646 756 578111059 757 580405527 758 582706058 759 585012660 760 587325341 761 589644109 762 591968972 763 594299938 764 596637015 765 598980211 766 601329534 767 603684992 768 606046593 769 608414345 770 610788256 771 613168334 772 615554587 773 617947023 774 620345650 775 622750476 776 625161509 777 627578757 778 630002228 779 632431930 780 634867871 781 637310059 782 639758502 783 642213208 784 644674185 785 647141441 786 649614984 787 652094822 788 654580963 789 657073415 790 659572186 791 662077284 792 664588717 793 667106493 794 669630620 795 672161106 796 674697959 797 677241187 798 679790798 799 682346800 800 684909201 801 687478009 802 690053232 803 692634878 804 695222955 805 697817471 806 700418434 807 703025852 808 705639733 809 708260085 810 710886916 811 713520234 812 716160047 813 718806363 814 721459190 815 724118536 816 726784409 817 729456817 818 732135768 819 734821270 820 737513331 821 740211959 822 742917162 823 745628948 824 748347325 825 751072301 826 753803884 827 756542082 828 759286903 829 762038355 830 764796446 831 767561184 832 770332577 833 773110633 834 775895360 835 778686766 836 781484859 837 784289647 838 787101138 839 789919340 840 792744261 841 795575909 842 798414292 843 801259418 844 804111295 845 806969931 846 809835334 847 812707512 848 815586473 849 818472225 850 821364776 851 824264134 852 827170307 853 830083303 854 833003130 855 835929796 856 838863309 857 841803677 858 844750908 859 847705010 860 850665991 861 853633859 862 856608622 863 859590288 864 862578865 865 865574361 866 868576784 867 871586142 868 874602443 869 877625695 870 880655906 871 883693084 872 886737237 873 889788373 874 892846500 875 895911626 876 898983759 877 902062907 878 905149078 879 908242280 880 911342521 881 914449809 882 917564152 883 920685558 884 923814035 885 926949591 886 930092234 887 933241972 888 936398813 889 939562765 890 942733836 891 945912034 892 949097367 893 952289843 894 955489470 895 958696256 896 961910209 897 965131337 898 968359648 899 971595150 900 974837851 901 978087759 902 981344882 903 984609228 904 987880805 905 991159621 906 994445684 907 997739002 908 1001039583 909 1004347435 910 1007662566 911 1010984984 912 1014314697 913 1017651713 914 1020996040 915 1024347686 916 1027706659 917 1031072967 918 1034446618 919 1037827620 920 1041215981 921 1044611709 922 1048014812 923 1051425298 924 1054843175 925 1058268451 926 1061701134 927 1065141232 928 1068588753 929 1072043705 930 1075506096 931 1078975934 932 1082453227 933 1085937983 934 1089430210 935 1092929916 936 1096437109 937 1099951797 938 1103473988 939 1107003690 940 1110540911 941 1114085659 942 1117637942 943 1121197768 944 1124765145 945 1128340081 946 1131922584 947 1135512662 948 1139110323 949 1142715575 950 1146328426 951 1149948884 952 1153576957 953 1157212653 954 1160855980 955 1164506946 956 1168165559 957 1171831827 958 1175505758 959 1179187360 960 1182876641 961 1186573609 962 1190278272 963 1193990638 964 1197710715 965 1201438511 966 1205174034 967 1208917292 968 1212668293 969 1216427045 970 1220193556 971 1223967834 972 1227749887 973 1231539723 974 1235337350 975 1239142776 976 1242956009 977 1246777057 978 1250605928 979 1254442630 980 1258287171 981 1262139559 982 1265999802 983 1269867908 984 1273743885 985 1277627741 986 1281519484 987 1285419122 988 1289326663 989 1293242115 990 1297165486 991 1301096784 992 1305036017 993 1308983193 994 1312938320 995 1316901406 996 1320872459 997 1324851487 998 1328838498 999 1332833500 1000 1336836501