1 0 2 0 3 0 4 0 5 1 6 1 7 1 8 1 9 2 10 2 11 2 12 4 13 5 14 5 15 5 16 7 17 8 18 8 19 11 20 14 21 15 22 15 23 19 24 22 25 23 26 27 27 33 28 37 29 38 30 44 31 50 32 54 33 60 34 71 35 79 36 84 37 94 38 106 39 114 40 125 41 143 42 159 43 169 44 187 45 208 46 225 47 242 48 273 49 302 50 323 51 351 52 390 53 421 54 451 55 498 56 551 57 590 58 636 59 697 60 757 61 807 62 881 63 965 64 1039 65 1113 66 1212 67 1310 68 1401 69 1513 70 1649 71 1771 72 1896 73 2048 74 2211 75 2357 76 2537 77 2745 78 2949 79 3145 80 3387 81 3641 82 3884 83 4154 84 4481 85 4800 86 5115 87 5477 88 5881 89 6261 90 6680 91 7166 92 7673 93 8158 94 8713 95 9319 96 9924 97 10552 98 11286 99 12049 100 12808 101 13630 102 14550 103 15463 104 16424 105 17499 106 18654 107 19792 108 21031 109 22382 110 23771 111 25190 112 26787 113 28482 114 30197 115 32007 116 34010 117 36054 118 38169 119 40476 120 42979 121 45494 122 48159 123 51048 124 54074 125 57149 126 60507 127 64107 128 67808 129 71649 130 75835 131 80195 132 84692 133 89487 134 94679 135 99999 136 105562 137 111516 138 117808 139 124243 140 131124 141 138481 142 146130 143 154037 144 162533 145 171449 146 180667 147 190376 148 200820 149 211637 150 222886 151 234819 152 247463 153 260463 154 274182 155 288790 156 304081 157 319866 158 336635 159 354298 160 372628 161 391770 162 412201 163 433518 164 455660 165 478952 166 503608 167 529110 168 555820 169 584079 170 613751 171 644440 172 676777 173 710812 174 746238 175 783099 176 822158 177 863026 178 905492 179 949935 180 996856 181 1045564 182 1096367 183 1149841 184 1206027 185 1264237 186 1325227 187 1389309 188 1456145 189 1525548 190 1598641 191 1675198 192 1754822 193 1837840 194 1925192 195 2016105 196 2110739 197 2209885 198 2313965 199 2421999 200 2534780 201 2652959 202 2776323 203 2904373 204 3038598 205 3179075 206 3325287 207 3477418 208 3636963 209 3803174 210 3976028 211 4156527 212 4345686 213 4542240 214 4746961 215 4960957 216 5184338 217 5416175 218 5658342 219 5911467 220 6175016 221 6448856 222 6735199 223 7033576 224 7343742 225 7666799 226 8004673 227 8355984 228 8721367 229 9102416 230 9499926 231 9912548 232 10342470 233 10791081 234 11258128 235 11743067 236 12248904 237 12775730 238 13323203 239 13892450 240 14486605 241 15104405 242 15746340 243 16414569 244 17110981 245 17833844 246 18585656 247 19368884 248 20183956 249 21029784 250 21910313 251 22826670 252 23778627 253 24767153 254 25797014 255 26867564 256 27979167 257 29134498 258 30337172 259 31585390 260 32881887 261 34230461 262 35632929 263 37087752 264 38599869 265 40171946 266 41804407 267 43498024 268 45259571 269 47089651 270 48988806 271 50960273 272 53010094 273 55136878 274 57343721 275 59636135 276 62018233 277 64488236 278 67052264 279 69715283 280 72479163 281 75344445 282 78320452 283 81410078 284 84614571 285 87937716 286 91388962 287 94968300 288 98679434 289 102529903 290 106527484 291 110670874 292 114967582 293 119425683 294 124049875 295 128840830 296 133810968 297 138966754 298 144311293 299 149849184 300 155594389 301 161549646 302 167720028 303 174115678 304 180749735 305 187622524 306 194743567 307 202125224 308 209776915 309 217700164 310 225911382 311 234422488 312 243240211 313 252370442 314 261833219 315 271636234 316 281787231 317 292299649 318 303194402 319 314475588 320 326155758 321 338252933 322 350784147 323 363753443 324 377182407 325 391090743 326 405491760 327 420393958 328 435825354 329 451801553 330 468335485 331 485445272 332 503162614 333 521498538 334 540470728 335 560104987 336 580429829 337 601454513 338 623207928 339 645720917 340 669017619 341 693111370 342 718041047 343 743834571 344 770513945 345 798104111 346 826651815 347 856180009 348 886714923 349 918292994 350 950959777 351 984734495 352 1019656567 353 1055772315 354 1093123160 355 1131731496 356 1171651026 357 1212927874 358 1255599465 359 1299701503 360 1345301395 361 1392441049 362 1441161135 363 1491513355 364 1543567764 365 1597360660 366 1652947547 367 1710396594 368 1769775499 369 1831122418 370 1894512090 371 1960017353 372 2027700436 373 2097614035 374 2169854321 375 2244492606 376 2321593092 377 2401229568 378 2483507212 379 2568490515 380 2656259681 381 2746913519 382 2840559038 383 2937261159 384 3037124861 385 3140261293 386 3246771663 387 3356736145 388 3470290959 389 3587551327 390 3708619356 391 3833601908 392 3962653787 393 4095883811 394 4233410772 395 4375377266 396 4521947673 397 4673230275 398 4829374716 399 4990547210 400 5156908236 401 5328581626 402 5505760384 403 5688624541 404 5877335394 405 6072049552 406 6272992222 407 6480340386 408 6694272517 409 6914993997 410 7142752286 411 7377724434 412 7620126399 413 7870202898 414 8128203245 415 8394320343 416 8668828132 417 8952000584 418 9244090061 419 9545328985 420 9856042103 421 10176508416 422 10506998445 423 10847809035 424 11199306455 425 11561773558 426 11935525893 427 12320920769 428 12718338003 429 13128077590 430 13550530492 431 13986106247 432 14435194309 433 14898142039 434 15375415853 435 15867445614 436 16374641659 437 16897434410 438 17436359769 439 17991860797 440 18564402051 441 19154502161 442 19762730962 443 20389552640 444 21035527991 445 21701260577 446 22387343706 447 23094298990 448 23822794662 449 24573480229 450 25346976606 451 26143910820 452 26965059686 453 27811104287 454 28682732031 455 29580693980 456 30505833617 457 31458862506 458 32440589527 459 33451895914 460 34493673663 461 35566705966 462 36671950237 463 37810373630 464 38982909875 465 40190475037 466 41434188375 467 42715080692 468 44034170174 469 45392542772 470 46791434079 471 48231924379 472 49715184726 473 51242492367 474 52815173211 475 54434400740 476 56101547083 477 57818034993 478 59585258698 479 61404559456 480 63277542562 481 65205746428 482 67190677532 483 69233905808 484 71337225285 485 73502258588 486 75730705781 487 78024409387 488 80385319570 489 82815186310 490 85315978130 491 87889768862 492 90538623417 493 93264505767 494 96069711899 495 98956511731 496 101927126391 497 104983824323 498 108129193031 499 111365645733 500 114695652142 501 118121860483 502 121647113805 503 125274007250 504 129005366357 505 132844191085 506 136793515781 507 140856213491 508 145035560971 509 149334874074 510 153757413134 511 158306454621 512 162985709577 513 167798732718 514 172749110077 515 177840638576 516 183077430530 517 188463308935 518 194002330551 519 199698810222 520 205557172248 521 211581608796 522 217776790119 523 224147520489 524 230698559505 525 237434634186 526 244361044350 527 251482981603 528 258805642537 529 266334459149 530 274075341069 531 282033882870 532 290215905514 533 298627585193 534 307275327611 535 316165229676 536 325303938991 537 334698367393 538 344355424189 539 354281918724 540 364485392669 541 374973368613 542 385753356028 543 396833112489 544 408221082290 545 419925396963 546 431954399602 547 444316897326 548 457022103643 549 470078848960 550 483496584448 551 497285196444 552 511454656598 553 526014751579 554 540976182424 555 556349774394 556 572146339966 557 588376936695 558 605053573863 559 622187994658 560 639792134354 561 657878510248 562 676460297178 563 695550227782 564 715161720085 565 735308843866 566 756005910110 567 777266947293 568 799107100074 569 821541849470 570 844586702227 571 868257389193 572 892570918984 573 917544146109 574 943194104351 575 969538534009 576 996596174457 577 1024385297482 578 1052924922707 579 1082234989027 580 1112335923903 581 1143247772266 582 1174991918926 583 1207590382724 584 1241065307283 585 1275439022287 586 1310735531743 587 1346978888854 588 1384193333999 589 1422403942753 590 1461637244267 591 1501919334737 592 1543277121606 593 1585738755042 594 1629333246622 595 1674089140274 596 1720036564446 597 1767206683930 598 1815630983276 599 1865341083638 600 1916370753685 601 1968754137567 602 2022525622511 603 2077720564128 604 2134376359585 605 2192530102693 606 2252219777785 607 2313484997154 608 2376366768520 609 2440905589138 610 2507143813718 611 2575125361864 612 2644894805035 613 2716496803420 614 2789978727255 615 2865388810580 616 2942775668195 617 3022189024919 618 3103681398222 619 3187305272818 620 3273114138036 621 3361163566422 622 3451511269885 623 3544214489448 624 3639332633282 625 3736927353921 626 3837061483982 627 3939797923192 628 4045202943792 629 4153344378667 630 4264290715889 631 4378111714887 632 4494880870151 633 4614672114618 634 4737560572968 635 4863623990682 636 4992943259239 637 5125598977357 638 5261674280978 639 5401255411133 640 5544430581569 641 5691288117098 642 5841920500831 643 5996422738190 644 6154890968624 645 6317422806779 646 6484120776819 647 6655088588860 648 6830431456181 649 7010257851868 650 7194680734426 651 7383813164237 652 7577771201049 653 7776675088435 654 7980648193534 655 8189814164600 656 8404301743814 657 8624243490687 658 8849773880430 659 9081029149315 660 9318151893754 661 9561287014969 662 9810581435523 663 10066186110271 664 10328258229000 665 10596955798108 666 10872440437972 667 11154879297009 668 11444444265363 669 11741307899253 670 12045648983487 671 12357651832182 672 12677503881998 673 13005394761919 674 13341522252637 675 13686088050110 676 14039296704593 677 14401357754261 678 14772489235624 679 15152911173470 680 15542848055681 681 15942531571743 682 16352200382840 683 16772094541424 684 17202461727960 685 17643557384385 686 18095641874871 687 18558978430994 688 19033840645485 689 19520508277990 690 20019265250113 691 20530401687298 692 21054219109833 693 21591022833788 694 22141123852988 695 22704842452823 696 23282508903905 697 23874456106246 698 24481026359975 699 25102572610138 700 25739455323009 701 26392038895228 702 27060700828039 703 27745827870119 704 28447812920304 705 29167056675055 706 29903974915691 707 30658989893170 708 31432531294671 709 32225040726078 710 33036973799874 711 33868790744671 712 34720963480840 713 35593978275098 714 36488332590076 715 37404529476459 716 38343088515412 717 39304542681547 718 40289434054912 719 41298314658050 720 42331756277652 721 43390341005627 722 44474660933420 723 45585323407043 724 46722955078748 725 47888190265787 726 49081678013946 727 50304086451767 728 51556099994412 729 52838411188330 730 54151733437449 731 55496799049472 732 56874353728028 733 58285156065340 734 59729990352236 735 61209656561623 736 62724968381503 737 64276759039014 738 65865888000766 739 67493226924120 740 69159666283251 741 70866121693217 742 72613532008197 743 74402848042445 744 76235046988799 745 78111132198365 746 80032126538118 747 81999069868729 748 84013035276123 749 86075118929597 750 88186436068564 751 90348127042385 752 92561367444934 753 94827351608054 754 97147298262786 755 99522459042138 756 101954118188298 757 104443577560070 758 106992172530645 759 109601274119155 760 112272281439457 761 115006616362109 762 117805743565721 763 120671160855394 764 123604392739675 765 126606996166897 766 129680574983074 767 132826761049130 768 136047218299989 769 139343653547366 770 142717818721395 771 146171491582897 772 149706492723762 773 153324690732874 774 157027994163698 775 160818342436202 776 164697730021451 777 168668197992896 778 172731824904476 779 176890731493725 780 181147100428102 781 185503155314002 782 189961162431074 783 194523443814853 784 199192383173295 785 203970401784550 786 208859976052792 787 213863646413411 788 218984009483507 789 224223704144493 790 229585440060285 791 235071991418788 792 240686184936398 793 246430902571877 794 252309107591311 795 258323821958860 796 264478124942568 797 270775168279719 798 277218187158073 799 283810470877258 800 290555380205479 801 297456360733316 802 304516936175498 803 311740688466605 804 319131290640957 805 326692503925424 806 334428162889411 807 342342174952052 808 350438553806776 809 358721395968951 810 367194875424724 811 375863260432549 812 384730931197991 813 393802345057541 814 403082052675872 815 412574716497886 816 422285106516436 817 432218073155577 818 442378584335534 819 452771727265608 820 463402691008405 821 474276761301910 822 485399362370986 823 496776033722422 824 508412420016048 825 520314288769666 826 532487556609742 827 544938248974032 828 557672513966369 829 570696646452090 830 584017088026665 831 597640391443098 832 611573261408073 833 625822562613020 834 640395300343100 835 655298608850634 836 670539802489350 837 686126354232369 838 702065880039931 839 718366156371250 840 735035157117866 841 752081008161133 842 769511997509881 843 787336605394432 844 805563510622171 845 824201545378050 846 843259738996971 847 862747333909062 848 882673765365050 849 903048641348265 850 923881803825935 851 945183310872424 852 966963414979061 853 989232578873653 854 1012001525460035 855 1035281187988481 856 1059082714916244 857 1083417506102003 858 1108297228261222 859 1133733759111081 860 1159739232997162 861 1186326066547520 862 1213506939157964 863 1241294762191103 864 1269702750902496 865 1298744412511160 866 1328433518205677 867 1358784115304120 868 1389810592670379 869 1421527627804302 870 1453950184764046 871 1487093556191368 872 1520973391122206 873 1555605627735638 874 1591006539333773 875 1627192771530285 876 1664181325814811 877 1701989515625527 878 1740635049209918 879 1780136026450570 880 1820510904744081 881 1861778505051902 882 1903958095380706 883 1947069336734341 884 1991132272394102 885 2036167375064425 886 2082195590887304 887 2129238260460889 888 2177317163257639 889 2226454568141503 890 2276673223160422 891 2327996295987563 892 2380447467559712 893 2434050940964187 894 2488831401992738 895 2544814016104688 896 2602024532567711 897 2660489231999339 898 2720234905401983 899 2781288905148004 900 2843679209633209 901 2907434332828023 902 2972583364840591 903 3039156037403753 904 3107182723975808 905 3176694362104759 906 3247722557218942 907 3320299607337724 908 3394458459897113 909 3470232696160200 910 3547656658551789 911 3626765403393820 912 3707594668332647 913 3790180925234986 914 3874561470525427 915 3960774324308488 916 4048858264412080 917 4138852908236855 918 4230798728350425 919 4324736954523325 920 4420709686467152 921 4518759938592968 922 4618931595754258 923 4721269381167699 924 4825819009276287 925 4932627148300815 926 5041741375177353 927 5153210227677068 928 5267083326019896 929 5383411263634244 930 5502245631769999 931 5623639118681075 932 5747645547102188 933 5874319754155994 934 6003717711219857 935 6135896593327811 936 6270914737760045 937 6408831591180764 938 6549707890072200 939 6693605638829931 940 6840588052034167 941 6990719602307773 942 7144066179339167 943 7300694975589686 944 7460674498421257 945 7624074687053060 946 7790966979668883 947 7961424170083524 948 8135520532245680 949 8313331919195017 950 8494935730032054 951 8680410831747534 952 8869837768804286 953 9063298763740677 954 9260877647676178 955 9462659899544761 956 9668732849088511 957 9879185562389092 958 10094108838547064 959 10313595344130591 960 10537739719109290 961 10766638410219303 962 11000389796979180 963 11239094325294039 964 11482854490214516 965 11731774727952512 966 11985961655642621 967 12245524102694047 968 12510573031859070 969 12781221564658014 970 13057585235269392 971 13339781882590521 972 13627931628853915 973 13922157030443526 974 14222583233437381 975 14529337785036358 976 14842550757357088 977 15162354920856132 978 15488885752555880 979 15822281294018611 980 16162682421614746 981 16510232918254530 982 16865079389276394 983 17227371268089116 984 17597261128101291 985 17974904590200542 986 18360460281462890 987 18754090000208740 988 19155958933555160 989 19566235450210650 990 19985091217896327 991 20412701421639150 992 20849244809729189 993 21294903514159079 994 21749863350973849 995 22214313943401207 996 22688448639257648 997 23172464490234701 998 23666562629140744 999 24170948204185001 1000 24685830317145658