1 1 2 2 3 4 4 8 5 16 6 31 7 57 8 99 9 163 10 256 11 386 12 562 13 794 14 1093 15 1471 16 1941 17 2517 18 3214 19 4048 20 5036 21 6196 22 7547 23 9109 24 10903 25 12951 26 15276 27 17902 28 20854 29 24158 30 27841 31 31931 32 36457 33 41449 34 46938 35 52956 36 59536 37 66712 38 74519 39 82993 40 92171 41 102091 42 112792 43 124314 44 136698 45 149986 46 164221 47 179447 48 195709 49 213053 50 231526 51 251176 52 272052 53 294204 54 317683 55 342541 56 368831 57 396607 58 425924 59 456838 60 489406 61 523686 62 559737 63 597619 64 637393 65 679121 66 722866 67 768692 68 816664 69 866848 70 919311 71 974121 72 1031347 73 1091059 74 1153328 75 1218226 76 1285826 77 1356202 78 1429429 79 1505583 80 1584741 81 1666981 82 1752382 83 1841024 84 1932988 85 2028356 86 2127211 87 2229637 88 2335719 89 2445543 90 2559196 91 2676766 92 2798342 93 2924014 94 3053873 95 3188011 96 3326521 97 3469497 98 3617034 99 3769228 100 3926176 101 4087976 102 4254727 103 4426529 104 4603483 105 4785691 106 4973256 107 5166282 108 5364874 109 5569138 110 5779181 111 5995111 112 6217037 113 6445069 114 6679318 115 6919896 116 7166916 117 7420492 118 7680739 119 7947773 120 8221711 121 8502671 122 8790772 123 9086134 124 9388878 125 9699126 126 10017001 127 10342627 128 10676129 129 11017633 130 11367266 131 11725156 132 12091432 133 12466224 134 12849663 135 13241881 136 13643011 137 14053187 138 14472544 139 14901218 140 15339346 141 15787066 142 16244517 143 16711839 144 17189173 145 17676661 146 18174446 147 18682672 148 19201484 149 19731028 150 20271451 151 20822901 152 21385527 153 21959479 154 22544908 155 23141966 156 23750806 157 24371582 158 25004449 159 25649563 160 26307081 161 26977161 162 27659962 163 28355644 164 29064368 165 29786296 166 30521591 167 31270417 168 32032939 169 32809323 170 33599736 171 34404346 172 35223322 173 36056834 174 36905053 175 37768151 176 38646301 177 39539677 178 40448454 179 41372808 180 42312916 181 43268956 182 44241107 183 45229549 184 46234463 185 47256031 186 48294436 187 49349862 188 50422494 189 51512518 190 52620121 191 53745491 192 54888817 193 56050289 194 57230098 195 58428436 196 59645496 197 60881472 198 62136559 199 63410953 200 64704851 201 66018451 202 67351952 203 68705554 204 70079458 205 71473866 206 72888981 207 74325007 208 75782149 209 77260613 210 78760606 211 80282336 212 81826012 213 83391844 214 84980043 215 86590821 216 88224391 217 89880967 218 91560764 219 93263998 220 94990886 221 96741646 222 98516497 223 100315659 224 102139353 225 103987801 226 105861226 227 107759852 228 109683904 229 111633608 230 113609191 231 115610881 232 117638907 233 119693499 234 121774888 235 123883306 236 126018986 237 128182162 238 130373069 239 132591943 240 134839021 241 137114541 242 139418742 243 141751864 244 144114148 245 146505836 246 148927171 247 151378397 248 153859759 249 156371503 250 158913876 251 161487126 252 164091502 253 166727254 254 169394633 255 172093891 256 174825281 257 177589057 258 180385474 259 183214788 260 186077256 261 188973136 262 191902687 263 194866169 264 197863843 265 200895971 266 203962816 267 207064642 268 210201714 269 213374298 270 216582661 271 219827071 272 223107797 273 226425109 274 229779278 275 233170576 276 236599276 277 240065652 278 243569979 279 247112533 280 250693591 281 254313431 282 257972332 283 261670574 284 265408438 285 269186206 286 273004161 287 276862587 288 280761769 289 284701993 290 288683546 291 292706716 292 296771792 293 300879064 294 305028823 295 309221361 296 313456971 297 317735947 298 322058584 299 326425178 300 330836026 301 335291426 302 339791677 303 344337079 304 348927933 305 353564541 306 358247206 307 362976232 308 367751924 309 372574588 310 377444531 311 382362061 312 387327487 313 392341119 314 397403268 315 402514246 316 407674366 317 412883942 318 418143289 319 423452723 320 428812561 321 434223121 322 439684722 323 445197684 324 450762328 325 456378976 326 462047951 327 467769577 328 473544179 329 479372083 330 485253616 331 491189106 332 497178882 333 503223274 334 509322613 335 515477231 336 521687461 337 527953637 338 534276094 339 540655168 340 547091196 341 553584516 342 560135467 343 566744389 344 573411623 345 580137511 346 586922396 347 593766622 348 600670534 349 607634478 350 614658801 351 621743851 352 628889977 353 636097529 354 643366858 355 650698316 356 658092256 357 665549032 358 673068999 359 680652513 360 688299931 361 696011611 362 703787912 363 711629194 364 719535818 365 727508146 366 735546541 367 743651367 368 751822989 369 760061773 370 768368086 371 776742296 372 785184772 373 793695884 374 802276003 375 810925501 376 819644751 377 828434127 378 837294004 379 846224758 380 855226766 381 864300406 382 873446057 383 882664099 384 891954913 385 901318881 386 910756386 387 920267812 388 929853544 389 939513968 390 949249471 391 959060441 392 968947267 393 978910339 394 988950048 395 999066786 396 1009260946 397 1019532922 398 1029883109 399 1040311903 400 1050819701 401 1061406901 402 1072073902 403 1082821104 404 1093648908 405 1104557716 406 1115547931 407 1126619957 408 1137774199 409 1149011063 410 1160330956 411 1171734286 412 1183221462 413 1194792894 414 1206448993 415 1218190171 416 1230016841 417 1241929417 418 1253928314 419 1266013948 420 1278186736 421 1290447096 422 1302795447 423 1315232209 424 1327757803 425 1340372651 426 1353077176 427 1365871802 428 1378756954 429 1391733058 430 1404800541 431 1417959831 432 1431211357 433 1444555549 434 1457992838 435 1471523656 436 1485148436 437 1498867612 438 1512681619 439 1526590893 440 1540595871 441 1554696991 442 1568894692 443 1583189414 444 1597581598 445 1612071686 446 1626660121 447 1641347347 448 1656133809 449 1671019953 450 1686006226 451 1701093076 452 1716280952 453 1731570304 454 1746961583 455 1762455241 456 1778051731 457 1793751507 458 1809555024 459 1825462738 460 1841475106 461 1857592586 462 1873815637 463 1890144719 464 1906580293 465 1923122821 466 1939772766 467 1956530592 468 1973396764 469 1990371748 470 2007456011 471 2024650021 472 2041954247 473 2059369159 474 2076895228 475 2094532926 476 2112282726 477 2130145102 478 2148120529 479 2166209483 480 2184412441 481 2202729881 482 2221162282 483 2239710124 484 2258373888 485 2277154056 486 2296051111 487 2315065537 488 2334197819 489 2353448443 490 2372817896 491 2392306666 492 2411915242 493 2431644114 494 2451493773 495 2471464711 496 2491557421 497 2511772397 498 2532110134 499 2552571128 500 2573155876 501 2593864876 502 2614698627 503 2635657629 504 2656742383 505 2677953391 506 2699291156 507 2720756182 508 2742348974 509 2764070038 510 2785919881 511 2807899011 512 2830007937 513 2852247169 514 2874617218 515 2897118596 516 2919751816 517 2942517392 518 2965415839 519 2988447673 520 3011613411 521 3034913571 522 3058348672 523 3081919234 524 3105625778 525 3129468826 526 3153448901 527 3177566527 528 3201822229 529 3226216533 530 3250749966 531 3275423056 532 3300236332 533 3325190324 534 3350285563 535 3375522581 536 3400901911 537 3426424087 538 3452089644 539 3477899118 540 3503853046 541 3529951966 542 3556196417 543 3582586939 544 3609124073 545 3635808361 546 3662640346 547 3689620572 548 3716749584 549 3744027928 550 3771456151 551 3799034801 552 3826764427 553 3854645579 554 3882678808 555 3910864666 556 3939203706 557 3967696482 558 3996343549 559 4025145463 560 4054102781 561 4083216061 562 4112485862 563 4141912744 564 4171497268 565 4201239996 566 4231141491 567 4261202317 568 4291423039 569 4321804223 570 4352346436 571 4383050246 572 4413916222 573 4444944934 574 4476136953 575 4507492851 576 4539013201 577 4570698577 578 4602549554 579 4634566708 580 4666750616 581 4699101856 582 4731621007 583 4764308649 584 4797165363 585 4830191731 586 4863388336 587 4896755762 588 4930294594 589 4964005418 590 4997888821 591 5031945391 592 5066175717 593 5100580389 594 5135159998 595 5169915136 596 5204846396 597 5239954372 598 5275239659 599 5310702853 600 5346344551 601 5382165351 602 5418165852 603 5454346654 604 5490708358 605 5527251566 606 5563976881 607 5600884907 608 5637976249 609 5675251513 610 5712711306 611 5750356236 612 5788186912 613 5826203944 614 5864407943 615 5902799521 616 5941379291 617 5980147867 618 6019105864 619 6058253898 620 6097592586 621 6137122546 622 6176844397 623 6216758759 624 6256866253 625 6297167501 626 6337663126 627 6378353752 628 6419240004 629 6460322508 630 6501601891 631 6543078781 632 6584753807 633 6626627599 634 6668700788 635 6710974006 636 6753447886 637 6796123062 638 6839000169 639 6882079843 640 6925362721 641 6968849441 642 7012540642 643 7056436964 644 7100539048 645 7144847536 646 7189363071 647 7234086297 648 7279017859 649 7324158403 650 7369508576 651 7415069026 652 7460840402 653 7506823354 654 7553018533 655 7599426591 656 7646048181 657 7692883957 658 7739934574 659 7787200688 660 7834682956 661 7882382036 662 7930298587 663 7978433269 664 8026786743 665 8075359671 666 8124152716 667 8173166542 668 8222401814 669 8271859198 670 8321539361 671 8371442971 672 8421570697 673 8471923209 674 8522501178 675 8573305276 676 8624336176 677 8675594552 678 8727081079 679 8778796433 680 8830741291 681 8882916331 682 8935322232 683 8987959674 684 9040829338 685 9093931906 686 9147268061 687 9200838487 688 9254643869 689 9308684893 690 9362962246 691 9417476616 692 9472228692 693 9527219164 694 9582448723 695 9637918061 696 9693627871 697 9749578847 698 9805771684 699 9862207078 700 9918885726 701 9975808326 702 10032975577 703 10090388179 704 10148046833 705 10205952241 706 10264105106 707 10322506132 708 10381156024 709 10440055488 710 10499205231 711 10558605961 712 10618258387 713 10678163219 714 10738321168 715 10798732946 716 10859399266 717 10920320842 718 10981498389 719 11042932623 720 11104624261 721 11166574021 722 11228782622 723 11291250784 724 11353979228 725 11416968676 726 11480219851 727 11543733477 728 11607510279 729 11671550983 730 11735856316 731 11800427006 732 11865263782 733 11930367374 734 11995738513 735 12061377931 736 12127286361 737 12193464537 738 12259913194 739 12326633068 740 12393624896 741 12460889416 742 12528427367 743 12596239489 744 12664326523 745 12732689211 746 12801328296 747 12870244522 748 12939438634 749 13008911378 750 13078663501 751 13148695751 752 13219008877 753 13289603629 754 13360480758 755 13431641016 756 13503085156 757 13574813932 758 13646828099 759 13719128413 760 13791715631 761 13864590511 762 13937753812 763 14011206294 764 14084948718 765 14158981846 766 14233306441 767 14307923267 768 14382833089 769 14458036673 770 14533534786 771 14609328196 772 14685417672 773 14761803984 774 14838487903 775 14915470201 776 14992751651 777 15070333027 778 15148215104 779 15226398658 780 15304884466 781 15383673306 782 15462765957 783 15542163199 784 15621865813 785 15701874581 786 15782190286 787 15862813712 788 15943745644 789 16024986868 790 16106538171 791 16188400341 792 16270574167 793 16353060439 794 16435859948 795 16518973486 796 16602401846 797 16686145822 798 16770206209 799 16854583803 800 16939279401 801 17024293801 802 17109627802 803 17195282204 804 17281257808 805 17367555416 806 17454175831 807 17541119857 808 17628388299 809 17715981963 810 17803901656 811 17892148186 812 17980722362 813 18069624994 814 18158856893 815 18248418871 816 18338311741 817 18428536317 818 18519093414 819 18609983848 820 18701208436 821 18792767996 822 18884663347 823 18976895309 824 19069464703 825 19162372351 826 19255619076 827 19349205702 828 19443133054 829 19537401958 830 19632013241 831 19726967731 832 19822266257 833 19917909649 834 20013898738 835 20110234356 836 20206917336 837 20303948512 838 20401328719 839 20499058793 840 20597139571 841 20695571891 842 20794356592 843 20893494514 844 20992986498 845 21092833386 846 21193036021 847 21293595247 848 21394511909 849 21495786853 850 21597420926 851 21699414976 852 21801769852 853 21904486404 854 22007565483 855 22111007941 856 22214814631 857 22318986407 858 22423524124 859 22528428638 860 22633700806 861 22739341486 862 22845351537 863 22951731819 864 23058483193 865 23165606521 866 23273102666 867 23380972492 868 23489216864 869 23597836648 870 23706832711 871 23816205921 872 23925957147 873 24036087259 874 24146597128 875 24257487626 876 24368759626 877 24480414002 878 24592451629 879 24704873383 880 24817680141 881 24930872781 882 25044452182 883 25158419224 884 25272774788 885 25387519756 886 25502655011 887 25618181437 888 25734099919 889 25850411343 890 25967116596 891 26084216566 892 26201712142 893 26319604214 894 26437893673 895 26556581411 896 26675668321 897 26795155297 898 26915043234 899 27035333028 900 27156025576 901 27277121776 902 27398622527 903 27520528729 904 27642841283 905 27765561091 906 27888689056 907 28012226082 908 28136173074 909 28260530938 910 28385300581 911 28510482911 912 28636078837 913 28762089269 914 28888515118 915 29015357296 916 29142616716 917 29270294292 918 29398390939 919 29526907573 920 29655845111 921 29785204471 922 29914986572 923 30045192334 924 30175822678 925 30306878526 926 30438360801 927 30570270427 928 30702608329 929 30835375433 930 30968572666 931 31102200956 932 31236261232 933 31370754424 934 31505681463 935 31641043281 936 31776840811 937 31913074987 938 32049746744 939 32186857018 940 32324406746 941 32462396866 942 32600828317 943 32739702039 944 32879018973 945 33018780061 946 33158986246 947 33299638472 948 33440737684 949 33582284828 950 33724280851 951 33866726701 952 34009623327 953 34152971679 954 34296772708 955 34441027366 956 34585736606 957 34730901382 958 34876522649 959 35022601363 960 35169138481 961 35316134961 962 35463591762 963 35611509844 964 35759890168 965 35908733696 966 36058041391 967 36207814217 968 36358053139 969 36508759123 970 36659933136 971 36811576146 972 36963689122 973 37116273034 974 37269328853 975 37422857551 976 37576860101 977 37731337477 978 37886290654 979 38041720608 980 38197628316 981 38354014756 982 38510880907 983 38668227749 984 38826056263 985 38984367431 986 39143162236 987 39302441662 988 39462206694 989 39622458318 990 39783197521 991 39944425291 992 40106142617 993 40268350489 994 40431049898 995 40594241836 996 40757927296 997 40922107272 998 41086782759 999 41251954753 1000 41417624251