1 1 2 0 3 0 4 1 5 0 6 1 7 0 8 1 9 1 10 1 11 1 12 1 13 2 14 1 15 2 16 2 17 3 18 2 19 3 20 3 21 4 22 4 23 4 24 5 25 6 26 6 27 6 28 8 29 8 30 9 31 9 32 11 33 12 34 13 35 13 36 16 37 17 38 18 39 19 40 22 41 24 42 25 43 27 44 30 45 33 46 35 47 37 48 41 49 46 50 47 51 51 52 56 53 61 54 64 55 69 56 75 57 82 58 86 59 92 60 100 61 109 62 114 63 122 64 133 65 143 66 151 67 161 68 174 69 187 70 198 71 210 72 227 73 244 74 257 75 273 76 295 77 314 78 333 79 353 80 379 81 405 82 428 83 453 84 486 85 518 86 547 87 579 88 620 89 659 90 696 91 737 92 786 93 835 94 882 95 932 96 993 97 1055 98 1111 99 1175 100 1250 101 1324 102 1396 103 1475 104 1565 105 1658 106 1747 107 1843 108 1954 109 2068 110 2176 111 2296 112 2431 113 2569 114 2703 115 2850 116 3013 117 3181 118 3347 119 3524 120 3723 121 3929 122 4128 123 4346 124 4587 125 4833 126 5079 127 5343 128 5632 129 5932 130 6230 131 6548 132 6898 133 7259 134 7619 135 8004 136 8426 137 8858 138 9294 139 9759 140 10262 141 10783 142 11309 143 11865 144 12470 145 13095 146 13724 147 14393 148 15117 149 15860 150 16618 151 17419 152 18279 153 19170 154 20076 155 21030 156 22057 157 23118 158 24197 159 25337 160 26558 161 27818 162 29105 163 30462 164 31908 165 33405 166 34938 167 36545 168 38261 169 40038 170 41851 171 43761 172 45791 173 47888 174 50041 175 52301 176 54695 177 57177 178 59722 179 62389 180 65215 181 68143 182 71144 183 74293 184 77622 185 81066 186 84607 187 88316 188 92226 189 96279 190 100448 191 104805 192 109399 193 114162 194 119053 195 124174 196 129563 197 135140 198 140886 199 146890 200 153195 201 159733 202 166464 203 173489 204 180868 205 188513 206 196385 207 204603 208 213223 209 222148 210 231349 211 240948 212 250997 213 261412 214 272152 215 283339 216 295054 217 307191 218 319699 219 332736 220 346371 221 360486 222 375053 223 390220 224 406063 225 422477 226 439412 227 457029 228 475431 229 494487 230 514146 231 534600 232 555944 233 578037 234 600844 235 624559 236 649280 237 674878 238 701305 239 728760 240 757377 241 787004 242 817576 243 849345 244 882433 245 916668 246 952024 247 988736 248 1026942 249 1066488 250 1107317 251 1149692 252 1193781 253 1239404 254 1286500 255 1335377 256 1386201 257 1438773 258 1493060 259 1549376 260 1607893 261 1668433 262 1730944 263 1795754 264 1863087 265 1932733 266 2004627 267 2079166 268 2156564 269 2236592 270 2319229 271 2404868 272 2493740 273 2585645 274 2680528 275 2778818 276 2880801 277 2986236 278 3095073 279 3207807 280 3324722 281 3445566 282 3570319 283 3699499 284 3833404 285 3971809 286 4114682 287 4262561 288 4415824 289 4574208 290 4737667 291 4906845 292 5082109 293 5263181 294 5450078 295 5643447 296 5843693 297 6050574 298 6264076 299 6484904 300 6713541 301 6949707 302 7193394 303 7445411 304 7706251 305 7975622 306 8253574 307 8540951 308 8838283 309 9145322 310 9462107 311 9789535 312 10128244 313 10477951 314 10838694 315 11211514 316 11597064 317 11995043 318 12405587 319 12829765 320 13268289 321 13720928 322 14187783 323 14670027 324 15168491 325 15682904 326 16213405 327 16761310 328 17327496 329 17911690 330 18514122 331 19136187 332 19778826 333 20441847 334 21125486 335 21831234 336 22560203 337 23312171 338 24087401 339 24887602 340 25713930 341 26566174 342 27444740 343 28351412 344 29287461 345 30252779 346 31247776 347 32274393 348 33334097 349 34426763 350 35552872 351 36714608 352 37913522 353 39149530 354 40423266 355 41737057 356 43092594 357 44489920 358 45929729 359 47414521 360 48946251 361 50524976 362 52151463 363 53828552 364 55558311 365 57340855 366 59177191 367 61070314 368 63022503 369 65034058 370 67106045 371 69241739 372 71443727 373 73712351 374 76048836 375 78456834 376 80939128 377 83496167 378 86129448 379 88842893 380 91639537 381 94520079 382 97486156 383 100542017 384 103691121 385 106934259 386 110273268 387 113712912 388 117256908 389 120906212 390 124663053 391 128532524 392 132518706 393 136622899 394 140847517 395 145198128 396 149679337 397 154292600 398 159040660 399 163929701 400 168964708 401 174147408 402 179481011 403 184972202 404 190626439 405 196445893 406 202434115 407 208598360 408 214944791 409 221475855 410 228195511 411 235111863 412 242231569 413 249557467 414 257094187 415 264850449 416 272833587 417 281047043 418 289495896 419 298189687 420 307136625 421 316340574 422 325807235 423 335547179 424 345569342 425 355878152 426 366480159 427 377386820 428 388607948 429 400148785 430 412016570 431 424223798 432 436781444 433 449695393 434 462973698 435 476630237 436 490676953 437 505120520 438 519970171 439 535240920 440 550945914 441 567092941 442 583692151 443 600759992 444 618311105 445 636354183 446 654900571 447 673968430 448 693573756 449 713726376 450 734439124 451 755731772 452 777621879 453 800120759 454 823242604 455 847008997 456 871439499 457 896546719 458 922346422 459 948862490 460 976116269 461 1004121942 462 1032897307 463 1062468326 464 1092858479 465 1124083952 466 1156164360 467 1189128131 468 1223001322 469 1257801933 470 1293551777 471 1330282196 472 1368021694 473 1406790447 474 1446612911 475 1487523264 476 1529552823 477 1572724427 478 1617065092 479 1662612184 480 1709400419 481 1757455184 482 1806806386 483 1857495263 484 1909559781 485 1963028270 486 2017934228 487 2074322567 488 2132235037 489 2191703555 490 2252765014 491 2315468625 492 2379860536 493 2445976148 494 2513856335 495 2583555245 496 2655123428 497 2728600294 498 2804031385 499 2881475826 500 2960989119 501 3042615452 502 3126405034 503 3212422553 504 3300729333 505 3391374310 506 3484412960 507 3579916484 508 3677952017 509 3778573900 510 3881843850 511 3987839560 512 4096634762 513 4208290166 514 4322873692 515 4440470429 516 4561161687 517 4685014578 518 4812104138 519 4942523850 520 5076362771 521 5213695309 522 5354604629 523 5499192884 524 5647557792 525 5799782174 526 5955957605 527 6116195823 528 6280604519 529 6449275154 530 6622308656 531 6799827814 532 6981950502 533 7168777908 534 7360421778 535 7557016179 536 7758690462 537 7965556959 538 8177738516 539 8395381888 540 8618629378 541 8847604871 542 9082443703 543 9323306888 544 9570350241 545 9823710595 546 10083537415 547 10350006634 548 10623289077 549 10903536277 550 11190912513 551 11485610205 552 11787817143 553 12097700261 554 12415440245 555 12741248161 556 13075329524 557 13417868398 558 13769064112 559 14129147165 560 14498342794 561 14876854455 562 15264900929 563 15662734377 564 16070602097 565 16488727917 566 16917352362 567 17356751669 568 17807196468 569 18268933245 570 18742226801 571 19227378923 572 19724685957 573 20234419824 574 20756871083 575 21292369602 576 21841240535 577 22403782726 578 22980315154 579 23571199099 580 24176790153 581 24797416973 582 25433430377 583 26085224818 584 26753189557 585 27437686562 586 28139100367 587 28857862100 588 29594398393 589 30349106633 590 31122408673 591 31914776239 592 32726675765 593 33558543788 594 34410843557 595 35284090118 596 36178793695 597 37095434307 598 38034519483 599 38996611762 600 39982269948 601 40992020550 602 42026419693 603 43086082637 604 44171619966 605 45283609354 606 46422660958 607 47589446140 608 48784632494 609 50008854425 610 51262779723 611 52547141528 612 53862670291 613 55210061164 614 56590045417 615 58003424168 616 59450995276 617 60933520664 618 62451801619 619 64006712199 620 65599124104 621 67229873027 622 68899835442 623 70609965191 624 72361215427 625 74154501038 626 75990780865 627 77871096700 628 79796489015 629 81767959565 630 83786558084 631 85853420589 632 87969683247 633 90136443577 634 92354848817 635 94626138250 636 96951553185 637 99332294052 638 101769615062 639 104264868726 640 106819409440 641 109434550435 642 112111663317 643 114852222508 644 117657705984 645 120529550914 646 123469255440 647 126478426976 648 129558679207 649 132711582809 650 135938774121 651 139242006572 652 142623039778 653 146083590429 654 149625446648 655 153250518802 656 156960726045 657 160757945242 658 164644127898 659 168621355889 660 172691722953 661 176857278646 662 181120153067 663 185482615585 664 189946948185 665 194515389060 666 199190263747 667 203974043796 668 208869216477 669 213878226508 670 219003610348 671 224248059828 672 229614286742 673 235104958721 674 240722842138 675 246470869710 676 252351995308 677 258369129664 678 264525290750 679 270823670807 680 277267487627 681 283859917793 682 290604250554 683 297503961100 684 304562555253 685 311783496573 686 319170370176 687 326726959725 688 334457082025 689 342364513415 690 350453161792 691 358727143937 692 367190615072 693 375847692958 694 384702634229 695 393759917903 696 403024068400 697 412499572271 698 422191065611 699 432103422487 700 442241565753 701 452610383456 702 463214925594 703 474060492448 704 485152440420 705 496496095285 706 508096953943 707 519960780293 708 532093402841 709 544500620258 710 557188415717 711 570163057627 712 583430884431 713 596998209232 714 610871544528 715 625057703737 716 639563579427 717 654396044786 718 669562184435 719 685069403619 720 700925197926 721 717137045873 722 733712653527 723 750660070084 724 767987442339 725 785702906536 726 803814845095 727 822332002318 728 841263232382 729 860617387047 730 880403579208 731 900631308119 732 921310196636 733 942449869727 734 964060233735 735 986151607863 736 1008734445530 737 1031819211265 738 1055416673492 739 1079538037306 740 1104194657233 741 1129397910158 742 1155159496155 743 1181491581066 744 1208406498172 745 1235916610286 746 1264034628138 747 1292773760807 748 1322147398708 749 1352168974318 750 1382852295987 751 1414211699268 752 1446261721048 753 1479016955252 754 1512492395791 755 1546703599703 756 1581666347758 757 1617396488715 758 1653910302262 759 1691224670070 760 1729356716611 761 1768323651257 762 1808143148277 763 1848833520252 764 1890413347619 765 1932901315651 766 1976316605453 767 2020679079419 768 2066008896795 769 2112326337390 770 2159652214649 771 2208008071239 772 2257415771229 773 2307897322021 774 2359475306913 775 2412173082523 776 2466014359497 777 2521023017855 778 2577223552133 779 2634641283306 780 2693301922421 781 2753231372135 782 2814456196767 783 2877003844637 784 2940902186970 785 3006179316490 786 3072864039340 787 3140986100841 788 3210575710085 789 3281663331902 790 3354280193468 791 3428458525288 792 3504231067777 793 3581630847378 794 3660691710864 795 3741448579108 796 3823936925014 797 3908192546795 798 3994252127315 799 4082153490937 800 4171935066469 801 4263635652438 802 4357294992919 803 4452954052718 804 4550654458664 805 4650438248141 806 4752348476434 807 4856429504958 808 4962726412287 809 5071284738556 810 5182151120655 811 5295373585771 812 5411000943809 813 5529082523782 814 5649668828306 815 5772811846277 816 5898564422645 817 6026979975468 818 6158113185533 819 6292020325086 820 6428758592414 821 6568385825152 822 6710961221493 823 6856545674125 824 7005201085366 825 7156990070564 826 7311976701377 827 7470226862302 828 7631807538968 829 7796786501230 830 7965233086017 831 8137218570842 832 8312815424497 833 8492096985079 834 8675138278115 835 8862016397760 836 9052809734097 837 9247597640889 838 9446461279550 839 9649484024190 840 9856750660460 841 10068347030334 842 10284360919943 843 10504882485392 844 10730003408288 845 10959816535598 846 11194416807786 847 11433901692241 848 11678370314307 849 11927923084833 850 12182662657487 851 12442694390596 852 12708125444467 853 12979064384928 854 13255622190207 855 13537912734598 856 13826051839856 857 14120156872007 858 14420347793392 859 14726747657170 860 15039481629220 861 15358676572593 862 15684462133224 863 16016971264807 864 16356339215004 865 16702703082539 866 17056202958343 867 17416982476576 868 17785187748338 869 18160966912293 870 18544471326992 871 18935856133405 872 19335279157327 873 19742900445482 874 20158883496058 875 20583395856842 876 21016607986163 877 21458692760118 878 21909826765814 879 22370190927429 880 22839969311071 881 23319348623945 882 23808519564647 883 24307677464968 884 24817021057671 885 25336751960794 886 25867076072352 887 26408204250129 888 26960351035638 889 27523734105890 890 28098575737929 891 28685103522292 892 29283549022913 893 29894147221286 894 30517138045807 895 31152767101932 896 31801284293080 897 32462943247260 898 33138002896887 899 33826728253594 900 34529388978160 901 35246258773380 902 35977617042491 903 36723749700398 904 37484947675377 905 38261506292239 906 39053727003661 907 39861918223014 908 40686393780584 909 41527472288966 910 42385478932489 911 43260746348534 912 44153613029449 913 45064422650396 914 45993525946531 915 46941281637614 916 47908054752831 917 48894215949270 918 49900143471970 919 50926224102071 920 51972851433413 921 53040425170787 922 54129353155743 923 55240052371587 924 56372947157627 925 57528468468196 926 58707055997794 927 59909159232951 928 61135235584533 929 62385749635449 930 63661175358605 931 64961997199178 932 66288708150785 933 67641808983107 934 69021810535620 935 70429234861566 936 71864613238309 937 73328485351261 938 74821401698862 939 76343924792208 940 77896627072927 941 79480090086920 942 81094906994404 943 82741683803336 944 84421037228017 945 86133593839918 946 87879992664107 947 89660886484438 948 91476939627348 949 93328827067516 950 95217237149794 951 97142872955706 952 99106449988727 953 101108695268139 954 103150350169057 955 105232171831180 956 107354930776321 957 109519409979516 958 111726407808569 959 113976739511519 960 116271234754913 961 118610736645668 962 120996104810993 963 123428216958516 964 125907966304308 965 128436260584252 966 131014025268336 967 133642205167764 968 136321761791873 969 139053672334307 970 141838933000293 971 144678560705842 972 147573590344847 973 150525073725138 974 153534083054444 975 156601712719776 976 159729076438008 977 162917306179848 978 166167555807283 979 169481002911205 980 172858845881040 981 176302302804952 982 179812615236905 983 183391050136185 984 187038896842469 985 190757465921627 986 194548093111253 987 198412141354471 988 202350997645689 989 206366071866802 990 210458800904626 991 214630650750789 992 218883113262488 993 223217704973328 994 227635971358383 995 232139489052587 996 236729862505959 997 241408722739534 998 246177731812551 999 251038585145982 1000 255993008041178