0 1 1 1 2 0 3 0 4 1 5 0 6 1 7 1 8 1 9 1 10 2 11 1 12 2 13 2 14 2 15 2 16 3 17 2 18 3 19 4 20 3 21 4 22 5 23 4 24 6 25 6 26 6 27 7 28 8 29 7 30 9 31 10 32 10 33 11 34 13 35 12 36 15 37 16 38 16 39 18 40 21 41 19 42 23 43 25 44 25 45 28 46 31 47 30 48 35 49 38 50 38 51 42 52 47 53 46 54 52 55 56 56 57 57 62 58 69 59 68 60 77 61 82 62 84 63 91 64 100 65 100 66 111 67 118 68 121 69 131 70 142 71 144 72 158 73 168 74 173 75 186 76 201 77 204 78 223 79 237 80 244 81 261 82 281 83 286 84 311 85 329 86 340 87 363 88 389 89 398 90 429 91 454 92 470 93 499 94 533 95 547 96 587 97 620 98 642 99 682 100 725 101 746 102 797 103 840 104 872 105 923 106 978 107 1008 108 1074 109 1130 110 1173 111 1239 112 1311 113 1353 114 1437 115 1510 116 1568 117 1654 118 1746 119 1803 120 1910 121 2005 122 2081 123 2192 124 2309 125 2388 126 2523 127 2646 128 2747 129 2888 130 3038 131 3144 132 3314 133 3471 134 3605 135 3784 136 3975 137 4114 138 4330 139 4531 140 4705 141 4933 142 5173 143 5358 144 5630 145 5884 146 6109 147 6398 148 6701 149 6942 150 7282 151 7606 152 7896 153 8260 154 8641 155 8952 156 9380 157 9789 158 10158 159 10616 160 11095 161 11494 162 12028 163 12542 164 13015 165 13588 166 14187 167 14697 168 15362 169 16008 170 16607 171 17322 172 18069 173 18718 174 19543 175 20352 176 21107 177 22000 178 22928 179 23750 180 24774 181 25780 182 26731 183 27840 184 28991 185 30025 186 31292 187 32542 188 33734 189 35107 190 36533 191 37830 192 39394 193 40943 194 42429 195 44128 196 45889 197 47507 198 49432 199 51349 200 53195 201 55290 202 57457 203 59474 204 61840 205 64202 206 66491 207 69066 208 71732 209 74233 210 77131 211 80036 212 82866 213 86024 214 89293 215 92384 216 95934 217 99496 218 102983 219 106850 220 110848 221 114660 222 118993 223 123351 224 127637 225 132361 226 137240 227 141926 228 147205 229 152530 230 157781 231 163540 232 169485 233 175226 234 181650 235 188138 236 194555 237 201559 238 208789 239 215806 240 223605 241 231491 242 239321 243 247824 244 256598 245 265154 246 274601 247 284174 248 293701 249 304001 250 314626 251 325037 252 336462 253 348056 254 359619 255 372080 256 384925 257 397560 258 411354 259 425366 260 439379 261 454420 262 469917 263 485219 264 501847 265 518750 266 535691 267 553814 268 572487 269 590980 270 610986 271 631344 272 651782 273 673586 274 696042 275 718342 276 742375 277 766851 278 791461 279 817648 280 844605 281 871454 282 900275 283 929652 284 959235 285 990628 286 1022943 287 1055203 288 1089712 289 1124910 290 1160407 291 1197984 292 1236659 293 1275345 294 1316610 295 1358716 296 1401236 297 1446147 298 1492355 299 1538678 300 1587940 301 1638228 302 1689071 303 1742669 304 1797799 305 1853166 306 1911886 307 1971866 308 2032565 309 2096432 310 2162110 311 2228176 312 2298082 313 2369506 314 2441853 315 2517847 316 2595984 317 2674690 318 2757788 319 2842718 320 2928829 321 3019124 322 3111947 323 3205576 324 3304219 325 3405072 326 3507403 327 3614541 328 3724662 329 3835876 330 3952814 331 4072410 332 4193840 333 4320804 334 4451269 335 4583178 336 4721631 337 4863254 338 5007154 339 5157408 340 5311772 341 5468006 342 5631721 343 5799214 344 5969506 345 6147088 346 6329509 347 6514301 348 6707646 349 6905483 350 7106730 351 7316364 352 7531664 353 7749937 354 7977992 355 8211384 356 8448907 357 8696066 358 8949855 359 9207362 360 9476038 361 9751032 362 10031019 363 10322066 364 10620886 365 10924278 366 11240433 367 11564060 368 11893702 369 12236030 370 12587448 371 12944462 372 13316079 373 13696493 374 14084121 375 14486311 376 14899109 377 15318730 378 15755032 379 16201687 380 16656965 381 17128955 382 17613312 383 18105936 384 18617619 385 19141476 386 19675597 387 20228890 388 20796596 389 21374252 390 21973703 391 22587428 392 23213336 393 23861236 394 24525921 395 25202534 396 25904061 397 26622292 398 27354975 399 28112862 400 28890271 401 29681931 402 30502052 403 31341724 404 32198467 405 33084086 406 33992394 407 34917681 408 35875476 409 36856106 410 37856851 411 38890708 412 39950885 413 41031218 414 42148688 415 43292776 416 44460552 417 45666239 418 46902445 419 48162516 420 49465010 421 50798488 422 52159789 423 53564496 424 55004583 425 56472821 426 57989508 427 59542235 428 61127562 429 62762594 430 64438566 431 66147684 432 67912127 433 69718436 434 71562874 435 73464204 436 75412874 437 77400502 438 79451270 439 81550618 440 83694500 441 85903452 442 88167127 443 90476463 444 92857853 445 95295544 446 97785174 447 100349208 448 102976433 449 105657067 450 108419937 451 111247968 452 114136474 453 117110034 454 120156482 455 123265324 456 126467963 457 129745938 458 133094234 459 136539735 460 140069236 461 143671480 462 147380680 463 151176938 464 155054819 465 159043736 466 163129399 467 167299716 468 171592000 469 175984730 470 180472086 471 185086247 472 189811754 473 194635606 474 199598490 475 204677167 476 209865452 477 215198448 478 220659482 479 226234631 480 231968188 481 237835140 482 243828842 483 249987652 484 256293590 485 262731748 486 269350336 487 276122448 488 283040967 489 290147822 490 297423576 491 304852326 492 312486543 493 320297254 494 328276938 495 336471316 496 344859461 497 353424409 498 362223266 499 371224864 500 380421236 501 389862254 502 399525445 503 409392678 504 419526101 505 429892220 506 440482599 507 451351692 508 462475293 509 473834092 510 485495721 511 497424234 512 509610689 513 522114508 514 534909674 515 547975706 516 561386092 517 575102304 518 589114930 519 603488762 520 618195927 521 633214628 522 648624772 523 664385113 524 680485766 525 696997330 526 713889989 527 731140596 528 748836071 529 766932187 530 785418643 531 804372396 532 823761516 533 843561546 534 863866901 535 884630299 536 905841027 537 927582944 538 949821901 539 972532098 540 995816082 541 1019623392 542 1043942854 543 1068865876 544 1094356005 545 1120385996 546 1147067332 547 1174346094 548 1202210747 549 1230760895 550 1259957681 551 1289772402 552 1320326193 553 1351561523 554 1383466611 555 1416149875 556 1449569988 557 1483696791 558 1518661841 559 1554403928 560 1590910953 561 1628300995 562 1666530168 563 1705566868 564 1745553931 565 1786426268 566 1828171584 567 1870918524 568 1914620433 569 1959244308 570 2004945255 571 2051654106 572 2099358545 573 2148198558 574 2198124737 575 2249102717 576 2301300902 577 2354645844 578 2409125337 579 2464891736 580 2521892849 581 2580092874 582 2639674694 583 2700560472 584 2762738190 585 2826373730 586 2891411940 587 2957815746 588 3025783725 589 3095233490 590 3166153362 591 3238723958 592 3312887107 593 3388604626 594 3466091989 595 3545262182 596 3626104115 597 3708814318 598 3793331716 599 3879616993 600 3967904048 601 4058101104 602 4150197922 603 4244408330 604 4340668315 605 4438937593 606 4539470146 607 4642169210 608 4747025717 609 4854272344 610 4963842090 611 5075694058 612 5190103815 613 5306969623 614 5426283946 615 5548299963 616 5672947719 617 5800185898 618 5930313552 619 6063224006 620 6198911489 621 6337651524 622 6479371336 623 6624029444 624 6771950497 625 6923022663 626 7077242529 627 7234909938 628 7395949414 629 7560319620 630 7728372978 631 7899992578 632 8075177953 633 8254255224 634 8437146479 635 8623811004 636 8814631279 637 9009485486 638 9208376561 639 9411659353 640 9619253733 641 9831120113 642 10047673580 643 10268787552 644 10494469060 645 10725104292 646 10960611068 647 11200951600 648 11446576412 649 11697354228 650 11953297157 651 12214825297 652 12481854922 653 12754350704 654 13032801683 655 13317072136 656 13607180143 657 13903582715 658 14206195176 659 14514985322 660 14830484052 661 15152551595 662 15481212962 663 15816965546 664 16159724066 665 16509460481 666 16866751196 667 17231452849 668 17603598534 669 17983729558 670 18371760784 671 18767669548 672 19172081471 673 19584850218 674 20006018413 675 20436175072 676 20875236204 677 21323185504 678 21780702256 679 22247637883 680 22724046041 681 23210567670 682 23707120905 683 24213697291 684 24731034518 685 25258982376 686 25797607433 687 26347607249 688 26908903127 689 27481496248 690 28066187555 691 28662826428 692 29271494290 693 29892950357 694 30527120451 695 31174017252 696 31834510509 697 32508450492 698 33195935536 699 33897792142 700 34613952260 701 35344442076 702 36090206366 703 36851097508 704 37627233419 705 38419513878 706 39227878843 707 40052370380 708 40894014840 709 41752668407 710 42628471590 711 43522403816 712 44434415220 713 45364566554 714 46313972791 715 47282496140 716 48270302612 717 49278458616 718 50306926930 719 51355790134 720 52426259543 721 53518205668 722 54631823697 723 55768275026 724 56927537608 725 58109719414 726 59316136745 727 60546670956 728 61801550695 729 63082040563 730 64388137105 731 65719977710 732 67078992900 733 68465077906 734 69878499385 735 71320634584 736 72791502413 737 74291273866 738 75821503949 739 77382105416 740 78973387887 741 80596851688 742 82252541964 743 83940668592 744 85662922109 745 87419236805 746 89209971006 747 91036759276 748 92899677746 749 94798981000 750 96736506897 751 98712216076 752 100726522024 753 102781205584 754 104876379522 755 107012349200 756 109191113177 757 111412663685 758 113677476618 759 115987492412 760 118342866486 761 120743962178 762 123192953326 763 125689869516 764 128235257180 765 130831230968 766 133477995708 767 136175981068 768 138927551469 769 141732780903 770 144592295333 771 147508399636 772 150481355699 773 153511668490 774 156601910246 775 159752207310 776 162963274891 777 166237625586 778 169575587231 779 172977750040 780 176446913065 781 179983263349 782 183587616814 783 187262712886 784 191008955154 785 194827030272 786 198719984594 787 202688075858 788 206732233323 789 210855443728 790 215058197623 791 219341290900 792 223708039327 793 228158782772 794 232694577382 795 237318680289 796 242031681426 797 246834499944 798 251730745467 799 256720852568 800 261806019771 801 266989799728 802 272272895342 803 277656364956 804 283144138809 805 288736760066 806 294435587256 807 300244495413 808 306164316289 809 312196264909 810 318344621335 811 324610053200 812 330994098113 813 337500983380 814 344131687327 815 350887600841 816 357773385848 817 364789852292 818 371938738035 819 379224655680 820 386648749162 821 394212607263 822 401921308671 823 409775825651 824 417778119856 825 425933224852 826 434242472146 827 442707672884 828 451334360180 829 460123691056 830 469077877416 831 478202412710 832 487498840725 833 496969221335 834 506619584146 835 516451295918 836 526466847976 837 536672236278 838 547069244111 839 557660210116 840 568451706138 841 579445336106 842 590643903312 843 602053953236 844 613677538685 845 625517310636 846 637580432527 847 649868776955 848 662385495035 849 675137732926 850 688127846697 851 701358836544 852 714838512026 853 728569049304 854 742553986697 855 756801127286 856 771313168086 857 786093499124 858 801150636136 859 816487097012 860 832106851597 861 848018421241 862 864224885712 863 880730070210 864 897543261722 865 914667362924 866 932106824339 867 949870952214 868 967963255686 869 986388045483 870 1005155450893 871 1024268807788 872 1043733100689 873 1063558494528 874 1083748979447 875 1104309407442 876 1125250827925 877 1146577063092 878 1168293691321 879 1190411816970 880 1212935967845 881 1235871599052 882 1259230765545 883 1283017834772 884 1307239045453 885 1331906528600 886 1357025413724 887 1382601827276 888 1408648922967 889 1435171679008 890 1462177067457 891 1489678342407 892 1517681305720 893 1546192830091 894 1575227270203 895 1604790288106 896 1634889669517 897 1665539897374 898 1696747523326 899 1728520250246 900 1760873745238 901 1793814434942 902 1827351007767 903 1861499290772 904 1896266671878 905 1931661776584 906 1967701705900 907 2004393740836 908 2041747571001 909 2079780493284 910 2118500828137 911 2157918224951 912 2198051352391 913 2238908444965 914 2280500302081 915 2322845828408 916 2365954382692 917 2409836750732 918 2454513315146 919 2499993373136 920 2546288953849 921 2593420720853 922 2641399187955 923 2690236402164 924 2739954618784 925 2790564319554 926 2842078895543 927 2894520934425 928 2947902234303 929 3002236240284 930 3057547254977 931 3113847079422 932 3171150611459 933 3229482543800 934 3288856102038 935 3349286280192 936 3410799619524 937 3473409387893 938 3537132151007 939 3601994904370 940 3668012458846 941 3735201523786 942 3803591087742 943 3873196049572 944 3944034819976 945 4016136912692 946 4089518898469 947 4164199385880 948 4240210038444 949 4317567567654 950 4396292423108 951 4476416873996 952 4557959443095 953 4640940840452 954 4725395653910 955 4811342607446 956 4898804404030 957 4987816327324 958 5078399063520 959 5170575647276 960 5264383863626 961 5359844669036 962 5456983256569 963 5555838206456 964 5656432602585 965 5758792049423 966 5862957827435 967 5968953368668 968 6076806615723 969 6186559754936 970 6298238525948 971 6411871372358 972 6527503396158 973 6645160773159 974 6764874480758 975 6886690650496 976 7010637960572 977 7136747991202 978 7265070022328 979 7395633268904 980 7528472056900 981 7663636832914 982 7801159526365 983 7941075181372 984 8083437644295 985 8228279494740 986 8375638752799 987 8525570584224 988 8678110514326 989 8833297409231 990 8991190108042 991 9151824913267 992 9315243918375 993 9481507450228 994 9650655008564 995 9822729676534 996 9997795751596 997 10175893652292 998 10357069962702 999 10541390654484 1000 10728899617565