1 1 2 2 3 4 4 8 5 16 6 30 7 57 8 88 9 163 10 230 11 386 12 456 13 794 14 966 15 1471 16 1712 17 2517 18 2484 19 4048 20 4520 21 6196 22 6842 23 9109 24 9048 25 12951 26 14014 27 17902 28 19208 29 24158 30 21510 31 31931 32 33888 33 41449 34 43826 35 52956 36 52992 37 66712 38 70034 39 82993 40 86840 41 102091 42 97776 43 124314 44 129448 45 149986 46 155894 47 179447 48 179280 49 213053 50 220650 51 251176 52 259688 53 294204 54 294030 55 342541 56 353192 57 396607 58 408494 59 456838 60 443520 61 523686 62 538222 63 597619 64 613568 65 679121 66 679140 67 768692 68 787848 69 866848 70 887810 71 974121 72 981288 73 1091059 74 1115846 75 1218226 76 1245032 77 1356202 78 1360398 79 1505583 80 1536880 81 1666981 82 1700762 83 1841024 84 1839600 85 2028356 86 2067354 87 2229637 88 2271368 89 2445543 90 2452140 91 2676766 92 2724488 93 2924014 94 2975006 95 3188011 96 3208224 97 3469497 98 3527314 99 3769228 100 3830600 101 4087976 102 4109886 103 4426529 104 4495608 105 4785691 106 4858934 107 5166282 108 5201064 109 5569138 110 5651030 111 5995111 112 6081488 113 6445069 114 6481812 115 6919896 116 7015912 117 7420492 118 7521674 119 7947773 120 7962360 121 8502671 122 8614542 123 9086134 124 9203528 125 9699126 126 9753282 127 10342627 128 10471808 129 11017633 130 11153090 131 11725156 132 11796576 133 12466224 134 12614626 135 13241881 136 13396952 137 14053187 138 14134788 139 14901218 140 15070440 141 15787066 142 15963782 143 16711839 144 16819056 145 17676661 146 17868794 147 18682672 148 18882728 149 19731028 150 19838550 151 20822901 152 21039688 153 21959479 154 22185086 155 23141966 156 23276760 157 24371582 158 24615294 159 25649563 160 25902560 161 26977161 162 27133380 163 28355644 164 28628168 165 29786296 166 30069074 167 31270417 168 31428936 169 32809323 170 33113110 171 34404346 172 34718888 173 36056834 174 36253422 175 37768151 176 38105232 177 39539677 178 39888554 179 41372808 180 41555880 181 43268956 182 43641962 183 45229549 184 45614888 185 47256031 186 47506260 187 49349862 188 49760968 189 51512518 190 51937070 191 53745491 192 54033984 193 56050289 194 56502306 195 58428436 196 58894472 197 60881472 198 61200414 199 63410953 200 63906200 201 66018451 202 66528902 203 68705554 204 69057672 205 71473866 206 72015334 207 74325007 208 74882288 209 77260613 210 77616840 211 80282336 212 80872488 213 83391844 214 83999066 215 86590821 216 87030936 217 89880967 218 90522974 219 93263998 220 93923720 221 96741646 222 97207806 223 100315659 224 101012128 225 103987801 226 104703314 227 107759852 228 108276288 229 111633608 230 112387890 231 115610881 232 116384888 233 119693499 234 120259620 235 123883306 236 124698152 237 128182162 238 129018134 239 132591943 240 133138320 241 137114541 242 137993482 243 141751864 244 142652648 245 146505836 246 147168270 247 151378397 248 152324328 249 156371503 250 157340750 251 161487126 252 162187704 253 166727254 254 167743886 255 172093891 256 173134592 257 177589057 258 178367268 259 183214788 260 184305160 261 188973136 262 190089122 263 194866169 264 195718248 265 200895971 266 202063974 267 207064642 268 208259048 269 213374298 270 214266870 271 219827071 272 221075888 273 226425109 274 227701946 275 233170576 276 234152880 277 240065652 278 241399354 279 247112533 280 248475080 281 254313431 282 255361716 283 261670574 284 263092488 285 269186206 286 270638654 287 276862587 288 278008416 289 284701993 290 286216370 291 292706716 292 294252488 293 300879064 294 302068242 295 309221361 296 310831672 297 317735947 298 319379414 299 326425178 300 327651600 301 335291426 302 337002102 303 344337079 304 346081808 305 353564541 306 354948372 307 362976232 308 364790888 309 372574588 310 374425130 311 382362061 312 383840184 313 392341119 314 394264366 315 402514246 316 404474312 317 412883942 318 414443358 319 423452723 320 425488320 321 434223121 322 436297442 323 445197684 324 446873760 325 456378976 326 458531714 327 467769577 328 469962008 329 479372083 330 481120860 331 491189106 332 493462888 333 503223274 334 505538726 335 515477231 336 517316016 337 527953637 338 530353434 339 540655168 340 543097640 341 553584516 342 555573870 343 566744389 344 569274248 345 580137511 346 582712094 347 593766622 348 595868568 349 607634478 350 610299550 351 621743851 352 624454688 353 636097529 354 638310852 355 650698316 356 653502792 357 665549032 358 668401394 359 680652513 360 682890120 361 696011611 362 698960822 363 711629194 364 714627368 365 727508146 366 729974190 367 743651367 368 746749648 369 760061773 370 763211210 371 776742296 372 779350416 373 793695884 374 796948746 375 810925501 376 814230632 377 828434127 378 831164544 379 846224758 380 849636680 381 864300406 382 867766862 383 882664099 384 885560448 385 901318881 386 904895554 387 920267812 388 923900168 389 939513968 390 942527430 391 959060441 392 962806488 393 978910339 394 982714406 395 999066786 396 1002268872 397 1019532922 398 1023454214 399 1040311903 400 1044292400 401 1061406901 402 1064744436 403 1082821104 404 1086922408 405 1104557716 406 1108720634 407 1126619957 408 1130137560 409 1149011063 410 1153298430 411 1171734286 412 1176084488 413 1194792894 414 1198474110 415 1218190171 416 1222668512 417 1241929417 418 1246473074 419 1266013948 420 1269696120 421 1290447096 422 1295122642 423 1315232209 424 1319974328 425 1340372651 426 1344392100 427 1365871802 428 1370749608 429 1391733058 430 1396679990 431 1417959831 432 1422195408 433 1444555549 434 1449642026 435 1471523656 436 1476680552 437 1498867612 438 1503260238 439 1526590893 440 1531891240 441 1554696991 442 1560070382 443 1583189414 444 1587787512 445 1612071686 446 1617592494 447 1641347347 448 1646942528 449 1671019953 450 1675784700 451 1701093076 452 1706839688 453 1731570304 454 1737393986 455 1762455241 456 1767469224 457 1793751507 458 1799730694 459 1825462738 460 1831520360 461 1857592586 462 1862776146 463 1890144719 464 1896361968 465 1923122821 466 1929421274 467 1956530592 468 1961981424 469 1990371748 470 1996834010 471 2024650021 472 2031194888 473 2059369159 474 2065017972 475 2094532926 476 2101245832 477 2130145102 478 2136943454 479 2166209483 480 2171963040 481 2202729881 482 2209700562 483 2239710124 484 2246767688 485 2277154056 486 2283284862 487 2315065537 488 2322299768 489 2353448443 490 2360772470 491 2392306666 492 2398676136 493 2431644114 494 2439149206 495 2471464711 496 2479061072 497 2511772397 498 2518379028 499 2552571128 500 2560353000 501 2593864876 502 2601741002 503 2635657629 504 2642492664 505 2677953391 506 2686019534 507 2720756182 508 2728918088 509 2764070038 510 2771175270 511 2807899011 512 2816255488 513 2852247169 514 2860702466 515 2897118596 516 2904522720 517 2942517392 518 2951171874 519 2988447673 520 2997202520 521 3034913571 522 3042597060 523 3081919234 524 3090877928 525 3129468826 526 3138531014 527 3177566527 528 3185537520 529 3226216533 530 3235487290 531 3275423056 532 3284798888 533 3325190324 534 3333427182 535 3375522581 536 3385111752 537 3426424087 538 3436121534 539 3477899118 540 3486313440 541 3529951966 542 3539867582 543 3582586939 544 3592612448 545 3635808361 546 3644615520 547 3689620572 548 3699869128 549 3744027928 550 3754389650 551 3799034801 552 3808202184 553 3854645579 554 3865235286 555 3910864666 556 3921569192 557 3967696482 558 3977174574 559 4025145463 560 4036082960 561 4083216061 562 4094271722 563 4141912744 564 4151710032 565 4201239996 566 4212533674 567 4261202317 568 4272615848 569 4321804223 570 4331898540 571 4383050246 572 4394706888 573 4444944934 574 4456724846 575 4507492851 576 4517989056 577 4570698577 578 4582726754 579 4634566708 580 4646719880 581 4699101856 582 4709900766 583 4764308649 584 4776715288 585 4830191731 586 4842726854 587 4896755762 588 4907846664 589 4964005418 590 4976799270 591 5031945391 592 5044869488 593 5100580389 594 5112112500 595 5169915136 596 5183103272 597 5239954372 598 5253276314 599 5310702853 600 5322427800 601 5382165351 602 5395756702 603 5454346654 604 5468073608 605 5527251566 606 5539509630 607 5600884907 608 5614886688 609 5675251513 610 5689392530 611 5750356236 612 5763032640 613 5826203944 614 5840625266 615 5902799521 616 5917361912 617 5980147867 618 5993182308 619 6058253898 620 6073102120 621 6137122546 622 6152115542 623 6216758759 624 6230220048 625 6297167501 626 6312451914 627 6378353752 628 6393784808 629 6460322508 630 6474070890 631 6543078781 632 6558806888 633 6626627599 634 6642506126 635 6710974006 636 6725248440 637 6796123062 638 6812304334 639 6882079843 640 6898413440 641 6968849441 642 6983533476 643 7056436964 644 7073079048 645 7144847536 646 7161645794 647 7234086297 648 7249251816 649 7324158403 650 7341270950 651 7415069026 652 7432339688 653 7506823354 654 7522381902 655 7599426591 656 7617017392 657 7692883957 658 7710636794 659 7787200688 660 7803075720 661 7882382036 662 7900460922 663 7978433269 664 7996676168 665 8075359671 666 8091848052 667 8173166542 668 8191741448 669 8271859198 670 8290602110 671 8371442971 672 8388319968 673 8471923209 674 8491004146 675 8573305276 676 8592556232 677 8675594552 678 8693004798 679 8778796433 680 8798391480 681 8882916331 682 8902685462 683 8987959674 684 9005892840 685 9093931906 686 9114051254 687 9200838487 688 9221133968 689 9308684893 690 9327048780 691 9417476616 692 9438128488 693 9527219164 694 9548051306 695 9637918061 696 9656839224 697 9749578847 698 9770773614 699 9862207078 700 9883584200 701 9975808326 702 9995233950 703 10090388179 704 10112134208 705 10205952241 706 10227884834 707 10322506132 708 10342447008 709 10440055488 710 10462363330 711 10558605961 712 10581102488 713 10678163219 714 10698581712 715 10798732946 716 10821611112 717 10920320842 718 10943391974 719 11042932623 720 11063726640 721 11166574021 722 11190033242 723 11291250784 724 11314905128 725 11416968676 726 11438511150 727 11543733477 728 11567782408 729 11671550983 730 11695799390 731 11800427006 732 11822545176 733 11930367374 734 11955016926 735 12061377931 736 12086229152 737 12193464537 738 12216156804 739 12326633068 740 12351892040 741 12460889416 742 12486354482 743 12596239489 744 12619517448 745 12732689211 746 12758568694 747 12870244522 748 12896332328 749 13008911378 750 13032717750 751 13148695751 752 13175204688 753 13289603629 754 13316325386 755 13431641016 756 13456016784 757 13574813932 758 13601963594 759 13719128413 760 13746493160 761 13864590511 762 13889627796 763 14011206294 764 14039005768 765 14158981846 766 14187000974 767 14307923267 768 14333610240 769 14458036673 770 14486497410 771 14609328196 772 14638010888 773 14761803984 774 14788109790 775 14915470201 776 14944601432 777 15070333027 778 15099690854 779 15226398658 780 15253158960 781 15383673306 782 15413486662 783 15542163199 784 15572205488 785 15701874581 786 15729439860 787 15862813712 788 15893318568 789 16024986868 790 16055725370 791 16188400341 792 16216682328 793 16353060439 794 16384268606 795 16518973486 796 16550417672 797 16686145822 798 16714996578 799 16854583803 800 16886504800 801 17024293801 802 17056455602 803 17195282204 804 17224870272 805 17367555416 806 17400201234 807 17541119857 808 17574008888 809 17715981963 810 17746197660 811 17892148186 812 17925528488 813 18069624994 814 18103253366 815 18248418871 816 18279411024 817 18428536317 818 18462663274 819 18609983848 820 18644361320 821 18792767996 822 18824435406 823 18976895309 824 19011778728 825 19162372351 826 19197511214 827 19349205702 828 19381640184 829 19537401958 830 19573054190 831 19726967731 832 19762877888 833 19917909649 834 19951029732 835 20110234356 836 20146665352 837 20303948512 838 20340642434 839 20499058793 840 20532554280 841 20695571891 842 20732794182 843 20893494514 844 20930982248 845 21092833386 846 21127476942 847 21293595247 848 21331618928 849 21495786853 850 21534081050 851 21699414976 852 21734816496 853 21904486404 854 21943324186 855 22111007941 856 22150118792 857 22318986407 858 22355143668 859 22528428638 860 22568090760 861 22739341486 862 22779281822 863 22951731819 864 22988740896 865 23165606521 866 23206105874 867 23380972492 868 23421752648 869 23597836648 870 23635548390 871 23816205921 872 23857552888 873 24036087259 874 24077720246 875 24257487626 876 24296061480 877 24480414002 878 24522621654 879 24704873383 880 24747369680 881 24930872781 882 24970231440 883 25158419224 884 25201498088 885 25387519756 886 25430892554 887 25618181437 888 25658427000 889 25850411343 890 25894374670 891 26084216566 892 26128476488 893 26319604214 894 26360656542 895 26556581411 896 26601439872 897 26795155297 898 26840315714 899 27035333028 900 27077045400 901 27277121776 902 27322888802 903 27520528729 904 27566600408 905 27765561091 906 27808338180 907 28012226082 908 28058912488 909 28260530938 910 28307527430 911 28510482911 912 28554179184 913 28762089269 914 28809708666 915 29015357296 916 29063289512 917 29270294292 918 29314873134 919 29526907573 920 29575470920 921 29785204471 922 29834086142 923 30045192334 924 30090549720 925 30306878526 926 30356399614 927 30570270427 928 30620112608 929 30835375433 930 30881712060 931 31102200956 932 31152690888 933 31370754424 934 31421571026 935 31641043281 936 31688411976 937 31913074987 938 31964547734 939 32186857018 940 32238659240 941 32462396866 942 32510636526 943 32739702039 944 32792168848 945 33018780061 946 33071581994 947 33299638472 948 33348853968 949 33582284828 950 33635759850 951 33866726701 952 33920539688 953 34152971679 954 34203160980 955 34441027366 956 34495521992 957 34730901382 958 34785739694 959 35022601363 960 35073487680 961 35316134961 962 35371663522 963 35611509844 964 35667384968 965 35908733696 966 35960813490 967 36207814217 968 36264388248 969 36508759123 970 36565685510 971 36811576146 972 36864762120 973 37116273034 974 37173907046 975 37422857551 976 37480846832 977 37731337477 978 37785485748 979 38041720608 980 38100426280 981 38354014756 982 38413081562 983 38668227749 984 38723447448 985 38984367431 986 39044159454 987 39302441662 988 39362597768 989 39622458318 990 39678626790 991 39944425291 992 40005315488 993 40268350489 994 40329610706 995 40594241836 996 40651540800 997 40922107272 998 40984110514 999 41251954753 1000 41314331000