0 1 1 2 2 4 3 8 4 14 5 22 6 33 7 47 8 66 9 91 10 121 11 158 12 204 13 258 14 323 15 399 16 487 17 590 18 708 19 843 20 996 21 1170 22 1365 23 1583 24 1827 25 2097 26 2397 27 2728 28 3091 29 3490 30 3927 31 4403 32 4921 33 5483 34 6092 35 6751 36 7462 37 8227 38 9050 39 9933 40 10879 41 11891 42 12972 43 14125 44 15353 45 16660 46 18048 47 19521 48 21083 49 22737 50 24486 51 26334 52 28284 53 30341 54 32509 55 34790 56 37189 57 39711 58 42358 59 45136 60 48048 61 51098 62 54292 63 57633 64 61126 65 64775 66 68586 67 72562 68 76708 69 81030 70 85531 71 90218 72 95095 73 100166 74 105438 75 110916 76 116604 77 122508 78 128633 79 134985 80 141570 81 148393 82 155459 83 162775 84 170346 85 178178 86 186277 87 194649 88 203300 89 212236 90 221464 91 230989 92 240818 93 250958 94 261415 95 272195 96 283305 97 294751 98 306541 99 318682 100 331179 101 344040 102 357273 103 370883 104 384879 105 399267 106 414054 107 429249 108 444858 109 460889 110 477349 111 494247 112 511589 113 529383 114 547638 115 566360 116 585559 117 605242 118 625416 119 646091 120 667275 121 688975 122 711200 123 733958 124 757258 125 781109 126 805519 127 830496 128 856050 129 882189 130 908922 131 936258 132 964206 133 992775 134 1021974 135 1051813 136 1082300 137 1113445 138 1145258 139 1177748 140 1210924 141 1244796 142 1279373 143 1314666 144 1350685 145 1387438 146 1424936 147 1463190 148 1502208 149 1542002 150 1582581 151 1623955 152 1666136 153 1709133 154 1752957 155 1797618 156 1843128 157 1889496 158 1936733 159 1984851 160 2033859 161 2083770 162 2134594 163 2186341 164 2239024 165 2292654 166 2347241 167 2402797 168 2459333 169 2516861 170 2575393 171 2634940 172 2695513 173 2757125 174 2819787 175 2883511 176 2948309 177 3014193 178 3081175 179 3149267 180 3218482 181 3288831 182 3360327 183 3432983 184 3506811 185 3581823 186 3658032 187 3735450 188 3814091 189 3893968 190 3975092 191 4057477 192 4141137 193 4226083 194 4312330 195 4399890 196 4488776 197 4579003 198 4670583 199 4763530 200 4857857 201 4953579 202 5050708 203 5149258 204 5249244 205 5350678 206 5453576 207 5557951 208 5663816 209 5771187 210 5880078 211 5990502 212 6102474 213 6216008 214 6331119 215 6447822 216 6566131 217 6686060 218 6807625 219 6930840 220 7055720 221 7182280 222 7310535 223 7440500 224 7572190 225 7705621 226 7840807 227 7977764 228 8116508 229 8257054 230 8399417 231 8543613 232 8689657 233 8837566 234 8987356 235 9139041 236 9292638 237 9448164 238 9605633 239 9765063 240 9926469 241 10089867 242 10255275 243 10422708 244 10592183 245 10763716 246 10937325 247 11113025 248 11290833 249 11470767 250 11652842 251 11837077 252 12023488 253 12212091 254 12402905 255 12595947 256 12791233 257 12988781 258 13188608 259 13390732 260 13595171 261 13801942 262 14011062 263 14222550 264 14436423 265 14652699 266 14871396 267 15092532 268 15316125 269 15542193 270 15770755 271 16001828 272 16235431 273 16471583 274 16710302 275 16951606 276 17195514 277 17442044 278 17691216 279 17943049 280 18197560 281 18454769 282 18714696 283 18977358 284 19242776 285 19510968 286 19781953 287 20055752 288 20332383 289 20611866 290 20894220 291 21179466 292 21467622 293 21758708 294 22052745 295 22349751 296 22649748 297 22952755 298 23258791 299 23567878 300 23880036 301 24195284 302 24513643 303 24835133 304 25159775 305 25487590 306 25818598 307 26152819 308 26490275 309 26830986 310 27174973 311 27522257 312 27872859 313 28226800 314 28584101 315 28944784 316 29308869 317 29676378 318 30047333 319 30421755 320 30799665 321 31181085 322 31566036 323 31954541 324 32346622 325 32742299 326 33141595 327 33544533 328 33951133 329 34361419 330 34775412 331 35193134 332 35614609 333 36039858 334 36468904 335 36901769 336 37338477 337 37779049 338 38223508 339 38671878 340 39124180 341 39580439 342 40040677 343 40504916 344 40973181 345 41445495 346 41921880 347 42402360 348 42886958 349 43375698 350 43868604 351 44365699 352 44867006 353 45372550 354 45882354 355 46396442 356 46914838 357 47437566 358 47964650 359 48496114 360 49031983 361 49572280 362 50117030 363 50666258 364 51219988 365 51778244 366 52341051 367 52908433 368 53480416 369 54057025 370 54638283 371 55224216 372 55814850 373 56410208 374 57010317 375 57615201 376 58224885 377 58839396 378 59458758 379 60082997 380 60712138 381 61346208 382 61985231 383 62629233 384 63278241 385 63932279 386 64591375 387 65255554 388 65924841 389 66599264 390 67278849 391 67963621 392 68653607 393 69348833 394 70049326 395 70755113 396 71466220 397 72182673 398 72904500 399 73631727 400 74364381 401 75102489 402 75846078 403 76595175 404 77349807 405 78110002 406 78875786 407 79647187 408 80424233 409 81206951 410 81995368 411 82789512 412 83589410 413 84395091 414 85206583 415 86023912 416 86847107 417 87676197 418 88511208 419 89352170 420 90199110 421 91052056 422 91911038 423 92776083 424 93647220 425 94524477 426 95407884 427 96297468 428 97193258 429 98095284 430 99003573 431 99918156 432 100839061 433 101766316 434 102699952 435 103639998 436 104586482 437 105539434 438 106498883 439 107464859 440 108437392 441 109416511 442 110402245 443 111394625 444 112393680 445 113399440 446 114411935 447 115431195 448 116457250 449 117490130 450 118529866 451 119576487 452 120630024 453 121690508 454 122757969 455 123832437 456 124913943 457 126002517 458 127098191 459 128200996 460 129310961 461 130428118 462 131552499 463 132684133 464 133823053 465 134969289 466 136122872 467 137283835 468 138452208 469 139628023 470 140811311 471 142002105 472 143200435 473 144406333 474 145619832 475 146840962 476 148069757 477 149306248 478 150550466 479 151802445 480 153062217 481 154329813 482 155605266 483 156888608 484 158179872 485 159479091 486 160786297 487 162101522 488 163424800 489 164756163 490 166095644 491 167443276 492 168799092 493 170163125 494 171535408 495 172915975 496 174304858 497 175702091 498 177107708 499 178521742 500 179944226 501 181375194 502 182814679 503 184262716 504 185719339 505 187184580 506 188658474 507 190141056 508 191632358 509 193132416 510 194641263 511 196158933 512 197685462 513 199220883 514 200765231 515 202318540 516 203880846 517 205452182 518 207032583 519 208622085 520 210220721 521 211828528 522 213445540 523 215071791 524 216707318 525 218352156 526 220006339 527 221669903 528 223342883 529 225025315 530 226717235 531 228418678 532 230129679 533 231850275 534 233580501 535 235320393 536 237069987 537 238829319 538 240598425 539 242377341 540 244166104 541 245964749 542 247773313 543 249591833 544 251420345 545 253258885 546 255107490 547 256966196 548 258835041 549 260714062 550 262603294 551 264502775 552 266412543 553 268332633 554 270263084 555 272203932 556 274155214 557 276116969 558 278089233 559 280072044 560 282065439 561 284069457 562 286084134 563 288109508 564 290145618 565 292192500 566 294250194 567 296318737 568 298398166 569 300488521 570 302589840 571 304702160 572 306825520 573 308959958 574 311105513 575 313262224 576 315430129 577 317609266 578 319799675 579 322001394 580 324214462 581 326438918 582 328674801 583 330922150 584 333181004 585 335451403 586 337733385 587 340026990 588 342332258 589 344649228 590 346977939 591 349318431 592 351670743 593 354034916 594 356410990 595 358799003 596 361198996 597 363611010 598 366035083 599 368471257 600 370919571 601 373380065 602 375852781 603 378337758 604 380835037 605 383344658 606 385866663 607 388401091 608 390947983 609 393507381 610 396079324 611 398663855 612 401261014 613 403870841 614 406493379 615 409128669 616 411776751 617 414437667 618 417111458 619 419798166 620 422497833 621 425210500 622 427936208 623 430675000 624 433426917 625 436192001 626 438970294 627 441761838 628 444566675 629 447384847 630 450216397 631 453061366 632 455919797 633 458791733 634 461677216 635 464576288 636 467488992 637 470415370 638 473355466 639 476309323 640 479276982 641 482258487 642 485253882 643 488263208 644 491286510 645 494323830 646 497375211 647 500440698 648 503520333 649 506614160 650 509722222 651 512844564 652 515981228 653 519132258 654 522297699 655 525477593 656 528671986 657 531880921 658 535104441 659 538342592 660 541595418 661 544862962 662 548145269 663 551442383 664 554754349 665 558081212 666 561423016 667 564779805 668 568151625 669 571538520 670 574940535 671 578357715 672 581790105 673 585237750 674 588700695 675 592178986 676 595672667 677 599181784 678 602706383 679 606246509 680 609802207 681 613373523 682 616960502 683 620563191 684 624181636 685 627815881 686 631465973 687 635131959 688 638813883 689 642511793 690 646225734 691 649955752 692 653701895 693 657464208 694 661242738 695 665037531 696 668848635 697 672676095 698 676519958 699 680380272 700 684257082 701 688150437 702 692060383 703 695986966 704 699930235 705 703890237 706 707867018 707 711860626 708 715871108 709 719898512 710 723942886 711 728004277 712 732082732 713 736178300 714 740291028 715 744420964 716 748568156 717 752732652 718 756914500 719 761113748 720 765330445 721 769564638 722 773816376 723 778085708 724 782372682 725 786677346 726 790999749 727 795339939 728 799697966 729 804073879 730 808467725 731 812879554 732 817309416 733 821757358 734 826223431 735 830707683 736 835210163 737 839730922 738 844270008 739 848827471 740 853403360 741 857997726 742 862610617 743 867242083 744 871892175 745 876560941 746 881248433 747 885954700 748 890679791 749 895423758 750 900186651 751 904968519 752 909769413 753 914589383 754 919428480 755 924286755 756 929164258 757 934061039 758 938977150 759 943912641 760 948867563 761 953841967 762 958835904 763 963849425 764 968882581 765 973935424 766 979008004 767 984100373 768 989212583 769 994344685 770 999496730 771 1004668770 772 1009860856 773 1015073041 774 1020305377 775 1025557914 776 1030830705 777 1036123803 778 1041437258 779 1046771124 780 1052125452 781 1057500294 782 1062895704 783 1068311733 784 1073748434 785 1079205859 786 1084684062 787 1090183094 788 1095703008 789 1101243858 790 1106805695 791 1112388574 792 1117992547 793 1123617666 794 1129263986 795 1134931560 796 1140620440 797 1146330680 798 1152062333 799 1157815453 800 1163590094 801 1169386309 802 1175204151 803 1181043675 804 1186904934 805 1192787982 806 1198692873 807 1204619661 808 1210568400 809 1216539144 810 1222531948 811 1228546865 812 1234583950 813 1240643258 814 1246724843 815 1252828759 816 1258955061 817 1265103803 818 1271275041 819 1277468830 820 1283685223 821 1289924276 822 1296186045 823 1302470583 824 1308777947 825 1315108191 826 1321461370 827 1327837541 828 1334236758 829 1340659077 830 1347104553 831 1353573243 832 1360065201 833 1366580483 834 1373119146 835 1379681244 836 1386266835 837 1392875974 838 1399508716 839 1406165119 840 1412845239 841 1419549131 842 1426276852 843 1433028458 844 1439804006 845 1446603553 846 1453427155 847 1460274868 848 1467146750 849 1474042857 850 1480963246 851 1487907974 852 1494877098 853 1501870675 854 1508888762 855 1515931417 856 1522998696 857 1530090657 858 1537207358 859 1544348856 860 1551515208 861 1558706472 862 1565922705 863 1573163966 864 1580430313 865 1587721802 866 1595038492 867 1602380442 868 1609747708 869 1617140350 870 1624558425 871 1632001991 872 1639471108 873 1646965833 874 1654486225 875 1662032342 876 1669604244 877 1677201988 878 1684825633 879 1692475239 880 1700150863 881 1707852566 882 1715580406 883 1723334441 884 1731114732 885 1738921338 886 1746754317 887 1754613729 888 1762499633 889 1770412089 890 1778351157 891 1786316896 892 1794309365 893 1802328625 894 1810374735 895 1818447755 896 1826547745 897 1834674765 898 1842828875 899 1851010135 900 1859218606 901 1867454347 902 1875717419 903 1884007883 904 1892325799 905 1900671227 906 1909044228 907 1917444862 908 1925873191 909 1934329276 910 1942813176 911 1951324953 912 1959864669 913 1968432383 914 1977028158 915 1985652054 916 1994304132 917 2002984455 918 2011693083 919 2020430078 920 2029195501 921 2037989415 922 2046811880 923 2055662958 924 2064542712 925 2073451202 926 2082388492 927 2091354643 928 2100349716 929 2109373775 930 2118426882 931 2127509098 932 2136620486 933 2145761108 934 2154931027 935 2164130306 936 2173359007 937 2182617192 938 2191904925 939 2201222268 940 2210569284 941 2219946036 942 2229352587 943 2238789000 944 2248255338 945 2257751665 946 2267278043 947 2276834536 948 2286421208 949 2296038122 950 2305685341 951 2315362929 952 2325070949 953 2334809466 954 2344578544 955 2354378245 956 2364208634 957 2374069776 958 2383961733 959 2393884571 960 2403838353 961 2413823143 962 2423839007 963 2433886008 964 2443964211 965 2454073680 966 2464214481 967 2474386677 968 2484590333 969 2494825515 970 2505092286 971 2515390713 972 2525720860 973 2536082791 974 2546476573 975 2556902271 976 2567359949 977 2577849673 978 2588371508 979 2598925520 980 2609511775 981 2620130338 982 2630781274 983 2641464650 984 2652180531 985 2662928983 986 2673710072 987 2684523864 988 2695370425 989 2706249821 990 2717162119 991 2728107384 992 2739085683 993 2750097083 994 2761141650 995 2772219450 996 2783330550 997 2794475016 998 2805652916 999 2816864317 1000 2828109284