1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 4 16 4 17 4 18 4 19 4 20 4 21 4 22 10 23 11 24 11 25 11 26 11 27 11 28 11 29 22 30 25 31 26 32 26 33 26 34 26 35 26 36 44 37 51 38 54 39 55 40 55 41 55 42 55 43 84 44 98 45 105 46 108 47 109 48 109 49 109 50 153 51 178 52 193 53 200 54 203 55 204 56 204 57 270 58 313 59 341 60 356 61 363 62 366 63 367 64 463 65 532 66 582 67 611 68 626 69 633 70 636 71 775 72 884 73 968 74 1021 75 1050 76 1065 77 1072 78 1269 79 1435 80 1572 81 1663 82 1717 83 1746 84 1761 85 2039 86 2289 87 2505 88 2657 89 2751 90 2805 91 2834 92 3221 93 3587 94 3921 95 4166 96 4325 97 4420 98 4474 99 5010 100 5543 101 6046 102 6433 103 6693 104 6855 105 6950 106 7687 107 8447 108 9195 109 9789 110 10205 111 10472 112 10635 113 11644 114 12723 115 13814 116 14714 117 15362 118 15793 119 16063 120 17437 121 18946 122 20521 123 21856 124 22850 125 23527 126 23965 127 25832 128 27934 129 30176 130 32135 131 33629 132 34677 133 35369 134 37896 135 40792 136 43956 137 46785 138 49003 139 50592 140 51669 141 55081 142 59058 143 63475 144 67524 145 70766 146 73146 147 74789 148 79386 149 84799 150 90923 151 96646 152 101336 153 104844 154 107319 155 113498 156 120845 157 129260 158 137289 159 143991 160 149109 161 152780 162 161071 163 170974 164 182470 165 193619 166 203113 167 210485 168 215872 169 226975 170 240288 171 255880 172 271263 173 284576 174 295103 175 302910 176 317755 177 335553 178 356593 179 377640 180 396170 181 411043 182 422255 183 442063 184 465800 185 494021 186 522655 187 548230 188 569086 189 585021 190 611412 191 642925 192 680614 193 719296 194 754364 195 783352 196 805822 197 840908 198 882651 199 932726 200 984724 201 1032465 202 1072489 203 1103898 204 1150469 205 1205549 206 1271827 207 1341306 208 1405929 209 1460774 210 1504374 211 1566054 212 1638578 213 1725918 214 1818345 215 1905280 216 1979995 217 2040065 218 2121610 219 2216784 220 2331487 221 2453808 222 2570166 223 2671286 224 2753540 225 2861100 226 2985743 227 3135808 228 3297051 229 3451952 230 3588092 231 3699989 232 3841593 233 4004346 234 4200080 235 4411674 236 4616950 237 4799195 238 4950582 239 5136560 240 5348656 241 5603096 242 5879775 243 6150519 244 6393330 245 6596971 246 6840728 247 7116387 248 7446235 249 7806585 250 8162220 251 8484098 252 8756674 253 9075386 254 9432961 255 9859288 256 10327096 257 10792268 258 11217138 259 11580127 260 11995945 261 12458635 262 13008277 263 13613453 264 14219656 265 14777954 266 15259182 267 15800363 268 16397923 269 17104642 270 17885216 271 18672223 272 19403001 273 20038070 274 20740853 275 21510812 276 22417404 277 23421041 278 24439347 279 25392039 280 26226713 281 27137118 282 28127341 283 29287479 284 30574446 285 31887539 286 33125116 287 34217615 288 35394337 289 36665042 290 38146459 291 39792047 292 41480073 293 43081870 294 44506499 295 46023764 296 47651353 297 49538763 298 51637685 299 53800984 300 55867434 301 57718213 302 59670182 303 61750519 304 64150364 305 66820590 306 69585178 307 72242230 308 74638400 309 77143655 310 79797771 311 82842810 312 86232053 313 89755082 314 93161275 315 96252947 316 99461177 317 102840494 318 106696892 319 110988590 320 115466492 321 119819813 322 123796263 323 127895201 324 132190039 325 137064443 326 142487325 327 148164169 328 153712530 329 158810920 330 164036427 331 169484174 332 175634289 333 182471582 334 189651123 335 196702895 336 203220674 337 209867407 338 216765161 339 224510594 340 233114093 341 242172435 342 251111930 343 259420154 344 267856637 345 276573858 346 286311769 347 297115880 348 308519253 349 319822689 350 330384479 351 341069361 352 352066572 353 364288184 354 377830544 355 392154327 356 406412628 357 419803303 358 433307792 359 447155937 360 462469655 361 479412361 362 497367177 363 515309996 364 532244394 365 549276783 366 566684832 367 585841091 368 607000856 369 629460980 370 651990055 371 673352738 372 694791619 373 716635859 374 740561178 375 766941129 376 794982635 377 823207677 378 850093124 379 877024131 380 904388765 381 934222924 382 967056571 383 1001999432 384 1037286780 385 1071044354 386 1104809023 387 1139030135 388 1176176051 389 1216974599 390 1260438267 391 1304464006 392 1346756823 393 1389007258 394 1431732232 395 1477911237 396 1528527469 397 1582492874 398 1637313546 399 1690184902 400 1742955316 401 1796208312 402 1853532964 403 1916231144 404 1983121335 405 2051252105 406 2117211269 407 2182998691 408 2249267316 409 2320322961 410 2397871382 411 2480642334 412 2565159239 413 2647278991 414 2729147523 415 2811479544 416 2899430240 417 2995203844 418 3097460992 419 3202115279 420 3304156312 421 3405855567 422 3507984824 423 3616693015 424 3734807012 425 3860937513 426 3990302992 427 4116856241 428 4242972480 429 4369460857 430 4503640723 431 4649100387 432 4804440945 433 4964080150 434 5120746413 435 5276875321 436 5433294832 437 5598686959 438 5777579873 439 5968608347 440 6165284131 441 6358880535 442 6551845363 443 6744985253 444 6948577836 445 7168291362 446 7402867543 447 7644783327 448 7883601534 449 8121703643 450 8359832714 451 8610114957 452 8879611920 453 9167253853 454 9464356180 455 9758460346 456 10051792689 457 10344959554 458 10652239576 459 10982372322 460 11334600450 461 11698924678 462 12060521005 463 12421329533 464 12781739027 465 13158509690 466 13562414066 467 13993147840 468 14439249291 469 14883113857 470 15326246001 471 15768692197 472 16230086037 473 16723632802 474 17249680909 475 17795129708 476 18339135308 477 18882558718 478 19424962746 479 19989277623 480 20591633521 481 21233260619 482 21899253987 483 22564981448 484 23230422997 485 23894454360 486 24583802076 487 25318075653 488 26099698224 489 26911765778 490 27725252069 491 28538938729 492 29350780853 493 30191838744 494 31085876724 495 32036869606 496 33025739649 497 34018347552 498 35011913291 499 36003150503 500 37028082852 501 38115390031 502 39271070696 503 40473671288 504 41683147605 505 42894686761 506 44103389861 507 45350917852 508 46671783614 509 48074555362 510 49535235958 511 51006943413 512 52482292703 513 53954279546 514 55470985150 515 57073788304 516 58774527980 517 60546474296 518 62334882994 519 64129112763 520 65919481640 521 67761324467 522 69704121436 523 71763793454 524 73910744631 525 76081169912 526 78260389695 527 80435303092 528 82669458963 529 85021827232 530 87513433659 531 90111674381 532 92742371440 533 95385832278 534 98024675046 535 100731677337 536 103576947193 537 106587798280 538 109728564336 539 112913170420 540 116115798691 541 119313691385 542 122590014573 543 126027863437 544 129662309016 545 133454581990 546 137305047931 547 141180397439 548 145051223106 549 149012294005 550 153161872307 551 157544484445 552 162118351186 553 166768360676 554 171452155959 555 176132087563 556 180915902903 557 185919471742 558 191198858644 559 196709417567 560 202318476494 561 207972742674 562 213624473091 563 219395818228 564 225423113639 565 231776365367 566 238408403810 567 245166610396 568 251984611378 569 258802285392 570 265757782905 571 273011098167 572 280649095654 573 288622531589 574 296756262406 575 304968257297 576 313183363404 577 321557361691 578 330277621646 579 339451226274 580 349027600496 581 358806142633 582 368686245593 583 378574486326 584 388646082436 585 399119919781 586 410127341152 587 421617373213 588 433360805610 589 445234981649 590 457124453312 591 469225683780 592 481793867465 593 494989253189 594 508761826344 595 522850210491 596 537105774347 597 551386504297 598 565912082657 599 580979337793 600 596782968468 601 613275587582 602 630159858860 603 647256544431 604 664391810619 605 681810482404 606 699857149957 607 718767322441 608 738498513352 609 758713176936 610 779196249979 611 799735776057 612 820603778533 613 842199398742 614 864806492572 615 888390232494 616 912568369929 617 937083903299 618 961679475088 619 986656226927 620 1012475621755 621 1039478489302 622 1067641269571 623 1096532023376 624 1125844944582 625 1155268606314 626 1185135256364 627 1215977260286 628 1248202579662 629 1281803259026 630 1316292450224 631 1351307555123 632 1386473089424 633 1422154127662 634 1458963706620 635 1497388521569 636 1537441742193 637 1578575878806 638 1620362599124 639 1662350541885 640 1704939285428 641 1748833287775 642 1794611560779 643 1842314983262 644 1891329508239 645 1941150733417 646 1991237832047 647 2042026101590 648 2094323593766 649 2148817114259 650 2205583466867 651 2263935630474 652 2323281601617 653 2382975100356 654 2443488137596 655 2505745702494 656 2570560420728 657 2638054757232 658 2707462214618 659 2778089941432 660 2849167867039 661 2921204965839 662 2995258193302 663 3072286486405 664 3152469935998 665 3234955631951 666 3318935149683 667 3403493165199 668 3489175377221 669 3577187112229 670 3668657369917 671 3763837969018 672 3861782738191 673 3961550863853 674 4062057209785 675 4163882815153 676 4268399752217 677 4376934018292 678 4489826280647 679 4606029969876 680 4724453263709 681 4843812607861 682 4964722114379 683 5088740564396 684 5217422033410 685 5351216118181 686 5488969085920 687 5629416965362 688 5771045129280 689 5914496792682 690 6061539677006 691 6213991096872 692 6372433717344 693 6535599851039 694 6702030067608 695 6869940800749 696 7039998951806 697 7214205207901 698 7394680525454 699 7582168827580 700 7775282489820 701 7972340310727 702 8171246662722 703 8372684246143 704 8578913305948 705 8792404035453 706 9014095219365 707 9242473718732 708 9475607679471 709 9711039616695 710 9949457908718 711 10193410922372 712 10445770272108 713 10707708692457 714 10977583412609 715 11253179517663 716 11531621094081 717 11813588562642 718 12101949816680 719 12400036637911 720 12709301973354 721 13027970372287 722 13353508463123 723 13682556833506 724 14015770992609 725 14356371857885 726 14708218359257 727 15073097272469 728 15449099826236 729 15833334717631 730 16221885289341 731 16615360268880 732 17017370150821 733 17432376229313 734 17862562172292 735 18305887303295 736 18759059513789 737 19217520392254 738 19681805223236 739 20155952742642 740 20645112056985 741 21151936565033 742 21674258853392 743 22208338505193 744 22748879809442 745 23296311163064 746 23855141370961 747 24431303064572 748 25028004574573 749 25642960402743 750 26271930554679 751 26908772918124 752 27553768792876 753 28211940844717 754 28890113580296 755 29592148356632 756 30315655876210 757 31055840167273 758 31805589666729 759 32564989120950 760 33339621941757 761 34137325568661 762 34962728563038 763 35813357615426 764 36683800349974 765 37565835723988 766 38459293087828 767 39370365053272 768 40308038564873 769 41277840447329 770 42277241394563 771 43300146682838 772 44337068244249 773 45387508721738 774 46458321129730 775 47559794112683 776 48698504627276 777 49871903692531 778 51073144198897 779 52291292361099 780 53525439971394 781 54783152455938 782 56076191282350 783 57412357361734 784 58789130120450 785 60198834339278 786 61628889964601 787 63077877138912 788 64554127712123 789 66071066170387 790 67637917979474 791 69252251208090 792 70905482959565 793 72583160172749 794 74283233221222 795 76014853912617 796 77793322890920 797 79629519148897 798 81521176154020 799 83458718269164 800 85425565583730 801 87418898528167 802 89448743081217 803 91532512300157 804 93683001957773 805 95898205035832 806 98167464993283 807 100471788986288 808 102807424203151 809 105185322520204 810 107625273287554 811 110142288756258 812 112734738421049 813 115390791926655 814 118088724022540 815 120823656387521 816 123607517071269 817 126462763402530 818 129406967477011 819 132439016636053 820 135545812174901 821 138702537506480 822 141902965959575 823 145160046541238 824 148499229269204 825 151941036000963 826 155485044565734 827 159116790208152 828 162807965212981 829 166550733948906 830 170359106480550 831 174261883408796 832 178282981623413 833 182422875683459 834 186665637988349 835 190979021915976 836 195353282204525 837 199803520235213 838 204362284267620 839 209057390632148 840 213890459242342 841 218844002473528 842 223881337353482 843 228990459418815 844 234187582215310 845 239509438006058 846 244988316804980 847 250627278305637 848 256407182612633 849 262286354979406 850 268250130099034 851 274315838550188 852 280524879052843 853 286914664279959 854 293490044978200 855 300230140826358 856 307087669943129 857 314044841645226 858 321120092281502 859 328360015528369 860 335807883393288 861 343470750697332 862 351325919567671 863 359319816053990 864 367430992390731 865 375678954950474 866 384116074646111 867 392792313459566 868 401717418921328 869 410866809400202 870 420179862155363 871 429630860254253 872 439240318872400 873 449067021892134 874 459168561542080 875 469557949156580 876 480208673098533 877 491052222240138 878 502057912356449 879 513247170125811 880 524685890243697 881 536440353027340 882 548527504528493 883 560918877814115 884 573537148483918 885 586345864787456 886 599367229356016 887 612675006900861 888 626345360109826 889 640399949847736 890 654808361315819 891 669483434021346 892 684382038978909 893 699526967546894 894 715000684591054 895 730890575848640 896 747223927969849 897 763968421048970 898 781025935230326 899 798345625638008 900 815950629663907 901 833933011999435 902 852392891169141 903 871364234046296 904 890812908979606 905 910628598756483 906 930751565549900 907 951204977668662 908 972091479285244 909 993525612888429 910 1015549250522641 911 1038126597641970 912 1061133784514545 913 1084500841386538 914 1108250573981239 915 1132497263224367 916 1157371775304362 917 1182925299604197 918 1209120602805224 919 1235818774398903 920 1262938099836360 921 1290500529008711 922 1318633125694284 923 1347485203352408 924 1377118901717429 925 1407495856129060 926 1438460491851263 927 1469917634497701 928 1501887776303527 929 1534511995081280 930 1567960431305639 931 1602308050842557 932 1637515773986101 933 1673409585607346 934 1709878919266648 935 1746942072325570 936 1784755464659419 937 1823512718375800 938 1863303785735725 939 1904089409465180 940 1945675203809052 941 1987933027018928 942 2030878096388029 943 2074683593046830 944 2119569588658088 945 2165643495095961 946 2212866569100010 947 2261021951053673 948 2309961471018650 949 2359696199481396 950 2410417601186914 951 2462375501294282 952 2515697609081785 953 2570346559043407 954 2626080741437764 955 2682729195250192 956 2740297578469446 957 2798997256621857 958 2859111493817087 959 2920791535775295 960 2984002472929004 961 3048475476108042 962 3114013697551354 963 3180615876218297 964 3248515002152752 965 3318031872783500 966 3389344974254297 967 3462423171220309 968 3536967754868509 969 3612752514314824 970 3689767498549043 971 3768269140447136 972 3848620327679383 973 3931031002614278 974 4015475416663765 975 4101622109721939 976 4189211623059227 977 4278223228259588 978 4368938724761727 979 4461768142759022 980 4556957686879320 981 4654488937697695 982 4753994606146695 983 4855177636013677 984 4958004086181625 985 5062783134928590 986 5169977565608373 987 5279875300867712 988 5392467591858191 989 5507348016705413 990 5624177073957393 991 5742904762091144 992 5863869748028130 993 5987593776259222 994 6114412689208910 995 6244330197612846 996 6376897227020832 997 6511726418452438 998 6648748408738838 999 6788333537425233 1000 6931069389111855