0 1 1 0 2 2 3 1 4 2 5 1 6 2 7 1 8 3 9 2 10 4 11 4 12 5 13 4 14 6 15 5 16 7 17 6 18 9 19 8 20 11 21 11 22 13 23 13 24 17 25 15 26 20 27 19 28 23 29 23 30 27 31 27 32 33 33 33 34 38 35 39 36 45 37 45 38 53 39 54 40 62 41 63 42 73 43 74 44 84 45 86 46 97 47 100 48 112 49 115 50 130 51 134 52 148 53 154 54 170 55 176 56 195 57 202 58 222 59 232 60 255 61 264 62 290 63 301 64 329 65 343 66 373 67 389 68 423 69 441 70 477 71 499 72 540 73 563 74 609 75 636 76 684 77 716 78 770 79 804 80 865 81 904 82 970 83 1015 84 1087 85 1135 86 1216 87 1272 88 1358 89 1421 90 1517 91 1586 92 1692 93 1770 94 1883 95 1972 96 2097 97 2192 98 2332 99 2439 100 2589 101 2709 102 2873 103 3004 104 3186 105 3332 106 3527 107 3690 108 3905 109 4082 110 4318 111 4515 112 4770 113 4987 114 5267 115 5504 116 5810 117 6072 118 6402 119 6693 120 7054 121 7369 122 7765 123 8112 124 8538 125 8920 126 9386 127 9801 128 10310 129 10765 130 11315 131 11816 132 12413 133 12956 134 13608 135 14202 136 14906 137 15557 138 16322 139 17028 140 17860 141 18631 142 19529 143 20372 144 21347 145 22258 146 23318 147 24312 148 25454 149 26538 150 27776 151 28949 152 30292 153 31567 154 33015 155 34403 156 35970 157 37469 158 39167 159 40795 160 42624 161 44391 162 46369 163 48279 164 50418 165 52486 166 54789 167 57031 168 59519 169 61937 170 64625 171 67243 172 70134 173 72966 174 76084 175 79138 176 82503 177 85802 178 89420 179 92986 180 96884 181 100723 182 104925 183 109068 184 113582 185 118052 186 122912 187 127722 188 132953 189 138137 190 143753 191 149341 192 155381 193 161386 194 167882 195 174347 196 181316 197 188274 198 195762 199 203236 200 211282 201 219317 202 227943 203 236584 204 245842 205 255113 206 265051 207 275011 208 285658 209 296355 210 307774 211 319244 212 331488 213 343796 214 356906 215 370113 216 384161 217 398308 218 413361 219 428530 220 444634 221 460893 222 478136 223 495541 224 514001 225 532643 226 552381 227 572348 228 593463 229 614820 230 637407 231 660265 232 684399 233 708856 234 734657 235 760800 236 788377 237 816331 238 845779 239 875667 240 907125 241 939047 242 972648 243 1006757 244 1042612 245 1079051 246 1117324 247 1156220 248 1197071 249 1238596 250 1282163 251 1326493 252 1372967 253 1420250 254 1469819 255 1520266 256 1573097 257 1626908 258 1683228 259 1740590 260 1800620 261 1861774 262 1925717 263 1990908 264 2059028 265 2128471 266 2201034 267 2275022 268 2352267 269 2431081 270 2513323 271 2597232 272 2684780 273 2774118 274 2867265 275 2962371 276 3061481 277 3162671 278 3268113 279 3375785 280 3487907 281 3602455 282 3721687 283 3843495 284 3970267 285 4099796 286 4234525 287 4372246 288 4515437 289 4661798 290 4813961 291 4969512 292 5131136 293 5296423 294 5468103 295 5643668 296 5826001 297 6012478 298 6206052 299 6404093 300 6609595 301 6819833 302 7037972 303 7261156 304 7492623 305 7729512 306 7975117 307 8226468 308 8487036 309 8753718 310 9030070 311 9312980 312 9606061 313 9906083 314 10216862 315 10535024 316 10864465 317 11201807 318 11551017 319 11908593 320 12278706 321 12657701 322 13049855 323 13451500 324 13866983 325 14292505 326 14732646 327 15183441 328 15649574 329 16127071 330 16620702 331 17126351 332 17649029 333 18184448 334 18737741 335 19304608 336 19890269 337 20490274 338 21110115 339 21745154 340 22401008 341 23073027 342 23766936 343 24477927 344 25212002 345 25964157 346 26740547 347 27536149 348 28357225 349 29198587 350 30066811 351 30956498 352 31874377 353 32815032 354 33785327 355 34779665 356 35805233 357 36856221 358 37939993 359 39050718 360 40195898 361 41369512 362 42579427 363 43819386 364 45097442 365 46407321 366 47757242 367 49140726 368 50566370 369 52027454 370 53532793 371 55075642 372 56664983 373 58293867 374 59971695 375 61691258 376 63462184 377 65277240 378 67146262 379 69061789 380 71034095 381 73055457 382 75136407 383 77269196 384 79464569 385 81714544 386 84030357 387 86403740 388 88846201 389 91349452 390 93925249 391 96565058 392 99281150 393 102064693 394 104928276 395 107863042 396 110881838 397 113975557 398 117157616 399 120418593 400 123772239 401 127209110 402 130743265 403 134364991 404 138088942 405 141905090 406 145828471 407 149849029 408 153982124 409 158217429 410 162570967 411 167032070 412 171617164 413 176315570 414 181144086 415 186091745 416 191176047 417 196385675 418 201738595 419 207223471 420 212858667 421 218632555 422 224564276 423 230641839 424 236884875 425 243281383 426 249851457 427 256582795 428 263496304 429 270579319 430 277853303 431 285305588 432 292958127 433 300797944 434 308847906 435 317094646 436 325561629 437 334235502 438 343140291 439 352262326 440 361626596 441 371219047 442 381065345 443 391151449 444 401503630 445 412107537 446 422990503 447 434137779 448 445577424 449 457294724 450 469318433 451 481633513 452 494269848 453 507212011 454 520490704 455 534090550 456 548042995 457 562332346 458 576991306 459 592003777 460 607403342 461 623173984 462 639350132 463 655915455 464 672905720 465 690304201 466 708147664 467 726419476 468 745157319 469 764344268 470 784019476 471 804165626 472 824822947 473 845974254 474 867660819 475 889865165 476 912630145 477 935937908 478 959832519 479 984296290 480 1009374413 481 1035048936 482 1061366802 483 1088309690 484 1115925849 485 1144197183 486 1173173216 487 1202835604 488 1233235747 489 1264354965 490 1296246137 491 1328890841 492 1362343341 493 1396585016 494 1431672202 495 1467585962 496 1504384233 497 1542048412 498 1580638002 499 1620134230 500 1660598827 501 1702012759 502 1744439552 503 1787860567 504 1832341044 505 1877862227 506 1924491823 507 1972210853 508 2021088978 509 2071107709 510 2122338632 511 2174763204 512 2228455669 513 2283397332 514 2339664632 515 2397239448 516 2456200320 517 2516529164 518 2578307460 519 2641517031 520 2706241752 521 2772464145 522 2840270455 523 2909643312 524 2980672140 525 3053339591 526 3127737765 527 3203850131 528 3281771385 529 3361485223 530 3443089861 531 3526569104 532 3612024098 533 3699439630 534 3788919756 535 3880449614 536 3974137074 537 4069967524 538 4168052113 539 4268377371 540 4371057642 541 4476079968 542 4583562909 543 4693493898 544 4805995088 545 4921055259 546 5038800158 547 5159219233 548 5282442816 549 5408460943 550 5537407956 551 5669275456 552 5804201730 553 5942179270 554 6083351434 555 6227711491 556 6375407201 557 6526433677 558 6680943095 559 6838931682 560 7000557145 561 7165816737 562 7334873090 563 7507725577 564 7684541693 565 7865322216 566 8050240755 567 8239299388 568 8432677129 569 8630378529 570 8832588052 571 9039311951 572 9250741362 573 9466884180 574 9687937579 575 9913912293 576 10145011505 577 10381248027 578 10622832432 579 10869779521 580 11122306514 581 11380431515 582 11644378451 583 11914167910 584 12190031905 585 12471993456 586 12760291993 587 13054954312 588 13356227252 589 13664140586 590 13978950100 591 14300688473 592 14629619666 593 14965780712 594 15309443853 595 15660649627 596 16019680076 597 16386579225 598 16761638230 599 17144906092 600 17536683113 601 17937022431 602 18346235213 603 18764378691 604 19191774090 605 19628484364 606 20074840943 607 20530911611 608 20997039717 609 21473297890 610 21960040685 611 22457347244 612 22965583413 613 23484833984 614 24015477999 615 24557605897 616 25111609106 617 25677585513 618 26255939148 619 26846774431 620 27450509895 621 28067256572 622 28697446783 623 29341200032 624 29998962577 625 30670861508 626 31357359153 627 32058590244 628 32775032350 629 33506829872 630 34254475921 631 35018123621 632 35798283769 633 36595118351 634 37409155143 635 38240567085 636 39089899158 637 39957334373 638 40843437294 639 41748401135 640 42672809237 641 43616867267 642 44581177747 643 45565957870 644 46571831735 645 47599028292 646 48648192534 647 49719567516 648 50813819471 649 51931204665 650 53072413251 651 54237714950 652 55427823033 653 56643023227 654 57884052457 655 59151211524 656 60445263722 657 61766525273 658 63115785205 659 64493377806 660 65900118311 661 67336358234 662 68802942026 663 70300238783 664 71829121440 665 73389979548 666 74983715218 667 76610737572 668 78271980962 669 79967874582 670 81699384458 671 83466962848 672 85271608118 673 87113794786 674 88994556956 675 90914391949 676 92874368943 677 94875011308 678 96917424199 679 99002156232 680 101130352011 681 103302586074 682 105520042028 683 107783323737 684 110093654681 685 112451667353 686 114858628961 687 117315201362 688 119822694962 689 122381804671 690 124993885247 691 127659663960 692 130380543866 693 133157285532 694 135991340010 695 138883505031 696 141835280805 697 144847501662 698 147921721344 699 151058811790 700 154260379919 701 157527339482 702 160861352047 703 164263372647 704 167735122003 705 171277597659 706 174892579414 707 178581111751 708 182345035034 709 186185440329 710 190104233551 711 194102553693 712 198182372108 713 202344880514 714 206592117575 715 210925327432 716 215346621211 717 219857297100 718 224459538887 719 229154703875 720 233945050449 721 238831994935 722 243817876012 723 248904170796 724 254093298466 725 259386802448 726 264787184764 727 270296055158 728 275916004433 729 281648710726 730 287496854201 731 293462187238 732 299547481803 733 305754564803 734 312086306550 735 318544610768 736 325132446739 737 331851801341 738 338705745790 739 345696350541 740 352826795556 741 360099237558 742 367516966329 743 375082231589 744 382798436055 745 390667923195 746 398694216193 747 406879755214 748 415228185062 749 423742049951 750 432425119988 751 441280044387 752 450310726465 753 459519923837 754 468911674718 755 478488852944 756 488255635547 757 498215013951 758 508371312700 759 518727644561 760 529288483453 761 540057071986 762 551038038052 763 562234755766 764 573652016132 765 585293329089 766 597163651240 767 609266637428 768 621607414766 769 634189785154 770 647019056307 771 660099181930 772 673435653067 773 687032585140 774 700895658228 775 715029151997 776 729438946212 777 744129490214 778 759106866930 779 774375705976 780 789942299569 781 805811460751 782 821989702754 783 838482028034 784 855295174684 785 872434346114 786 889906512345 787 907717081408 788 925873267662 789 944380690559 790 963246813529 791 982477479847 792 1002080409630 793 1022061674376 794 1042429264577 795 1063189487451 796 1084350609075 797 1105919185925 798 1127903768394 799 1150311167259 800 1173150231771 801 1196428035490 802 1220153732802 803 1244334674602 804 1268980329848 805 1294098332767 806 1319698482881 807 1345788707088 808 1372379142427 809 1399478024342 810 1427095838140 811 1455241134624 812 1483924764426 813 1513155604242 814 1542944878236 815 1573301806120 816 1604237997255 817 1635763022300 818 1667888894583 819 1700625547341 820 1733985406917 821 1767978787828 822 1802618542661 823 1837915376192 824 1873882587316 825 1910531284104 826 1947875222367 827 1985925933657 828 2024697645057 829 2064202321988 830 2104454684861 831 2145467147344 832 2187254934886 833 2229830931460 834 2273210883771 835 2317408157776 836 2362439045081 837 2408317409746 838 2455060101804 839 2502681507268 840 2551199052273 841 2600627658150 842 2650985353126 843 2702287611624 844 2754553078890 845 2807797808523 846 2862041082658 847 2917299549070 848 2973593154714 849 3030939161374 850 3089358197967 851 3148868168538 852 3209490405614 853 3271243472575 854 3334149436259 855 3398227541241 856 3463500607580 857 3529988591937 858 3597715091876 859 3666700795237 860 3736970110136 861 3808544479978 862 3881449144966 863 3955706337571 864 4031342156610 865 4108379645203 866 4186845797087 867 4266764492901 868 4348163645066 869 4431068008392 870 4515506443624 871 4601504603838 872 4689092337278 873 4778296225160 874 4869147130158 875 4961672601441 876 5055904548484 877 5151871515553 878 5249606501955 879 5349139079955 880 5450503368383 881 5553730011057 882 5658854282470 883 5765907928184 884 5874927424841 885 5985945656328 886 6099000334908 887 6214125530132 888 6331360229394 889 6450739721801 890 6572304320921 891 6696090575673 892 6822140162700 893 6950490942553 894 7081185998908 895 7214264541605 896 7349771116624 897 7487746327706 898 7628236224592 899 7771282861321 900 7916933839472 901 8065232705510 902 8216228673497 903 8369966831458 904 8526498051609 905 8685869025229 906 8848132336121 907 9013336325543 908 9181535354605 909 9352779468956 910 9527124858147 911 9704623339405 912 9885332989184 913 10069307448414 914 10256606752581 915 10447286426167 916 10641408519980 917 10839030515633 918 11040216544075 919 11245026101760 920 11453525478067 921 11665776250466 922 11881846929615 923 12101801254169 924 12325710027014 925 12553639212236 926 12785661990809 927 13021846625043 928 13262268743162 929 13506998993436 930 13756115529912 931 14009691457892 932 14267807550490 933 14530539450447 934 14797970626971 935 15070179355899 936 15347251888555 937 15629269212782 938 15916320464301 939 16208489431348 940 16505868218744 941 16808543519857 942 17116610503709 943 17430158855970 944 17749286921063 945 18074087474491 946 18404662130192 947 18741106867737 948 19083526674705 949 19432020831388 950 19786697820899 951 20147660331412 952 20515020445069 953 20888884382943 954 21269367941197 955 21656580980466 956 22050643143533 957 22451668048734 958 22859779300229 959 23275094410496 960 23697741070960 961 24127840806267 962 24565525540471 963 25010920940133 964 25464163288013 965 25925382541929 966 26394719482221 967 26872308488076 968 27358294995636 969 27852817948356 970 28356027577770 971 28868067554587 972 29389093057756 973 29919252629075 974 30458706568249 975 31007608445029 976 31566123833209 977 32134411508843 978 32712642487330 979 33300980909425 980 33899603420936 981 34508679699955 982 35128392192143 983 35758916307651 984 36400440475375 985 37053146012337 986 37717227537480 987 38392872464139 988 39080281787298 989 39779649229672 990 40491182364163 991 41215081415230 992 41951560759020 993 42700827330018 994 43463102512951 995 44238600184959 996 45027548960268 997 45830169870774 998 46646699006929 999 47477364783834 1000 48322410993449