0 1 1 1 2 1 3 1 4 2 5 2 6 2 7 2 8 4 9 5 10 5 11 5 12 7 13 8 14 8 15 8 16 12 17 14 18 15 19 15 20 19 21 21 22 22 23 22 24 28 25 33 26 35 27 37 28 43 29 48 30 50 31 52 32 61 33 69 34 74 35 78 36 90 37 98 38 103 39 107 40 122 41 135 42 143 43 152 44 170 45 186 46 194 47 203 48 225 49 247 50 261 51 275 52 305 53 330 54 348 55 362 56 396 57 429 58 454 59 477 60 519 61 561 62 590 63 618 64 666 65 717 66 756 67 794 68 856 69 916 70 966 71 1009 72 1083 73 1155 74 1217 75 1275 76 1365 77 1454 78 1527 79 1599 80 1703 81 1813 82 1902 83 1991 84 2118 85 2248 86 2358 87 2461 88 2613 89 2768 90 2905 91 3032 92 3210 93 3394 94 3555 95 3708 96 3913 97 4137 98 4331 99 4521 100 4764 101 5022 102 5252 103 5472 104 5757 105 6059 106 6341 107 6607 108 6947 109 7297 110 7621 111 7932 112 8321 113 8736 114 9119 115 9498 116 9957 117 10441 118 10884 119 11315 120 11841 121 12401 122 12929 123 13439 124 14063 125 14714 126 15326 127 15912 128 16615 129 17367 130 18080 131 18776 132 19594 133 20472 134 21296 135 22097 136 23024 137 24020 138 24977 139 25910 140 26991 141 28138 142 29246 143 30318 144 31546 145 32850 146 34115 147 35358 148 36771 149 38276 150 39727 151 41156 152 42761 153 44470 154 46127 155 47760 156 49599 157 51552 158 53453 159 55315 160 57406 161 59622 162 61789 163 63915 164 66286 165 68808 166 71275 167 73698 168 76376 169 79235 170 82041 171 84803 172 87837 173 91063 174 94245 175 97375 176 100801 177 104439 178 108051 179 111610 180 115487 181 119587 182 123654 183 127671 184 132028 185 136646 186 141237 187 145795 188 150715 189 155916 190 161075 191 166190 192 171701 193 177534 194 183347 195 189118 196 195333 197 201889 198 208419 199 214884 200 221816 201 229142 202 236469 203 243747 204 251527 205 259751 206 267965 207 276115 208 284781 209 293934 210 303116 211 312254 212 321963 213 332194 214 342477 215 352688 216 363503 217 374867 218 386315 219 397722 220 409793 221 422479 222 435247 223 447984 224 461407 225 475501 226 489683 227 503858 228 518794 229 534473 230 550270 231 566038 232 582637 233 600024 234 617563 235 635071 236 653479 237 672768 238 692241 239 711694 240 732082 241 753462 242 775038 243 796625 244 819191 245 842835 246 866733 247 890645 248 915617 249 941740 250 968205 251 994682 252 1022308 253 1051144 254 1080367 255 1109634 256 1140122 257 1171956 258 1204216 259 1236597 260 1270264 261 1305382 262 1340942 263 1376632 264 1413720 265 1452386 266 1491606 267 1530969 268 1571893 269 1614478 270 1657677 271 1700996 272 1745965 273 1792776 274 1840298 275 1888034 276 1937513 277 1989034 278 2041293 279 2093783 280 2148082 281 2204578 282 2261974 283 2319668 284 2379357 285 2441381 286 2504448 287 2567796 288 2633247 289 2701178 290 2770276 291 2839797 292 2911578 293 2986089 294 3061837 295 3138106 296 3216722 297 3298261 298 3381148 299 3464653 300 3550752 301 3639995 302 3730779 303 3822188 304 3916411 305 4013962 306 4113211 307 4213167 308 4316139 309 4422763 310 4531249 311 4640564 312 4753033 313 4869486 314 4987955 315 5107365 316 5230137 317 5357168 318 5486492 319 5616842 320 5750816 321 5889318 322 6030415 323 6172646 324 6318753 325 6469675 326 6623410 327 6778477 328 6937645 329 7102047 330 7269497 331 7438537 332 7611938 333 7790917 334 7973164 335 8157136 336 8345817 337 8540478 338 8738794 339 8939022 340 9144384 341 9356104 342 9571741 343 9789425 344 10012531 345 10242535 346 10476843 347 10713524 348 10955992 349 11205930 350 11460468 351 11717545 352 11980706 353 12251831 354 12528086 355 12807203 356 13092930 357 13387145 358 13686989 359 13989876 360 14299727 361 14618571 362 14943538 363 15272010 364 15607981 365 15953655 366 16305910 367 16662045 368 17026071 369 17400383 370 17781776 371 18167475 372 18561752 373 18967060 374 19380100 375 19797765 376 20224613 377 20663140 378 21109985 379 21561869 380 22023606 381 22497944 382 22981290 383 23470187 384 23969481 385 24482301 386 25004766 387 25533292 388 26072880 389 26626923 390 27191485 391 27762653 392 28345635 393 28943964 394 29553751 395 30170692 396 30800235 397 31446067 398 32104237 399 32770292 400 33449750 401 34146635 402 34856772 403 35575645 404 36308771 405 37060430 406 37826223 407 38601478 408 39391994 409 40202244 410 41027841 411 41863688 412 42716006 413 43589249 414 44478903 415 45379511 416 46297617 417 47238098 418 48196279 419 49166510 420 50155391 421 51168273 422 52200002 423 53244650 424 54308983 425 55398804 426 56509037 427 57633362 428 58778855 429 59951443 430 61146057 431 62355703 432 63587746 433 64848411 434 66132705 435 67433508 436 68758266 437 70113673 438 71494295 439 72892848 440 74316669 441 75772925 442 77256037 443 78758592 444 80288320 445 81852612 446 83445823 447 85059835 448 86702865 449 88382398 450 90092758 451 91825468 452 93589156 453 95391882 454 97227626 455 99087551 456 100980255 457 102914544 458 104883940 459 106879318 460 108909520 461 110983926 462 113096092 463 115236174 464 117413415 465 119637404 466 121901924 467 124196320 468 126530232 469 128913640 470 131340325 471 133799310 472 136300250 473 138853856 474 141453541 475 144088183 476 146767338 477 149502288 478 152286211 479 155107591 480 157976462 481 160904480 482 163884947 483 166905556 484 169976963 485 173110953 486 176300682 487 179533202 488 182819597 489 186172553 490 189584941 491 193043524 492 196559323 493 200146006 494 203795741 495 207494715 496 211254175 497 215088658 498 218990584 499 222945375 500 226964787 501 231063643 502 235234539 503 239461655 504 243757105 505 248136414 506 252592356 507 257108864 508 261698114 509 266376534 510 271136362 511 275961087 512 280862655 513 285858355 514 290940368 515 296091833 516 301325360 517 306658674 518 312084080 519 317583413 520 323169977 521 328861787 522 334651213 523 340519422 524 346480355 525 352553130 526 358729687 527 364990561 528 371349486 529 377826956 530 384414297 531 391091447 532 397872519 533 404779098 534 411802731 535 418922139 536 426151908 537 433514181 538 441000958 539 448589587 540 456295157 541 464140702 542 472118350 543 480204891 544 488415282 545 496773938 546 505272522 547 513887502 548 522633574 549 531536270 550 540587045 551 549761673 552 559075500 553 568554797 554 578191466 555 587959860 556 597876258 557 607967307 558 618224857 559 628622153 560 639176063 561 649914826 562 660830081 563 671894475 564 683124750 565 694550823 566 706163479 567 717934263 568 729880214 569 742032796 570 754383458 571 766902389 572 779607403 573 792530606 574 805663951 575 818975527 576 832483547 577 846221442 578 860181688 579 874331937 580 888690367 581 903292143 582 918129054 583 933167979 584 948426527 585 963941405 586 979704600 587 995682349 588 1011893234 589 1028374943 590 1045119841 591 1062092102 592 1079311106 593 1096815278 594 1114597243 595 1132620146 596 1150904219 597 1169489961 598 1188369552 599 1207505092 600 1226916299 601 1246645964 602 1266685644 603 1286996321 604 1307598275 605 1328536304 606 1349802655 607 1371356245 608 1393218000 609 1415433724 610 1437996673 611 1460863545 612 1484055856 613 1507621194 614 1531553332 615 1555807997 616 1580406397 617 1605398360 618 1630777408 619 1656498504 620 1682582452 621 1709080977 622 1735987776 623 1763256591 624 1790909118 625 1818998445 626 1847519243 627 1876423081 628 1905732814 629 1935502542 630 1965727131 631 1996356416 632 2027413985 633 2058956682 634 2090979352 635 2123430889 636 2156334532 637 2189750006 638 2223671285 639 2258045400 640 2292895892 641 2328285210 642 2364208625 643 2400611177 644 2437517296 645 2474990955 646 2513028413 647 2551571548 648 2590645054 649 2630315321 650 2670579834 651 2711379678 652 2752739477 653 2794728519 654 2837343844 655 2880525140 656 2924296009 657 2968728316 658 3013819833 659 3059509296 660 3105821652 661 3152830656 662 3200535158 663 3248870689 664 3297863184 665 3347587736 666 3398044109 667 3449166105 668 3500981011 669 3553567375 670 3606924955 671 3660985759 672 3715776233 673 3771378579 674 3827792106 675 3884947062 676 3942870538 677 4001648415 678 4061281449 679 4121696879 680 4182922471 681 4245046012 682 4308070255 683 4371918956 684 4436620651 685 4502266238 686 4568860000 687 4636324156 688 4704686565 689 4774041962 690 4844394603 691 4915665729 692 4987882119 693 5061142068 694 5135450567 695 5210727209 696 5286999815 697 5364369184 698 5442842333 699 5522335553 700 5602878253 701 5684573082 702 5767428178 703 5851357067 704 5936390277 705 6022634924 706 6110099723 707 6198696861 708 6288456047 709 6379489328 710 6471804660 711 6565311544 712 6660039842 713 6756106254 714 6853521423 715 6952191648 716 7052148299 717 7153510490 718 7256291477 719 7360392463 720 7465845212 721 7572772807 722 7681191132 723 7791000344 724 7902231794 725 8015013632 726 8129361669 727 8245174206 728 8362480574 729 8481413380 730 8601990287 731 8724108254 732 8847798562 733 8973197071 734 9100324097 735 9229071715 736 9359472556 737 9491664841 738 9625671032 739 9761380830 740 9898828587 741 10038158635 742 10179393879 743 10322421954 744 10467275274 745 10614104446 746 10762932288 747 10913643952 748 11066272781 749 11220975379 750 11377777988 751 11536561054 752 11697359020 753 11860331661 754 12025509141 755 12192766841 756 12362140042 757 12533794041 758 12707762155 759 12883917855 760 13062294993 761 13243065318 762 13426263001 763 13611760124 764 13799588911 765 13989926766 766 14182810472 767 14378109493 768 14575857818 769 14776236800 770 14979287570 771 15184874671 772 15393034338 773 15603951421 774 15817669633 775 16034050011 776 16253129862 777 16475101740 778 16700010982 779 16927717017 780 17158255905 781 17391827981 782 17628478930 783 17868064100 784 18110619888 785 18356354079 786 18605317600 787 18857361318 788 19112523665 789 19371017086 790 19632897141 791 19898007984 792 20166387780 793 20438256089 794 20713673353 795 20992482667 796 21274721380 797 21560617463 798 21850232700 799 22143407546 800 22440176368 801 22740774062 802 23045266888 803 23353493411 804 23665490990 805 23981500292 806 24301592694 807 24625600389 808 24953561952 809 25285722641 810 25622158105 811 25962697616 812 26307382281 813 26656467218 814 27010030583 815 27367898595 816 27730109947 817 28096929030 818 28468435905 819 28844453138 820 29225020953 821 29610413702 822 30000717965 823 30395750160 824 30795551733 825 31200402793 826 31610396859 827 32025343630 828 32445285455 829 32870511881 830 33301122889 831 33736925806 832 34177961027 833 34624528103 834 35076730285 835 35534373056 836 35997494459 837 36466403496 838 36941208999 839 37421713685 840 37907957563 841 38400256975 842 38898728240 843 39403168108 844 39913619269 845 40430404654 846 40953646236 847 41483136265 848 42018919328 849 42561330283 850 43110495610 851 43666205717 852 44228503497 853 44797736304 854 45374033121 855 45957179359 856 46547218196 857 47144509218 858 47749190820 859 48361042800 860 48980111238 861 49606763974 862 50241148298 863 50883034875 864 51532469690 865 52189831733 866 52855278031 867 53528578079 868 54209777157 869 54899267674 870 55597211136 871 56303374013 872 57017797127 873 57740884393 874 58472805788 875 59213326375 876 59962491097 877 60720713955 878 61488174950 879 62264630747 880 63050128353 881 63845089332 882 64649702461 883 65463721124 884 66287196170 885 67120565246 886 67964023197 887 68817320484 888 69680504260 889 70554027271 890 71438089061 891 72332436383 892 73237118420 893 74152604410 894 75079106072 895 76016362525 896 76964424999 897 77923772503 898 78894629362 899 79876726080 900 80870115495 901 81875291921 902 82892492244 903 83921444963 904 84962200103 905 86015268566 906 87080894216 907 88158804525 908 89249046033 909 90352145182 910 91468357374 911 92597407311 912 93739345149 913 94894709175 914 96063769074 915 97246241948 916 98442182449 917 99652139871 918 100876395603 919 102114662071 920 103366996845 921 104633968542 922 105915867975 923 107212406733 924 108523640304 925 109850157179 926 111192255296 927 112549640840 928 113922370204 929 115311051475 930 116715999713 931 118136914474 932 119573857235 933 121027449836 934 122498023742 935 123985267542 936 125489242646 937 127010589597 938 128549656937 939 130106134100 940 131680081455 941 133272161731 942 134882733452 943 136511483936 944 138158467645 945 139824365846 946 141509553365 947 143213717374 948 144936919180 949 146679856938 950 148442923921 951 150225797848 952 152028543174 953 153851871457 954 155696192344 955 157561181406 956 159446909290 957 161354113350 958 163283216254 959 165233891984 960 167206206803 961 169200921741 962 171218470724 963 173258524511 964 175321153678 965 177407145214 966 179516955602 967 181650247076 968 183807094279 969 185988300833 970 188194345404 971 190424880752 972 192679984536 973 194960485586 974 197266885355 975 199598836738 976 201956414520 977 204340473816 978 206751531152 979 209189240343 980 211653672632 981 214145708230 982 216665885396 983 219213857475 984 221789701688 985 224394318516 986 227028271410 987 229691206309 988 232383207612 989 235105195126 990 237857754094 991 240640527749 992 243453605607 993 246297938537 994 249174130393 995 252081826726 996 255021115566 997 257992979349 998 260998037925 999 264035932859 1000 267106755002