1 1 2 2 3 3 4 4 5 8 6 9 7 15 8 27 9 63 10 195 11 728 12 1443 13 3843 14 5475 15 6174 16 11913 17 13376 18 24963 19 37635 20 77283 21 98595 22 113398 23 158403 24 178083 25 209763 26 293763 27 294335 28 319124 29 376995 30 406503 31 438243 32 454275 33 538755 34 574563 35 770883 36 996003 37 1196835 38 1331715 39 1444803 40 1473795 41 1532643 42 1569542 43 1747683 44 1909923 45 2004215 46 2114115 47 2583167 48 2630883 49 2748963 50 3076515 51 3511875 52 3692193 53 3740355 54 3894384 55 3976035 56 4072323 57 4571043 58 4791500 59 4874221 60 5410175 61 5484963 62 5903985 63 6120675 64 6543363 65 6728835 66 7616541 67 7828803 68 8168163 69 8514723 70 9375843 71 9458085 72 10355523 73 10588515 74 10626550 75 10982595 76 12376323 77 13942755 78 15331678 79 16176483 80 16467363 81 16632265 82 17455683 83 18164643 84 18267075 85 18992163 86 19165223 87 19731363 88 20811843 89 21362883 90 21386000 91 23046815 92 23569545 93 23755773 94 24344355 95 25786083 96 26030403 97 26152995 98 27201419 99 27394755 100 27841131 101 29311395 102 29571843 103 30833293 104 31158723 105 32188785 106 32359584 107 32512803 108 36457443 109 36893475 110 37478883 111 37625955 112 38663523 113 39437817 114 40170243 115 40475043 116 40627875 117 44063043 118 44382243 119 45995523 120 48244536 121 48972003 122 49815363 123 52041795 124 54671235 125 55026723 126 55920483 127 56821443 128 60124515 129 62948355 130 63520159 131 64866915 132 65642403 133 66863328 134 67287267 135 67601283 136 69189123 137 69534828 138 69789315 139 71605443 140 72624483 141 73545237 142 74849554 143 75307683 144 75933795 145 78766388 146 79103235 147 81252195 148 83429955 149 84309123 150 85414563 151 86081283 152 92198403 153 93354243 154 94517283 155 96393123 156 98049603 157 99480675 158 106791555 159 107288163 160 108110513 161 108161673 162 109286115 163 110209582 164 117462243 165 117983043 166 120077763 167 123520995 168 124590243 169 128097123 170 132204003 171 136375683 172 136936803 173 139072558 174 145781475 175 147816963 176 149866563 177 151339203 178 154306083 179 154604355 180 155201763 181 157301763 182 157602915 183 158810403 184 161849283 185 162766563 186 164916963 187 165225315 188 168245433 189 171452835 190 172946915 191 176690544 192 179077923 193 180042723 194 187197123 195 193822083 196 194156355 197 206354834 198 208455843 199 212984835 200 217208643 201 219691683 202 220645600 203 225420195 204 227225475 205 228674883 206 228841535 207 232318563 208 233417283 209 235991043 210 236359875 211 238683249 212 245189130 213 246055509 214 246110898 215 247558755 216 252873603 217 257089155 218 266799555 219 268369923 220 269550723 221 269931199 222 274697475 223 276689955 224 277488963 225 286354083 226 289241040 227 290429763 228 290838915 229 291658083 230 295642355 231 297838563 232 299082435 233 301994883 234 305115051 235 319765923 236 324504195 237 327537603 238 328841955 239 330585123 240 331895523 241 333208515 242 334963203 243 335402595 244 335727281 245 337558221 246 338486403 247 341584323 248 344250915 249 347024817 250 347279760 251 347375043 252 353214435 253 359273291 254 361755134 255 369364151 256 370100643 257 377991363 258 379392483 259 388799523 260 392119203 261 392594595 262 394499043 263 414285315 264 421645155 265 426092163 266 428076076 267 434080682 268 435056163 269 441084003 270 443607843 271 449185635 272 452753283 273 454286595 274 455135439 275 465610083 276 468405441 277 469242243 278 469762275 279 472437513 280 473815228 281 476025123 282 478239898 283 488144835 284 506278067 285 506340003 286 509585475 287 511671964 288 511754883 289 516804316 290 527032050 291 528184787 292 528724035 293 531486915 294 537034275 295 543734972 296 544255748 297 554979363 298 560647683 299 565203075 300 572070723 301 575424957 302 580713603 303 591823466 304 596434083 305 599368323 306 614147523 307 617124963 308 618352169 309 626701155 310 632723715 311 635144011 312 636956643 313 652874038 314 653415843 315 657491337 316 658332963 317 672572355 318 676936323 319 691374435 320 691628014 321 692637123 322 698967843 323 702144003 324 709694008 325 719419683 326 720063555 327 722641923 328 726518115 329 733001475 330 738756655 331 742780515 332 743765987 333 747366243 334 748679043 335 753941763 336 764773645 337 773551526 338 783888003 339 787251363 340 800776803 341 801959850 342 805401050 343 806219235 344 809221913 345 827983520 346 830246595 347 831630243 348 836482083 349 846926403 350 866242559 351 868716675 352 878648163 353 880758943 354 895054487 355 910953123 356 914578563 357 931348323 358 933546915 359 935014083 360 938687043 361 940158243 362 941019429 363 942367203 364 947531523 365 951969315 366 963267776 367 966090723 368 975812643 369 979909475 370 981067683 371 981819555 372 983324163 373 990864483 374 992019984 375 996917475 376 1006762317 377 1013327018 378 1015951875 379 1022848323 380 1030308327 381 1035166275 382 1048334883 383 1053188595 384 1056120003 385 1058461155 386 1063534857 387 1078071555 388 1078658928 389 1080217775 390 1085859071 391 1086787806 392 1091509443 393 1109023203 394 1119437763 395 1121848035 396 1139602563 397 1150269695 398 1153417443 399 1159947363 400 1170597795 401 1174707075 402 1182121923 403 1182343335 404 1191216195 405 1195524043 406 1217870403 407 1223740323 408 1233589819 409 1247361123 410 1261812483 411 1270665018 412 1272919683 413 1294416483 414 1299962399 415 1303065603 416 1303554847 417 1305790464 418 1313482563 419 1327436355 420 1329185763 421 1330599127 422 1339312115 423 1353798435 424 1359986883 425 1361757603 426 1362643395 427 1389351075 428 1392931683 429 1395620163 430 1402121783 431 1411805475 432 1420377827 433 1422647523 434 1437386327 435 1440809763 436 1465511523 437 1479325443 438 1480366799 439 1488527978 440 1508079555 441 1517414115 442 1519284483 443 1538051523 444 1550311875 445 1552202403 446 1578790755 447 1596934763 448 1607528835 449 1614271683 450 1617165795 451 1621553567 452 1631618118 453 1633980349 454 1656001635 455 1665782595 456 1678898384 457 1682476323 458 1699253283 459 1704203523 460 1708751746 461 1715119395 462 1729770239 463 1732057923 464 1736781975 465 1744647658 466 1755107235 467 1769211843 468 1775948750 469 1780795478 470 1791390742 471 1792506243 472 1795555875 473 1817925993 474 1831326435 475 1843819147 476 1845733443 477 1858725825 478 1859161923 479 1864339683 480 1866412803 481 1869521649 482 1876795683 483 1898693475 484 1900785603 485 1903925955 486 1910344149 487 1911263523 488 1911998865 489 1940754915 490 1944986403 491 1955585283 492 1956677702 493 1958770563 494 1961015786 495 1961958435 496 1973045711 497 2015471235 498 2022489290 499 2030583843 500 2036860881 501 2055534243 502 2063208023 503 2064248355 504 2068612323 505 2073806532 506 2075166915 507 2080636995 508 2101488963 509 2118024483 510 2120976780 511 2129084163 512 2140172643 513 2196047043 514 2201181983 515 2208436035 516 2210692323 517 2224254243 518 2242401315 519 2249022836 520 2258340483 521 2259481155 522 2270903715 523 2276625795 524 2278916643 525 2282886413 526 2284648803 527 2290388163 528 2301743795 529 2304137934 530 2315726883 531 2322661635 532 2336562243 533 2369158275 534 2377342563 535 2379683523 536 2389415849 537 2391622650 538 2404333155 539 2426744643 540 2437509213 541 2439767235 542 2442138723 543 2444275010 544 2459961603 545 2468301123 546 2483932395 547 2490317640 548 2495801763 549 2500358887 550 2522249283 551 2534316963 552 2537942883 553 2567441717 554 2578183504 555 2582875683 556 2590199235 557 2617140963 558 2623283523 559 2624245823 560 2625742563 561 2641386699 562 2650396323 563 2654104323 564 2666483043 565 2683045617 566 2710035363 567 2712534723 568 2728808643 569 2737591683 570 2751422115 571 2756460003 572 2769347180 573 2789318595 574 2794391043 575 2804549763 576 2817274083 577 2821096995 578 2838971523 579 2851773603 580 2884115521 581 2907150723 582 2929190883 583 2930489955 584 2935689123 585 2939591523 586 2961754083 587 2972212323 588 2974829763 589 2989246275 590 2994497283 591 3022140675 592 3027129343 593 3031383363 594 3067165923 595 3078050850 596 3079866787 597 3080472003 598 3095141955 599 3117882243 600 3119453402 601 3127270083 602 3128612355 603 3142050915 604 3147434403 605 3148780995 606 3150613059 607 3158215203 608 3176111448 609 3181185603 610 3185247843 611 3195866339 612 3197233094 613 3215116803 614 3223287075 615 3228739683 616 3232832163 617 3236927235 618 3257441475 619 3260181603 620 3269157534 621 3271153635 622 3276646563 623 3291775875 624 3299006099 625 3301421763 626 3316258455 627 3347085315 628 3370248783 629 3381887715 630 3412662723 631 3415467363 632 3415837068 633 3426514952 634 3426697443 635 3430913475 636 3444985635 637 3453472517 638 3454907539 639 3487374915 640 3504403203 641 3507245283 642 3514355523 643 3521472963 644 3532035100 645 3550113540 646 3580107555 647 3588870384 648 3626207523 649 3640674243 650 3642551860 651 3645019875 652 3676967043 653 3688618755 654 3713439843 655 3728079363 656 3739811715 657 3753032643 658 3755728400 659 3757444803 660 3789879843 661 3801708963 662 3804669123 663 3809111523 664 3826907043 665 3834695683 666 3837339654 667 3838688756 668 3861131043 669 3903000675 670 3905666412 671 3906000003 672 3910501155 673 3925523715 674 3940575075 675 3958143838 676 3961684040 677 3962000847 678 4008662595 679 4019306403 680 4037585763 681 4041772895 682 4057435203 683 4068143523 684 4084999395 685 4102866430 686 4115735715 687 4126520643 688 4145041923 689 4150343204 690 4162056195 691 4188419523 692 4218384015 693 4247650275 694 4263306435 695 4267264056 696 4278991395 697 4282131843 698 4289988003 699 4297851363 700 4313599683 701 4340437923 702 4355239101 703 4395955203 704 4403915043 705 4435826403 706 4448623203 707 4469457315 708 4485516675 709 4496775363 710 4509659715 711 4525791075 712 4552284384 713 4553280483 714 4561381443 715 4563487316 716 4588978563 717 4593857283 718 4615028355 719 4617718750 720 4623184035 721 4639516995 722 4662431523 723 4676232754 724 4695264483 725 4724912643 726 4741234213 727 4761276003 728 4771217475 729 4814757755 730 4824413763 731 4827631935 732 4829416035 733 4847546645 734 4857811203 735 4875753209 736 4882934883 737 4904334719 738 4906728390 739 4916533923 740 4924951683 741 4929795935 742 4941808803 743 4970532003 744 4987466883 745 5006472969 746 5029930083 747 5038444323 748 5044962117 749 5074282755 750 5089680963 751 5091393315 752 5125700835 753 5158399683 754 5192188605 755 5194661475 756 5253640323 757 5272792995 758 5314701603 759 5319951843 760 5349752163 761 5358628510 762 5359504997 763 5390202723 764 5399016483 765 5400497304 766 5411367843 767 5418840755 768 5430805635 769 5442090191 770 5454490314 771 5487550083 772 5523165123 773 5532086883 774 5582181795 775 5627100195 776 5627979864 777 5637986409 778 5640876016 779 5645117955 780 5648307794 781 5652333123 782 5720727615 783 5732849550 784 5733821283 785 5744730435 786 5762935395 787 5824356427 788 5826879555 789 5861739843 790 5867253603 791 5879980224 792 5891176515 793 5939203775 794 5950271043 795 6028280163 796 6048568812 797 6076654847 798 6108672963 799 6114301635 800 6127445283 801 6221738883 802 6225525603 803 6293883555 804 6297692163 805 6320691260 806 6326293443 807 6345396963 808 6351133635 809 6357346723 810 6357633072 811 6368359203 812 6379855875 813 6412486083 814 6427870275 815 6435569283 816 6476064675 817 6505591211 818 6512812803 819 6514749795 820 6547722723 821 6563268195 822 6589765467 823 6590517123 824 6592407246 825 6644460250 826 6645184323 827 6664763043 828 6695325450 829 6700077315 830 6703853922 831 6727608483 832 6749279715 833 6767036643 834 6816483843 835 6886012323 836 6901954083 837 6910353834 838 6910940181 839 6925901283 840 6927898755 841 6961899843 842 6991969923 843 7006024803 844 7018083075 845 7048882709 846 7076510883 847 7108850595 848 7165488777 849 7169686275 850 7173751203 851 7190022435 852 7210387395 853 7272238224 854 7275748803 855 7281891555 856 7292143887 857 7302386115 858 7313963677 859 7321669727 860 7347575523 861 7384652355 862 7442866815 863 7457013315 864 7467379395 865 7501496649 866 7562246560 867 7600701123 868 7613260515 869 7627926243 870 7642606083 871 7644704355 872 7659400323 873 7665702915 874 7677412254 875 7681640485 876 7722434575 877 7735184127 878 7739424675 879 7764781923 880 7775359683 881 7785944643 882 7790180643 883 7834728195 884 7875142563 885 7902854403 886 7919932035 887 7973418435 888 8038161887 889 8062541592 890 8067346875 891 8070147555 892 8085246723 893 8095078278 894 8097300718 895 8121974883 896 8218667809 897 8261396095 898 8295930723 899 8303121979 900 8311581284 901 8350669923 902 8352863235 903 8373264812 904 8374812195 905 8446408729 906 8449593122 907 8456273763 908 8471729763 909 8473557300 910 8525681064 911 8532995469 912 8566983363 913 8589588159 914 8604788643 915 8615923683 916 8629295235 917 8638215363 918 8663797791 919 8667237603 920 8673941955 921 8741128035 922 8748009699 923 8768075043 924 8819839395 925 8842393155 926 8858197923 927 8887587075 928 8896639683 929 8919291363 930 8944241475 931 8982869283 932 8994246243 933 9023860035 934 9074086563 935 9085521123 936 9101541603 937 9135918723 938 9142801923 939 9161169795 940 9165764643 941 9234825603 942 9246360963 943 9248718652 944 9250977123 945 9311092035 946 9315618560 947 9315724323 948 9403956675 949 9424914723 950 9443563683 951 9506640003 952 9518343843 953 9545097625 954 9560537283 955 9567578595 956 9607528323 957 9651537791 958 9707310274 959 9715225314 960 9749192643 961 9773437907 962 9791894115 963 9809866274 964 9856121283 965 9889108991 966 9901323649 967 9915778083 968 9932514243 969 9975614883 970 9991003819 971 9991201010 972 10030823715 973 10047656643 974 10124786883 975 10159954816 976 10161177924 977 10171578499 978 10220631714 979 10233750243 980 10236178275 981 10241035203 982 10260474435 983 10270200963 984 10309153155 985 10329917296 986 10331096163 987 10338382175 988 10399512483 989 10404408003 990 10416651843 991 10428902883 992 10448519523 993 10465699203 994 10473066243 995 10479782537 996 10485350403 997 10492724355 998 10502560323 999 10576476963 1000 10583882883