0 1 1 0 2 1 3 2 4 6 5 6 6 21 7 27 8 48 9 73 10 112 11 149 12 224 13 289 14 390 15 507 16 656 17 812 18 1037 19 1259 20 1545 21 1866 22 2245 23 2648 24 3158 25 3679 26 4300 27 4983 28 5757 29 6579 30 7554 31 8562 32 9713 33 10960 34 12339 35 13798 36 15463 37 17190 38 19111 39 21170 40 23409 41 25767 42 28392 43 31116 44 34092 45 37255 46 40654 47 44219 48 48119 49 52162 50 56523 51 61128 52 66032 53 71156 54 76691 55 82421 56 88542 57 94971 58 101770 59 108851 60 116426 61 124255 62 132556 63 141237 64 150366 65 159846 66 169911 67 180297 68 191243 69 202648 70 214587 71 226954 72 240004 73 253449 74 267550 75 282197 76 297471 77 313257 78 329832 79 346884 80 364695 81 383146 82 402325 83 422108 84 442793 85 464044 86 486165 87 509028 88 532727 89 557129 90 582554 91 608642 92 635718 93 663645 94 692524 95 722213 96 753053 97 784660 98 817381 99 851070 100 885834 101 921522 102 958497 103 996351 104 1035452 105 1075645 106 1117044 107 1159489 108 1203364 109 1248237 110 1294498 111 1341983 112 1390812 113 1440816 114 1492401 115 1545111 116 1599357 117 1654966 118 1712065 119 1770476 120 1830626 121 1892035 122 1955136 123 2019747 124 2086001 125 2153711 126 2223326 127 2294342 128 2367213 129 2441748 130 2518087 131 2596034 132 2676059 133 2757634 134 2841235 135 2926662 136 3014061 137 3103227 138 3194652 139 3287784 140 3383120 141 3480451 142 3579930 143 3681343 144 3785203 145 3890934 146 3999055 147 4109348 148 4221972 149 4336704 150 4454079 151 4573497 152 4695498 153 4819855 154 4946734 155 5075903 156 5207918 157 5342155 158 5479176 159 5618745 160 5761034 161 5905802 162 6053627 163 6203861 164 6357087 165 6513060 166 6671959 167 6833534 168 6998384 169 7165837 170 7336498 171 7510113 172 7686867 173 7866501 174 8049636 175 8235576 176 8424947 177 8617486 178 8813385 179 9012376 180 9215101 181 9420840 182 9630241 183 9843032 184 10059411 185 10279101 186 10502766 187 10729662 188 10960458 189 11194873 190 11433112 191 11674889 192 11920889 193 12170344 194 12423945 195 12681402 196 12942926 197 13208222 198 13477997 199 13751459 200 14029320 201 14311281 202 14597560 203 14887853 204 15182888 205 15481849 206 15785470 207 16093443 208 16405992 209 16722804 210 17044629 211 17370627 212 17701553 213 18037090 214 18377469 215 18722368 216 19072558 217 19427175 218 19786996 219 20151695 220 20521509 221 20896107 222 21276282 223 21661146 224 22051497 225 22447000 226 22847899 227 23253854 228 23665679 229 24082462 230 24505023 231 24933018 232 25366697 233 25805711 234 26250896 235 26701316 236 27157812 237 27620031 238 28088230 239 28562051 240 29042351 241 29528170 242 30020371 243 30518592 244 31023096 245 31533516 246 32050731 247 32573757 248 33103478 249 33639523 250 34182162 251 34731019 252 35286994 253 35849079 254 36418180 255 36993917 256 37576566 257 38165742 258 38762367 259 39365409 260 39975795 261 40593136 262 41217715 263 41849138 264 42488348 265 43134289 266 43787910 267 44448813 268 45117287 269 45792929 270 46476704 271 47167532 272 47866383 273 48572850 274 49287229 275 50009108 276 50739473 277 51477220 278 52223341 279 52977420 280 53739759 281 54509937 282 55288962 283 56075706 284 56871182 285 57674965 286 58487364 287 59307949 288 60137749 289 60975612 290 61822573 291 62678198 292 63542802 293 64415946 294 65298681 295 66189831 296 67090452 297 68000101 298 68919100 299 69847001 300 70784876 301 71731525 302 72688026 303 73653927 304 74629556 305 75614456 306 76609721 307 77614127 308 78628773 309 79653198 310 80687737 311 81731924 312 82786874 313 83851339 314 84926440 315 86011707 316 87107481 317 88213287 318 89330262 319 90457134 320 91595045 321 92743516 322 93902895 323 95072698 324 96254083 325 97445754 326 98648875 327 99862958 328 101088357 329 102324579 330 103572804 331 104831712 332 106102488 333 107384635 334 108678514 335 109983623 336 111301163 337 112629790 338 113970711 339 115323420 340 116688284 341 118064792 342 119454167 343 120855041 344 122268642 345 123694455 346 125132854 347 126583319 348 128047094 349 129522787 350 131011648 351 132513153 352 134027682 353 135554706 354 137095491 355 138648621 356 140215367 357 141795196 358 143388495 359 144994726 360 146615176 361 148248405 362 149895706 363 151556537 364 153231291 365 154919421 366 156622236 367 158338272 368 160068843 369 161813398 370 163572337 371 165345104 372 167133029 373 168934624 374 170751225 375 172582272 376 174428171 377 176288357 378 178164182 379 180054134 380 181959570 381 183879921 382 185815600 383 187766033 384 189732593 385 191713744 386 193710865 387 195723378 388 197751702 389 199795254 390 201855429 391 203930667 392 206022368 393 208129945 394 210253824 395 212393413 396 214550128 397 216722385 398 218911606 399 221117195 400 223339584 401 225578172 402 227834397 403 230106651 404 232396377 405 234702970 406 237026869 407 239367464 408 241726214 409 244101487 410 246494748 411 248905383 412 251333837 413 253779491 414 256243826 415 258725186 416 261225057 417 263742816 418 266278915 419 268832726 420 271405751 421 273996310 422 276605911 423 279233922 424 281880801 425 284545911 426 287230776 427 289933692 428 292656188 429 295397623 430 298158462 431 300938059 432 303737959 433 306556434 434 309395035 435 312253112 436 315131136 437 318028452 438 320946627 439 323883909 440 326841870 441 329819851 442 332818330 443 335836643 444 338876378 445 341935759 446 345016380 447 348117573 448 351239822 449 354382454 450 357547079 451 360731897 452 363938523 453 367166280 454 370415659 455 373685978 456 376978868 457 380292505 458 383628526 459 386986245 460 390366159 461 393767577 462 397192152 463 400638036 464 404106887 465 407598010 466 411111909 467 414647884 468 418207609 469 421789212 470 425394373 471 429022388 472 432673767 473 436347801 474 440046186 475 443767026 476 447512022 477 451280461 478 455072860 479 458888501 480 462729101 481 466592740 482 470481141 483 474393582 484 478330586 485 482291426 486 486277841 487 490287887 488 494323308 489 498383373 490 502468612 491 506578289 492 510714164 493 514874269 494 519060370 495 523271727 496 527508876 497 531771072 498 536060097 499 540373959 500 544714445 501 549080806 502 553473585 503 557892028 504 562337938 505 566809299 506 571307920 507 575833043 508 580385217 509 584963679 510 589570254 511 594202902 512 598863453 513 603551140 514 608266519 515 613008818 516 617779883 517 622577650 518 627403971 519 632258070 520 637140509 521 642050507 522 646989932 523 651956696 524 656952672 525 661977075 526 667030474 527 672112079 528 677223779 529 682363462 530 687533023 531 692731668 532 697959972 533 703217136 534 708505071 535 713821641 536 719168762 537 724545631 538 729952830 539 735389551 540 740857726 541 746355195 542 751883896 543 757443017 544 763033146 545 768653466 546 774305931 547 779988357 548 785702703 549 791448148 550 797225287 551 803033294 552 808874144 553 814745629 554 820649730 555 826585617 556 832553891 557 838553717 558 844587092 559 850651784 560 856749795 561 862880286 562 869043865 563 875239688 564 881469773 565 887731864 566 894027985 567 900357288 568 906720387 569 913116429 570 919547454 571 926011182 572 932509658 573 939042025 574 945608904 575 952209433 576 958845673 577 965515320 578 972220441 579 978960170 580 985735134 581 992544462 582 999390237 583 1006270131 584 1013186232 585 1020137665 586 1027125064 587 1034147549 588 1041207224 589 1048301737 590 1055433198 591 1062600723 592 1069804952 593 1077044996 594 1084322981 595 1091636531 596 1098987777 597 1106375826 598 1113801325 599 1121263376 600 1128764126 601 1136301175 602 1143876676 603 1151489727 604 1159140981 605 1166829531 606 1174557546 607 1182322602 608 1190126873 609 1197969448 610 1205850987 611 1213770574 612 1221730399 613 1229728014 614 1237765615 615 1245842282 616 1253958681 617 1262113887 618 1270310112 619 1278544884 620 1286820420 621 1295135791 622 1303491670 623 1311887123 624 1320324383 625 1328800954 626 1337319075 627 1345877808 628 1354477832 629 1363118204 630 1371801179 631 1380524237 632 1389289638 633 1398096435 634 1406945314 635 1415835323 636 1424768738 637 1433743015 638 1442760436 639 1451820045 640 1460922534 641 1470066942 642 1479255567 643 1488485841 644 1497760067 645 1507077280 646 1516438179 647 1525841794 648 1535290444 649 1544781537 650 1554317398 651 1563897053 652 1573521207 653 1583188881 654 1592902416 655 1602659196 656 1612461567 657 1622308546 658 1632200845 659 1642137476 660 1652120801 661 1662148180 662 1672221981 663 1682341212 664 1692506591 665 1702717121 666 1712975186 667 1723278122 668 1733628318 669 1744024773 670 1754468212 671 1764957629 672 1775495429 673 1786078924 674 1796710525 675 1807389222 676 1818115746 677 1828889082 678 1839711657 679 1850580759 680 1861498820 681 1872464821 682 1883479500 683 1894541833 684 1905654268 685 1916814069 686 1928023690 687 1939282103 688 1950590052 689 1961946504 690 1973353929 691 1984809567 692 1996315893 693 2007871870 694 2019478249 695 2031133988 696 2042841578 697 2054598235 698 2066406456 699 2078265195 700 2090175209 701 2102135447 702 2114148422 703 2126211326 704 2138326677 705 2150493420 706 2162712319 707 2174982314 708 2187305939 709 2199680362 710 2212108123 711 2224588158 712 2237121237 713 2249706291 714 2262345876 715 2275037136 716 2287782632 717 2300581291 718 2313433890 719 2326339351 720 2339300251 721 2352313710 722 2365382311 723 2378504972 724 2391682476 725 2404913736 726 2418201351 727 2431542417 728 2444939538 729 2458391623 730 2471899462 731 2485461959 732 2499081734 733 2512755859 734 2526486960 735 2540273937 736 2554117586 737 2568016802 738 2581974227 739 2595986909 740 2610057495 741 2624184876 742 2638369855 743 2652611318 744 2666911928 745 2681268709 746 2695684330 747 2710157673 748 2724689547 749 2739278829 750 2753928204 751 2768634672 752 2783400923 753 2798225830 754 2813110209 755 2828052928 756 2843056693 757 2858118480 758 2873241001 759 2888423120 760 2903665659 761 2918967477 762 2934331302 763 2949754086 764 2965238562 765 2980783585 766 2996389984 767 3012056609 768 3027786209 769 3043575712 770 3059427873 771 3075341538 772 3091317542 773 3107354726 774 3123455861 775 3139617851 776 3155843472 777 3172131561 778 3188482960 779 3204896501 780 3221374976 781 3237915265 782 3254520166 783 3271188507 784 3287921136 785 3304716876 786 3321578541 787 3338502987 788 3355493033 789 3372547498 790 3389667237 791 3406851064 792 3424101814 793 3441416319 794 3458797420 795 3476243927 796 3493756701 797 3511334547 798 3528980322 799 3546690834 800 3564468945 801 3582313456 802 3600225235 803 3618203078 804 3636249863 805 3654362374 806 3672543495 807 3690792018 808 3709108817 809 3727492679 810 3745946504 811 3764467052 812 3783057228 813 3801715815 814 3820443694 815 3839239643 816 3858106583 817 3877041250 818 3896046571 819 3915121320 820 3934266384 821 3953480532 822 3972766707 823 3992121621 824 4011548222 825 4031045275 826 4050613674 827 4070252179 828 4089963754 829 4109745087 830 4129599148 831 4149524693 832 4169522622 833 4189591686 834 4209734871 835 4229948841 836 4250236587 837 4270596856 838 4291030555 839 4311536426 840 4332117476 841 4352770345 842 4373498046 843 4394299317 844 4415175071 845 4436124041 846 4457149256 847 4478247332 848 4499421303 849 4520669898 850 4541994037 851 4563392444 852 4584868169 853 4606417804 854 4628044405 855 4649746692 856 4671525591 857 4693379817 858 4715312442 859 4737320034 860 4759405670 861 4781568061 862 4803808140 863 4826124613 864 4848520573 865 4870992564 866 4893543685 867 4916172638 868 4938880362 869 4961665554 870 4984531329 871 5007474207 872 5030497308 873 5053599325 874 5076781204 875 5100041633 876 5123383748 877 5146804045 878 5170305666 879 5193887295 880 5217549884 881 5241292112 882 5265117137 883 5289021431 884 5313008157 885 5337075990 886 5361225889 887 5385456524 888 5409771074 889 5434165987 890 5458644448 891 5483205123 892 5507848977 893 5532574671 894 5557385406 895 5582277606 896 5607254477 897 5632314676 898 5657459175 899 5682686626 900 5708000251 901 5733396450 902 5758878451 903 5784444902 904 5810096781 905 5835832731 906 5861655996 907 5887562952 908 5913556848 909 5939636323 910 5965802362 911 5992053599 912 6018393299 913 6044817814 914 6071330415 915 6097929732 916 6124616756 917 6151390112 918 6178253087 919 6205202009 920 6232240170 921 6259366191 922 6286581070 923 6313883423 924 6341276558 925 6368756779 926 6396327400 927 6423987033 928 6451736682 929 6479574954 930 6507505179 931 6535523637 932 6563633663 933 6591833860 934 6620125239 935 6648506398 936 6676980688 937 6705544365 938 6734200786 939 6762948545 940 6791788659 941 6820719717 942 6849745092 943 6878861016 944 6908070867 945 6937373230 946 6966769129 947 6996257144 948 7025840669 949 7055515912 950 7085286273 951 7115150328 952 7145109107 953 7175161181 954 7205309966 955 7235551646 956 7265889642 957 7296322521 958 7326851320 959 7357474601 960 7388195801 961 7419011080 962 7449923881 963 7480932762 964 7512038766 965 7543240446 966 7574541261 967 7605937347 968 7637432168 969 7669024273 970 7700714712 971 7732502029 972 7764389704 973 7796373849 974 7828457950 975 7860640547 976 7892922696 977 7925302932 978 7957784757 979 7990364259 980 8023044945 981 8055825346 982 8088706525 983 8121687008 984 8154770318 985 8187952519 986 8221237140 987 8254622703 988 8288110277 989 8321698379 990 8355390554 991 8389182842 992 8423078793 993 8457076920 994 8491178299 995 8525381438 996 8559689903 997 8594099710 998 8628614431 999 8663232570 1000 8697955209