0 1 1 1 2 1 3 1 4 1 5 2 6 1 7 3 8 2 9 4 10 1 11 5 12 1 13 6 14 1 15 1 16 10 17 9 18 2 19 12 20 2 21 2 22 2 23 19 24 3 25 24 26 3 27 30 28 4 29 36 30 1 31 43 32 48 33 4 34 6 35 4 36 8 37 73 38 8 39 7 40 9 41 103 42 1 43 121 44 12 45 11 46 15 47 162 48 17 49 187 50 20 51 17 52 21 53 247 54 28 55 22 56 30 57 27 58 32 59 371 60 1 61 423 62 43 63 41 64 512 65 47 66 1 67 614 68 66 69 65 70 1 71 781 72 90 73 879 74 98 75 99 76 109 77 109 78 1 79 1236 80 142 81 1381 82 161 83 1541 84 1 85 185 86 208 87 213 88 232 89 2116 90 2 91 270 92 298 93 312 94 335 95 350 96 384 97 3180 98 426 99 447 100 481 101 3868 102 2 103 4260 104 607 105 1 106 678 107 5149 108 767 109 5653 110 1 111 902 112 952 113 6796 114 2 115 1120 116 1191 117 1259 118 1332 119 1405 120 3 121 9715 122 1659 123 1753 124 1843 125 11558 126 3 127 12592 128 13143 129 2423 130 2 131 14913 132 4 133 2981 134 3144 135 3317 136 3481 137 19123 138 3 139 20747 140 2 141 4526 142 4740 143 5009 144 5266 145 5538 146 5821 147 6140 148 6427 149 30879 150 5 151 33375 152 7858 153 8280 154 2 155 9138 156 6 157 42004 158 10564 159 11116 160 11630 161 12248 162 12832 163 52604 164 14124 165 2 166 15536 167 60962 168 7 169 65582 170 3 171 19757 172 20663 173 75783 174 7 175 23832 176 24934 177 26177 178 27359 179 93805 180 10 181 100636 182 3 183 34539 184 36081 185 37832 186 9 187 41434 188 43304 189 45381 190 5 191 142079 192 51877 193 152047 194 56746 195 4 196 62026 197 173909 198 12 199 185884 200 74077 201 77511 202 80892 203 84614 204 12 205 92338 206 96386 207 100765 208 105132 209 109889 210 1 211 275116 212 124987 213 130571 214 136169 215 142236 216 148362 217 154893 218 161546 219 168657 220 10 221 183536 222 18 223 402233 224 208151 225 217175 226 226338 227 455369 228 19 229 484301 230 8 231 5 232 290494 233 547281 234 21 235 328850 236 342548 237 357006 238 11 239 656003 240 27 241 696467 242 437593 243 739208 244 474492 245 494184 246 27 247 535609 248 557489 249 580404 250 603974 251 935575 252 30 253 680855 254 708387 255 9 256 1081693 257 1113336 258 33 259 863301 260 15 261 933927 262 971151 263 1321867 264 36 265 1091955 266 14 267 1180349 268 1226935 269 1566085 270 45 271 1656341 272 1432043 273 12 274 1546482 275 1607020 276 43 277 1956899 278 1802253 279 1872281 280 29 281 2184550 282 51 283 2307352 284 2263115 285 17 286 29 287 2533946 288 2630942 289 2715324 290 27 291 2943691 292 3055619 293 3023464 294 60 295 3416458 296 3545661 297 3679399 298 3818020 299 3961627 300 73 301 4264520 302 4424332 303 4589650 304 4761004 305 4938414 306 73 307 4376729 308 32 309 5713776 310 50 311 4856175 312 83 313 5113851 314 6848265 315 29 316 7359969 317 5667736 318 85 319 8196837 320 8495874 321 8804903 322 57 323 9456077 324 9799020 325 10153352 326 10520552 327 10899932 328 11292913 329 11699064 330 1 331 8077914 332 13004429 333 13469446 334 13950978 335 14448540 336 121 337 9378643 338 16046736 339 16615814 340 82 341 17813419 342 133 343 10872689 344 19767069 345 50 346 21181943 347 11989128 348 140 349 12586704 350 80 351 25157815 352 26035335 353 13866134 354 156 355 28846410 356 29847387 357 54 358 31949336 359 16014904 360 183 361 16797794 362 36588772 363 37845681 364 114 365 40486461 366 191 367 19366415 368 44783387 369 46310100 370 139 371 49516392 372 211 373 22299036 374 108 375 56582206 376 58495393 377 60469717 378 231 379 25643268 380 133 381 69030905 382 71347645 383 28127695 384 76206750 385 52 386 81383792 387 84097097 388 86898729 389 32280414 390 1 391 95851198 392 99029126 393 102307049 394 105690673 395 109180810 396 304 397 38715243 398 120333384 399 112 400 128369521 401 42366253 402 335 403 141400913 404 146022514 405 150788072 406 236 407 160774636 408 360 409 50657849 410 222 411 182695812 412 188611615 413 194710792 414 392 415 207486113 416 214174064 417 221068327 418 282 419 63167756 420 1 421 65995133 422 258883009 423 267160458 424 275694213 425 284489692 426 479 427 302901132 428 312533715 429 189 430 363 431 82005243 432 354102706 433 85617204 434 310 435 223 436 400984754 437 413609979 438 570 439 97370766 440 367 441 468060441 442 426 443 106032014 444 617 445 529402223 446 545911247 447 562916041 448 580432582 449 120393089 450 704 451 636197959 452 655911523 453 676213837 454 697123109 455 143 456 742 457 142402134 458 787181830 459 811395461 460 582 461 154776981 462 1 463 161337482 464 943670518 465 364 466 1002219091 467 175252111 468 886 469 1096674673 470 586 471 1164365814 472 1199708557 473 1236087884 474 952 475 1312072144 476 630 477 1392563672 478 1434579072 479 224092082 480 1088 481 1568113160 482 1615237670 483 455 484 1713629953 485 1764976097 486 1817807628 487 263495546 488 1928098773 489 1985644848 490 935 491 285564600 492 1263 493 2232893236 494 827 495 584 496 2437614896 497 2509806651 498 1359 499 335036669 500 2739007641 501 2819814962 502 2902924910 503 362704607 504 1489 505 3166731016 506 1014 507 3355335717 508 3453668901 509 408280148 510 1 511 3765701151 512 433045702 513 3988700987 514 4104940746 515 4224459999 516 1768 517 4473683713 518 1212 519 4737115697 520 1467 521 516132435 522 1933 523 536537723 524 5463094090 525 940 526 5782697319 527 5949218044 528 2095 529 602425092 530 1499 531 6662954176 532 1720 533 7050251745 534 2276 535 7459314943 536 7672374000 537 7891326977 538 8116322761 539 8347532310 540 2524 541 757808981 542 9080085716 543 9337832979 544 9602657748 545 9874758386 546 1 547 849033078 548 10736630656 549 11039796307 550 2287 551 11671205296 552 2951 553 12337548472 554 12684398704 555 1477 556 13406679685 557 1024545785 558 3183 559 14565373738 560 2372 561 1560 562 15820872231 563 1145783343 564 3462 565 17181007538 566 17659072476 567 18150028175 568 18654199370 569 1280516679 570 1 571 1328666739 572 2775 573 21385781591 574 3166 575 22583729666 576 23206851257 577 1483615429 578 24503507812 579 25177916339 580 3528 581 26581149640 582 4462 583 28060102215 584 28829199338 585 2315 586 30429212489 587 1780525402 588 4828 589 32991855680 590 3688 591 34815304144 592 35763316161 593 1984826750 594 5248 595 1880 596 39812080043 597 40891771408 598 4482 599 2211213711 600 5762 601 2291967553 602 4332 603 47991957398 604 49286176569 605 50614243558 606 6200 607 2551338978 608 54810162998 609 3197 610 5399 611 59342839789 612 6716 613 2838385569 614 64238429193 615 3591 616 5819 617 3046488167 618 7276 619 3155889317 620 5690 621 77234862547 622 79288354059 623 81394813033 624 7868 625 3506899780 626 88045357861 627 4196 628 92769026989 629 95222231889 630 2 631 3894750706 632 102965774258 633 105680287187 634 108464231664 635 111319341389 636 9294 637 117250136987 638 7235 639 123487310743 640 126725554184 641 4633102814 642 10062 643 4795912838 644 7873 645 5524 646 8863 647 5137974461 648 155775424418 649 159832846649 650 8714 651 5942 652 172630708724 653 5694816875 654 11766 655 186421757947 656 191252240385 657 196204233611 658 10442 659 6308680263 660 1 661 6526913502 662 222893181923 663 6996 664 234528757023 665 4868 666 13845 667 253096103672 668 259596847964 669 266259727199 670 12435 671 280087691679 672 15011 673 7994723732 674 302146871635 675 309868333782 676 317781435684 677 8550140878 678 16204 679 342717307255 680 13216 681 360387035271 682 14542 683 9452526684 684 17502 685 398422130058 686 408524367033 687 418875424246 688 429481263244 689 440347969014 690 1 691 10797319504 692 474576376534 693 10763 694 498817869533 695 511385881583 696 20547 697 537452210863 698 550965334357 699 564808576290 700 18716 701 12735111686 702 22241 703 623642278246 704 639257379546 705 12876 706 671636373187 707 688418440397 708 23985 709 14519165685 710 19955 711 759719137077 712 778637181129 713 798013070351 714 1 715 11726 716 858996818538 717 880314314408 718 902146043152 719 17084905173 720 28254 721 970848497133 722 994860469317 723 1019449747552 724 1044629850274 725 1070414554351 726 30323 727 19442618635 728 25260 729 20078732688 730 27946 731 1238632866850 732 32799 733 21410913420 734 1332122313707 735 19554 736 1398225695749 737 1432463478369 738 35346 739 23568092203 740 29888 741 21035 742 32571 743 25119573387 744 38171 745 1737353490249 746 1779644544186 747 1822936765804 748 35218 749 1912617507590 750 41488 751 28519315988 752 2055240826333 753 2105042710939 754 38038 755 2208194776395 756 44602 757 31352287437 758 2372206299321 759 26798 760 41484 761 33387828548 762 48142 763 2672264308193 764 2736561361822 765 29416 766 2869704845388 767 2938620582986 768 3009146498250 769 37843069969 770 1 771 3230755226401 772 3308095969470 773 40277905696 774 55952 775 3551090977418 776 3635886047692 777 34344 778 3811431380417 779 3902271716070 780 2 781 4090320426963 782 51875 783 4287182069660 784 4389042593414 785 4493258333434 786 65228 787 50030756445 788 4820572861832 789 4934751285491 790 61290 791 5171063496119 792 70318 793 5418383002196 794 5546325512407 795 44008 796 5811097927123 797 58335072307 798 1 799 6231483520766 800 6378085174600 801 6528044156765 802 6681435365880 803 6838335223701 804 81643 805 42352 806 71009 807 7502609669895 808 7678259293230 809 70040094372 810 88399 811 72196932579 812 76794 813 8618367091915 814 82947 815 9025018981317 816 95001 817 9450342053036 818 9670264597434 819 60066 820 89985 821 83966925401 822 102329 823 86531154487 824 11098384267873 825 65552 826 96807 827 91885691799 828 110175 829 94680204112 830 97178 831 13025242639997 832 13325851210721 833 13633216680372 834 118582 835 14268813258033 836 104562 837 14933254006838 838 15276687038934 839 109914253914 840 3 841 113229905271 842 16729046682638 843 17112659853127 844 17504841866065 845 17905779127851 846 137785 847 18734685121098 848 19163046842746 849 19600949958861 850 131540 851 20506213007505 852 148243 853 135221638388 854 131385 855 97005 856 22951386122397 857 143418924449 858 1 859 147693576568 860 142396 861 104496 862 26262418638783 863 156610987948 864 27466254214767 865 28088180393890 866 28723828840926 867 29373494553089 868 164267 869 30716088994821 870 2 871 32118449876159 872 32842848284414 873 33583168457140 874 176966 875 35112945425762 876 198938 877 192052118799 878 37535784631334 879 38379051596825 880 191353 881 203510667542 882 214074 883 209482276208 884 191840 885 143007 886 44821552804638 887 221931993514 888 230130 889 47895021956456 890 207490 891 50057194241937 892 51173690045051 893 52314460989856 894 247322 895 54670896953728 896 55887623084131 897 166214 898 58400827061123 899 59698433075689 900 266856 901 62378561294589 902 240435 903 179367 904 66620132316717 905 68095535139680 906 286287 907 295560094963 908 72715583204404 909 74322494131462 910 1 911 312857473803 912 307735 913 81103722105345 914 82891175265961 915 209764 916 86582124214819 917 88487246334452 918 330548 919 350402299851 920 301054 921 96525145620116 922 98643381956320 923 100806949736802 924 2 925 105273883082161 926 107579198930157 927 109933747555670 928 112338554337598 929 403419764819 930 3 931 119865092790128 932 122481609195939 933 125153831664601 934 127882916889139 935 228639 936 410307 937 451278892088 938 374652 939 142423436741650 940 399746 941 477201618840 942 440807 943 155206342685908 944 158573066772376 945 306410 946 429092 947 518775586693 948 473220 949 176505137008621 950 434771 951 184219293609439 952 461420 953 563805158226 954 508131 955 200647470246393 956 204972930236590 957 355091 958 213898635829646 959 218502652244809 960 546729 961 629696489579 962 502182 963 237905586531557 964 243013242969261 965 248227894433878 966 2 967 683890697434 968 264535906854247 969 412071 970 574074 971 722472547172 972 287915620068169 973 294068733639735 974 300350168064406 975 445446 976 313308497239371 977 784279340016 978 674903 979 333775390193146 980 625329 981 348139217111484 982 355545715524456 983 851134451075 984 724266 985 378700402244373 986 671175 987 515671 988 710516 989 411875855136504 990 4 991 948812120531 992 438603505379813 993 447883508734799 994 763117 995 467022318751548 996 834296 997 1029028458599 998 497236637668556 999 507726010373039 1000 518431378141104