0 1 1 1 2 1 3 2 4 2 5 2 6 3 7 4 8 4 9 5 10 6 11 6 12 7 13 9 14 10 15 11 16 13 17 14 18 15 19 18 20 20 21 21 22 24 23 26 24 28 25 33 26 36 27 38 28 43 29 46 30 49 31 56 32 60 33 63 34 71 35 76 36 80 37 90 38 96 39 100 40 112 41 120 42 125 43 139 44 149 45 155 46 171 47 183 48 190 49 208 50 223 51 232 52 252 53 269 54 280 55 304 56 325 57 338 58 364 59 387 60 403 61 434 62 462 63 481 64 515 65 547 66 570 67 609 68 646 69 672 70 716 71 759 72 790 73 840 74 889 75 925 76 981 77 1037 78 1079 79 1141 80 1205 81 1254 82 1323 83 1396 84 1453 85 1531 86 1614 87 1679 88 1765 89 1857 90 1932 91 2030 92 2135 93 2221 94 2329 95 2446 96 2544 97 2665 98 2797 99 2907 100 3041 101 3189 102 3314 103 3464 104 3630 105 3771 106 3937 107 4122 108 4281 109 4464 110 4670 111 4849 112 5052 113 5282 114 5483 115 5708 116 5963 117 6187 118 6435 119 6717 120 6968 121 7243 122 7556 123 7836 124 8138 125 8484 126 8796 127 9129 128 9512 129 9858 130 10224 131 10646 132 11030 133 11434 134 11900 135 12326 136 12769 137 13280 138 13751 139 14237 140 14800 141 15321 142 15853 143 16471 144 17046 145 17630 146 18308 147 18941 148 19580 149 20322 150 21020 151 21720 152 22531 153 23298 154 24063 155 24950 156 25793 157 26629 158 27597 159 28520 160 29433 161 30489 162 31500 163 32497 164 33649 165 34756 166 35842 167 37095 168 38305 169 39488 170 40853 171 42175 172 43461 173 44943 174 46386 175 47789 176 49400 177 50972 178 52496 179 54242 180 55955 181 57613 182 59506 183 61368 184 63168 185 65222 186 67247 187 69200 188 71423 189 73620 190 75740 191 78147 192 80531 193 82828 194 85430 195 88017 196 90507 197 93318 198 96119 199 98813 200 101851 201 104884 202 107798 203 111076 204 114356 205 117511 206 121050 207 124594 208 128000 209 131812 210 135643 211 139325 212 143433 213 147567 214 151538 215 155963 216 160425 217 164710 218 169471 219 174278 220 178901 221 184024 222 189202 223 194183 224 199689 225 205266 226 210633 227 216549 228 222547 229 228320 230 234678 231 241133 232 247344 233 254167 234 261102 235 267783 236 275107 237 282557 238 289735 239 297584 240 305586 241 313303 242 321717 243 330300 244 338580 245 347596 246 356806 247 365695 248 375350 249 385216 250 394751 251 405091 252 415664 253 425886 254 436945 255 448268 256 459225 257 471053 258 483172 259 494905 260 507552 261 520523 262 533087 263 546598 264 560463 265 573911 266 588349 267 603171 268 617555 269 632965 270 648801 271 664186 272 680637 273 697547 274 713984 275 731537 276 749595 277 767158 278 785876 279 805138 280 823894 281 843854 282 864403 283 884424 284 905688 285 927596 286 948965 287 971622 288 994969 289 1017755 290 1041884 291 1066760 292 1091057 293 1116743 294 1143228 295 1169124 296 1196466 297 1224665 298 1252251 299 1281327 300 1311334 301 1340719 302 1371646 303 1403567 304 1434843 305 1467718 306 1501666 307 1534956 308 1569895 309 1605973 310 1641386 311 1678510 312 1716851 313 1754511 314 1793934 315 1834662 316 1874701 317 1916562 318 1959812 319 2002352 320 2046782 321 2092701 322 2137898 323 2185041 324 2233765 325 2281764 326 2331775 327 2383468 328 2434425 329 2487448 330 2542270 331 2596359 332 2652577 333 2710698 334 2768073 335 2827651 336 2889259 337 2950118 338 3013243 339 3078511 340 3143035 341 3209902 342 3279045 343 3347441 344 3418238 345 3491454 346 3563934 347 3638883 348 3716392 349 3793163 350 3872482 351 3954518 352 4035826 353 4119750 354 4206536 355 4292613 356 4381391 357 4473193 358 4564297 359 4658168 360 4755242 361 4851643 362 4950889 363 5053514 364 5155477 365 5260369 366 5368838 367 5476670 368 5587505 369 5702102 370 5816101 371 5933193 372 6054250 373 6174741 374 6298397 375 6426234 376 6553556 377 6684128 378 6819097 379 6953583 380 7091416 381 7233886 382 7375919 383 7521383 384 7671716 385 7821673 386 7975164 387 8133774 388 8292061 389 8453957 390 8621244 391 8788290 392 8959039 393 9135444 394 9311668 395 9491697 396 9677677 397 9863559 398 10053341 399 10249352 400 10445357 401 10645377 402 10851933 403 11058571 404 11269316 405 11486923 406 11704726 407 11926741 408 12155947 409 12385443 410 12619265 411 12860637 412 13102421 413 13348635 414 13602745 415 13857402 416 14116617 417 14384096 418 14652257 419 14925079 420 15206559 421 15488884 422 15775992 423 16072151 424 16369296 425 16671356 426 16982903 427 17295607 428 17613346 429 17940989 430 18269974 431 18604139 432 18948662 433 19294717 434 19646068 435 20008248 436 20372185 437 20741556 438 21122232 439 21504869 440 21893092 441 22293137 442 22695381 443 23103351 444 23523645 445 23946386 446 24375027 447 24816536 448 25260750 449 25711000 450 26174685 451 26641369 452 27114254 453 27601150 454 28091324 455 28587869 456 29099043 457 29613814 458 30135123 459 30671661 460 31212134 461 31759344 462 32322430 463 32889798 464 33464071 465 34054889 466 34650373 467 35252960 468 35872782 469 36497639 470 37129806 471 37779942 472 38435526 473 39098618 474 39780405 475 40468078 476 41163494 477 41878374 478 42599594 479 43328754 480 44078177 481 44834442 482 45598887 483 46384411 484 47177261 485 47978535 486 48801757 487 49632838 488 50472594 489 51335157 490 52206138 491 53086075 492 53989735 493 54902394 494 55824257 495 56770790 496 57726958 497 58692615 498 59683915 499 60685473 500 61696816 501 62734825 502 63783776 503 64842817 504 65929545 505 67027926 506 68136738 507 69274312 508 70424280 509 71584990 510 72775583 511 73979367 512 75194243 513 76440150 514 77700039 515 78971381 516 80274969 517 81593395 518 82923649 519 84287355 520 85666796 521 87058476 522 88484876 523 89927946 524 91383646 525 92875379 526 94384782 527 95907243 528 97467087 529 99045594 530 100637615 531 102268443 532 103919001 533 105583536 534 107288302 535 109013907 536 110754000 537 112535819 538 114339640 539 116158433 540 118020498 541 119905801 542 121806606 543 123752267 544 125722413 545 127708619 546 129741348 547 131799882 548 133875054 549 135998418 550 138148964 551 140316781 552 142534543 553 144780917 554 147045175 555 149361186 556 151707326 557 154072005 558 156490301 559 158940262 560 161409462 561 163934228 562 166492281 563 169070284 564 171705813 565 174376323 566 177067570 567 179818387 568 182605940 569 185414992 570 188285731 571 191195060 572 194126715 573 197122232 574 200158220 575 203217400 576 206342719 577 209510483 578 212702330 579 215962612 580 219267408 581 222597256 582 225997930 583 229445252 584 232918581 585 236465203 586 240060734 587 243683297 588 247381691 589 251131281 590 254908984 591 258765165 592 262674943 593 266613946 594 270634111 595 274710376 596 278817071 597 283007710 598 287257033 599 291537974 600 295905746 601 300334930 602 304797007 603 309348868 604 313964913 605 318615187 606 323358330 607 328168559 608 333014402 609 337956232 610 342968174 611 348017216 612 353165481 613 358386969 614 363647048 615 369009708 616 374448876 617 379928212 618 385513564 619 391178750 620 396885766 621 402702388 622 408602336 623 414545825 624 420602551 625 426746229 626 432935285 627 439241337 628 445638086 629 452082057 630 458646925 631 465306418 632 472015088 633 478848640 634 485780811 635 492764213 636 499876668 637 507091912 638 514360507 639 521762368 640 529271355 641 536835950 642 544538185 643 552352017 644 560223741 645 568237627 646 576367799 647 584558263 648 592895515 649 601353822 650 609874961 651 618547720 652 627346509 653 636210734 654 645231464 655 654383381 656 663603522 657 672985238 658 682503463 659 692092717 660 701848793 661 711746942 662 721719077 663 731863401 664 742155473 665 752524636 666 763071589 667 773772190 668 784553081 669 795517420 670 806641541 671 817849362 672 829246506 673 840809736 674 852460113 675 864305876 676 876324320 677 888433535 678 900744359 679 913234580 680 925819375 681 938612255 682 951591515 683 964669255 684 977961647 685 991447665 686 1005036325 687 1018846431 688 1032857622 689 1046975659 690 1061322160 691 1075877533 692 1090544182 693 1105446486 694 1120565601 695 1135800619 696 1151278780 697 1166981981 698 1182805861 699 1198880480 700 1215188685 701 1231622622 702 1248315159 703 1265250054 704 1282315806 705 1299648279 706 1317232289 707 1334952534 708 1352947816 709 1371203968 710 1389601972 711 1408283660 712 1427235920 713 1446335826 714 1465728198 715 1485401176 716 1505227931 717 1525356228 718 1545775445 719 1566354658 720 1587244799 721 1608436619 722 1629794959 723 1651473831 724 1673465345 725 1695630164 726 1718125514 727 1740944881 728 1763944567 729 1787284924 730 1810961068 731 1834824917 732 1859039921 733 1883602801 734 1908360919 735 1933481020 736 1958961599 737 1984645282 738 2010702032 739 2037132082 740 2063773441 741 2090799407 742 2118211987 743 2145844324 744 2173872981 745 2202301992 746 2230959653 747 2260025744 748 2289506331 749 2319224624 750 2349363850 751 2379932280 752 2410747882 753 2441997199 754 2473690717 755 2505641256 756 2538038821 757 2570896120 758 2604020597 759 2637605598 760 2671666371 761 2706004995 762 2740818127 763 2776123507 764 2811717613 765 2847800632 766 2884393036 767 2921285507 768 2958681656 769 2996604656 770 3034839521 771 3073593406 772 3112892245 773 3152515095 774 3192672533 775 3233393584 776 3274451414 777 3316059948 778 3358251284 779 3400792401 780 3443900823 781 3487611951 782 3531686434 783 3576345243 784 3621627076 785 3667286336 786 3713547604 787 3760452908 788 3807750143 789 3855667342 790 3904250268 791 3953240322 792 4002868921 793 4053185514 794 4103924734 795 4155321613 796 4207429614 797 4259976405 798 4313200468 799 4367159216 800 4421573506 801 4476685413 802 4532556389 803 4588900169 804 4645962263 805 4703808544 806 4762145699 807 4821222571 808 4881109439 809 4941505586 810 5002663476 811 5064658129 812 5127181263 813 5190488731 814 5254660268 815 5319380133 816 5384907755 817 5451327674 818 5518316413 819 5586136730 820 5654878419 821 5724210316 822 5794398431 823 5865537758 824 5937289134 825 6009922075 826 6083537179 827 6157787056 828 6232944514 829 6309115671 830 6385945081 831 6463709028 832 6542519318 833 6622012081 834 6702466818 835 6784001461 836 6866243830 837 6949476515 838 7033823602 839 7118904212 840 7205004300 841 7292254493 842 7380265047 843 7469324993 844 7559571460 845 7650605989 846 7742720917 847 7836059999 848 7930215724 849 8025483406 850 8122013945 851 8219390860 852 8317912361 853 8417736474 854 8518437364 855 8620316364 856 8723539129 857 8827670240 858 8933013871 859 9039743226 860 9147413528 861 9256331977 862 9366679528 863 9478001631 864 9590608162 865 9704688320 866 9819777983 867 9936189582 868 10054120598 869 10173096838 870 10293433552 871 10415336985 872 10538322718 873 10662708488 874 10788709281 875 10915830603 876 11044392902 877 11174620091 878 11306007231 879 11438877035 880 11573462960 881 11709249783 882 11846562366 883 11985643688 884 12125967791 885 12267861891 886 12411579084 887 12556582492 888 12703201362 889 12851698795 890 13001527213 891 13153018087 892 13306444796 893 13461248606 894 13617762788 895 13776271591 896 13936205370 897 14097899011 898 14261647700 899 14426870306 900 14593903567 901 14763054217 902 14933729544 903 15106267715 904 15280986959 905 15457283142 906 15635496090 907 15815955763 908 15998046248 909 16182108497 910 16368484889 911 16556547920 912 16746639523 913 16939114495 914 17133333211 915 17329638788 916 17528399187 917 17728962483 918 17931672546 919 18136910372 920 18344011978 921 18553322172 922 18765235374 923 18979075102 924 19195186528 925 19413978137 926 19634761255 927 19857881194 928 20083760595 929 20311697977 930 20542039035 931 20775221276 932 21010530326 933 21248311744 934 21489017832 935 21731921489 936 21977368409 937 22225826041 938 22476554177 939 22729897939 940 22986340704 941 23245129397 942 23506608375 943 23771277000 944 24038368776 945 24308227435 946 24581369180 947 24857013942 948 25135504305 949 25417373145 950 25701827132 951 25989207920 952 26280065525 953 26573592869 954 26870129948 955 27170244638 956 27473116484 957 27779083592 958 28088731876 959 28401226806 960 28716904755 961 29036370513 962 29358775419 963 29684453481 964 30014028318 965 30346637380 966 30682612561 967 31022596724 968 31365713047 969 31712290424 970 32062991822 971 32416926500 972 32774420159 973 33136155944 974 33501228554 975 33869960572 976 34243056324 977 34619595816 978 34999897927 979 35384688002 980 35773031702 981 36165244376 982 36562072971 983 36962568292 984 37367041238 985 37776261197 986 38189264641 987 38606357719 988 39028332463 989 39454210228 990 39884292485 991 40319394883 992 40758523710 993 41201975064 994 41650588123 995 42103354357 996 42560564725 997 43023082451 998 43489883790 999 43961253522 1000 44438079913