1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 1 10 0 11 0 12 1 13 0 14 0 15 2 16 2 17 0 18 2 19 2 20 0 21 3 22 4 23 3 24 3 25 4 26 4 27 4 28 6 29 8 30 8 31 6 32 9 33 11 34 8 35 13 36 18 37 13 38 14 39 21 40 19 41 18 42 29 43 30 44 25 45 32 46 38 47 35 48 40 49 51 50 52 51 50 52 59 53 66 54 67 55 73 56 89 57 93 58 89 59 104 60 119 61 115 62 129 63 156 64 154 65 153 66 186 67 195 68 195 69 228 70 254 71 251 72 269 73 304 74 319 75 333 76 374 77 407 78 417 79 438 80 493 81 520 82 538 83 602 84 655 85 659 86 709 87 790 88 818 89 858 90 962 91 1014 92 1039 93 1128 94 1228 95 1271 96 1357 97 1485 98 1562 99 1620 100 1749 101 1881 102 1967 103 2086 104 2269 105 2384 106 2477 107 2666 108 2866 109 2975 110 3170 111 3433 112 3581 113 3735 114 4038 115 4278 116 4462 117 4770 118 5108 119 5319 120 5601 121 5993 122 6336 123 6634 124 7064 125 7520 126 7863 127 8253 128 8823 129 9306 130 9735 131 10352 132 11003 133 11457 134 12070 135 12867 136 13515 137 14152 138 15061 139 15895 140 16586 141 17494 142 18569 143 19460 144 20438 145 21653 146 22809 147 23822 148 25111 149 26561 150 27853 151 29205 152 30906 153 32492 154 33931 155 35737 156 37766 157 39491 158 41449 159 43794 160 45925 161 47960 162 50556 163 53214 164 55648 165 58423 166 61577 167 64459 168 67418 169 70906 170 74535 171 77921 172 81750 173 85992 174 89997 175 94033 176 98864 177 103750 178 108390 179 113650 180 119439 181 124769 182 130439 183 136996 184 143528 185 149872 186 157155 187 164787 188 172085 189 179888 190 188705 191 197416 192 206192 193 215936 194 226191 195 236068 196 246702 197 258466 198 270239 199 282011 200 295209 201 308863 202 322158 203 336512 204 352348 205 367876 206 383872 207 401547 208 419636 209 437441 210 456934 211 477757 212 498523 213 520025 214 543522 215 567402 216 591419 217 617274 218 644937 219 672485 220 701201 221 732271 222 763987 223 795768 224 830315 225 866743 226 903175 227 941300 228 982496 229 1024002 230 1066364 231 1112060 232 1159894 233 1207866 234 1258580 235 1312441 236 1367116 237 1423108 238 1483313 239 1545822 240 1609192 241 1675741 242 1746437 243 1818019 244 1891784 245 1970617 246 2052531 247 2135297 248 2222850 249 2315069 250 2408581 251 2505222 252 2608569 253 2714831 254 2823272 255 2937701 256 3057654 257 3179319 258 3306041 259 3440144 260 3578394 261 3719678 262 3868726 263 4024121 264 4182614 265 4347213 266 4521502 267 4700465 268 4884077 269 5077331 270 5278728 271 5483616 272 5697629 273 5922903 274 6154146 275 6391794 276 6642250 277 6901472 278 7166654 279 7443410 280 7733933 281 8031654 282 8339147 283 8661512 284 8995394 285 9337086 286 9694107 287 10067297 288 10450614 289 10846003 290 11260867 291 11689189 292 12128605 293 12587285 294 13066449 295 13557292 296 14065590 297 14597255 298 15145712 299 15708825 300 16297582 301 16909562 302 17538098 303 18188936 304 18868785 305 19568882 306 20289972 307 21041742 308 21823106 309 22625131 310 23456681 311 24323166 312 25216162 313 26135264 314 27094469 315 28088633 316 29110222 317 30169222 318 31272344 319 32406735 320 33577371 321 34796865 322 36059564 323 37357053 324 38704008 325 40102775 326 41542814 327 43028912 328 44576301 329 46175536 330 47821660 331 49528234 332 51300146 333 53122831 334 55005897 335 56963559 336 58986807 337 61067933 338 63227621 339 65465718 340 67768846 341 70148247 342 72621690 343 75172972 344 77801274 345 80526467 346 83348434 347 86251320 348 89253825 349 92368713 350 95582473 351 98892919 352 102325354 353 105874711 354 109528962 355 113305941 356 117223816 357 121261852 358 125424364 359 129736788 360 134195119 361 138782230 362 143527325 363 148442619 364 153508227 365 158729775 366 164139960 367 169724970 368 175476068 369 181422575 370 187578943 371 193919496 372 200460373 373 207229696 374 214217334 375 221411203 376 228850746 377 236544328 378 244470198 379 252643097 380 261101460 381 269824749 382 278809047 383 288095908 384 297697217 385 307581426 386 317779794 387 328325383 388 339198525 389 350395612 390 361971832 391 373926225 392 386236790 393 398935555 394 412062392 395 425588376 396 439523910 397 453921059 398 468785558 399 484087364 400 499874696 401 516182267 402 532985469 403 550292039 404 568172948 405 586619574 406 605611067 407 625200227 408 645430778 409 666262869 410 687727103 411 709891288 412 732749388 413 756276964 414 780549293 415 805596412 416 831389540 417 857960375 418 885392598 419 913666264 420 942773938 421 972790439 422 1003759251 423 1035637817 424 1068482000 425 1102373576 426 1137298955 427 1173243434 428 1210313317 429 1248536390 430 1287880382 431 1328408720 432 1370223384 433 1413287943 434 1457616900 435 1503318168 436 1550427919 437 1598905122 438 1648847908 439 1700346383 440 1753378273 441 1807956402 442 1864219039 443 1922186877 444 1981839153 445 2043277447 446 2106619253 447 2171819833 448 2238924629 449 2308077655 450 2379312733 451 2452595413 452 2528076812 453 2605860781 454 2685914909 455 2768292842 456 2853177763 457 2940575942 458 3030489384 459 3123078436 460 3218469358 461 3316612164 462 3417609322 463 3521640100 464 3628733547 465 3738885469 466 3852308801 467 3969116944 468 4089284273 469 4212919107 470 4340252791 471 4471286315 472 4606057899 473 4744799147 474 4887653154 475 5034569199 476 5185727571 477 5341356800 478 5501477980 479 5666137123 480 5835635233 481 6010087507 482 6189487933 483 6374034400 484 6564005496 485 6759399276 486 6960327798 487 7167103784 488 7379885456 489 7598650496 490 7823678848 491 8055250992 492 8293399958 493 8538245725 494 8790193721 495 9049373510 496 9315815934 497 9589836794 498 9871780608 499 10161646785 500 10459655727 501 10766232512 502 11081547306 503 11405632822 504 11738916643 505 12081730245 506 12434133811 507 12796375726 508 13168979779 509 13552093397 510 13945834814 511 14350667570 512 14767009125 513 15194896538 514 15634699331 515 16086974698 516 16551930405 517 17029689187 518 17520867042 519 18025871743 520 18544812970 521 19078119433 522 19626474702 523 20190050196 524 20769102541 525 21364305325 526 21976155126 527 22604761871 528 23250724397 529 23914750339 530 24597105203 531 25298080714 532 26018525256 533 26758937874 534 27519544738 535 28301016246 536 29104225875 537 29929415960 538 30777047195 539 31648057888 540 32543067183 541 33462307685 542 34406687148 543 35377118361 544 36373955148 545 37397741986 546 38449645396 547 39530275470 548 40640047752 549 41779985751 550 42951185843 551 44154009192 552 45389244741 553 46658156694 554 47961525190 555 49299816758 556 50674342644 557 52086266701 558 53536120675 559 55024808400 560 56553895136 561 58124175167 562 59736352769 563 61391918797 564 63092276426 565 64837976355 566 66630272266 567 68470870285 568 70360766448 569 72300788472 570 74292811337 571 76338307101 572 78438088342 573 80593602285 574 82806907721 575 85079061736 576 87411241850 577 89805543818 578 92263761276 579 94786789316 580 97376518953 581 100035215062 582 102764223169 583 105564902910 584 108439863807 585 111391016284 586 114419599858 587 117527812539 588 120718377566 589 123992728842 590 127352734739 591 130801320531 592 134340782338 593 137972547264 594 141699420472 595 145524370718 596 149449252215 597 153476244169 598 157608900499 599 161849716183 600 166200625183 601 170664838897 602 175245931401 603 179945943157 604 184767720682 605 189715267977 606 194791604259 607 199998949718 608 205341343418 609 210822711007 610 216445642681 611 222213483035 612 228131060470 613 234201658258 614 240428237031 615 246815425429 616 253367890129 617 260088566211 618 266981728508 619 274052773395 620 281305711750 621 288743991086 622 296373290620 623 304198788642 624 312224210437 625 320454519729 626 328896201643 627 337553693560 628 346431436018 629 355535952262 630 364873403034 631 374448024222 632 384266067869 633 394334806212 634 404659618117 635 415245725768 636 426101051710 637 437232423296 638 448645213283 639 460346684769 640 472345471712 641 484647632179 642 497259788995 643 510190972173 644 523449331353 645 537041062661 646 550975111735 647 565261209400 648 579906724906 649 594919392972 650 610310109254 651 626087985430 652 642260751554 653 658838810745 654 675833686651 655 693253711817 656 711108583103 657 729410728033 658 748170958885 659 767398288633 660 787105394445 661 807305232084 662 828007973072 663 849224959850 664 870971005182 665 893258317989 666 916098070634 667 939504903536 668 963494153648 669 988077452561 670 1013268761017 671 1039085006232 672 1065540701113 673 1092648848708 674 1120427154945 675 1148892936728 676 1178060294507 677 1207945577386 678 1238568865183 679 1269946580105 680 1302094751734 681 1335033814637 682 1368784150235 683 1403362041970 684 1438787421825 685 1475083158329 686 1512268821696 687 1550363130275 688 1589390513585 689 1629374104362 690 1670333620336 691 1712292274010 692 1755277115184 693 1799310450170 694 1844415080699 695 1890619204469 696 1937950039766 697 1986430383999 698 2036088330306 699 2086954728316 700 2139056066510 701 2192419033447 702 2247077146826 703 2303061314388 704 2360399107040 705 2419123208201 706 2479269883120 707 2540869533805 708 2603954465379 709 2668563220311 710 2734732189490 711 2802493390123 712 2871885969908 713 2942951377547 714 3015725729658 715 3090246713745 716 3166559956334 717 3244706952999 718 3324726174724 719 3406663135805 720 3490566461351 721 3576477674744 722 3664442153592 723 3754512351101 724 3846736986862 725 3941160884925 726 4037838242390 727 4136824584756 728 4238169260213 729 4341925186503 730 4448154071275 731 4556911707601 732 4668251782078 733 4782237073105 734 4898932651223 735 5018395477622 736 5140688762249 737 5265883468760 738 5394045109630 739 5525236166171 740 5659531051473 741 5797004202463 742 5937723098243 743 6081761419073 744 6229202393350 745 6380121130739 746 6534592243214 747 6692701827705 748 6854536848354 749 7020175453085 750 7189705225557 751 7363221711181 752 7540813135415 753 7722566383621 754 7908582892988 755 8098962353662 756 8293797236494 757 8493189330061 758 8697250451752 759 8906082041881 760 9119787299552 761 9338483502822 762 9562287022333 763 9791304966439 764 10025657841623 765 10265474043816 766 10510872501676 767 10761973415735 768 11018914464247 769 11281829068733 770 11550843815040 771 11826098582182 772 12107743125669 773 12395914544169 774 12690755121491 775 12992423680489 776 13301075905131 777 13616858597777 778 13939936495745 779 14270481656445 780 14608654744932 781 14954621167382 782 15308566848809 783 15670670557116 784 16041105249911 785 16420061948359 786 16807741009998 787 17204327744135 788 17610017349331 789 18025024143361 790 18449556365169 791 18883814755513 792 19328023509133 793 19782412671923 794 20247199310676 795 20722610152212 796 21208895190023 797 21706293903785 798 22215042338488 799 22735399881870 800 23267634114007 801 23811995718745 802 24368751166494 803 24938188495602 804 25520586511353 805 26116218928807 806 26725389307721 807 27348405008765 808 27985559148281 809 28637160964999 810 29303545712274 811 29985034098927 812 30681947371338 813 31394636331829 814 32123457813349 815 32868750658318 816 33630877263052 817 34410223412146 818 35207162317929 819 36022066384058 820 36855344751798 821 37707407528293 822 38578650497811 823 39469493432709 824 40380384581087 825 41311753618025 826 42264036386914 827 43237705249413 828 44233235875522 829 45251085664000 830 46291745290123 831 47355730349092 832 48443540213248 833 49555679901659 834 50692699031989 835 51855144159484 836 53043548975657 837 54258481170207 838 55500538531162 839 56770296396825 840 58068344589013 841 59395316674447 842 60751846120328 843 62138549753258 844 63556089158942 845 65005151767202 846 66486405766506 847 68000533696620 848 69548271285500 849 71130346615767 850 72747478087225 851 74400430291448 852 76089999156009 853 77816954425302 854 79582091701730 855 81386258324834 856 83230297112755 857 85115038282839 858 87041370886483 859 89010209535217 860 91022447566182 861 93079004812859 862 95180863040950 863 97328991226394 864 99524354966030 865 101767980133710 866 104060924510473 867 106404217366960 868 108798928373746 869 111246187386129 870 113747115239242 871 116302826921620 872 118914512934172 873 121583388456237 874 124310646541142 875 127097522744634 876 129945324052910 877 132855338753649 878 135828861887601 879 138867265653820 880 141971953500638 881 145144300041405 882 148385739402164 883 151697774123416 884 155081893378359 885 158539591687910 886 162072458000086 887 165682104258768 888 169370122319867 889 173138166509337 890 176987972524082 891 180921252006894 892 184939737801096 893 189045259538680 894 193239677116671 895 197524823715848 896 201902616213730 897 206375048643060 898 210944097531780 899 215611761302059 900 220380154996743 901 225251413698885 902 230227658291710 903 235311097661295 904 240504031759948 905 245808732228829 906 251227512817120 907 256762805971282 908 262417073116494 909 268192755748348 910 274092408447459 911 280118671916889 912 286274167314501 913 292561560252135 914 298983658394007 915 305543286518724 916 312243265756353 917 319086536888477 918 326076142220929 919 333215092996105 920 340506471137694 921 347953502648630 922 355559440717158 923 363327531439712 924 371261170477790 925 379363848157199 926 387639036373149 927 396090282637009 928 404721304694373 929 413535834871742 930 422537619984782 931 431730564397803 932 441118685130505 933 450705969492248 934 460496512637668 935 470494582637270 936 480704474401183 937 491130495880614 938 501777148849082 939 512649039261720 940 523750759891258 941 535087020394813 942 546662733102860 943 558482822986062 944 570552257210962 945 582876206829576 946 595459966944664 947 608308810118473 948 621428165695366 949 634823667755123 950 648500979300089 951 662465807528033 952 676724105732019 953 691281942117413 954 706145384700034 955 721320670951147 956 736814277895359 957 752632696672671 958 768782499767098 959 785270519156031 960 802103724632009 961 819289078141986 962 836833761074719 963 854745196292038 964 873030841021536 965 891698241540405 966 910755253191816 967 930209858183879 968 950070061955116 969 970344107110142 970 991040516909336 971 1012167835452637 972 1033734743576383 973 1055750246870920 974 1078223505793425 975 1101163700033302 976 1124580306747162 977 1148483086746669 978 1172881848145677 979 1197786549265835 980 1223207532358748 981 1249155282805099 982 1275640345862091 983 1302673589260404 984 1330266209431774 985 1358429437567961 986 1387174716892619 987 1416513893598756 988 1446458989945524 989 1477022090780540 990 1508215676577702 991 1540052559323666 992 1572545621913415 993 1605707980976334 994 1639553224630974 995 1674095106630762 996 1709347497054899 997 1745324693537643 998 1782041378698313 999 1819512296874095 1000 1857752503302592