0 1 1 3 2 10 3 23 4 47 5 84 6 141 7 221 8 333 9 480 10 674 11 918 12 1226 13 1602 14 2062 15 2611 16 3266 17 4033 18 4932 19 5969 20 7166 21 8529 22 10083 23 11835 24 13811 25 16019 26 18487 27 21224 28 24260 29 27604 30 31289 31 35324 32 39744 33 44559 34 49806 35 55496 36 61667 37 68331 38 75529 39 83273 40 91606 41 100540 42 110121 43 120362 44 131310 45 142979 46 155418 47 168642 48 182702 49 197613 50 213429 51 230165 52 247877 53 266581 54 286335 55 307156 56 329103 57 352194 58 376491 59 402012 60 428821 61 456936 62 486424 63 517304 64 549644 65 583464 66 618834 67 655775 68 694359 69 734607 70 776594 71 820341 72 865925 73 913368 74 962749 75 1014091 76 1067474 77 1122922 78 1180518 79 1240286 80 1302311 81 1366617 82 1433292 83 1502361 84 1573913 85 1647974 86 1724635 87 1803923 88 1885931 89 1970686 90 2058284 91 2148752 92 2242188 93 2338620 94 2438148 95 2540801 96 2646680 97 2755815 98 2868310 99 2984195 100 3103576 101 3226483 102 3353025 103 3483233 104 3617217 105 3755009 106 3896721 107 4042386 108 4192118 109 4345950 110 4503999 111 4666298 112 4832966 113 5004037 114 5179632 115 5359786 116 5544621 117 5734173 118 5928567 119 6127839 120 6332116 121 6541434 122 6755923 123 6975620 124 7200656 125 7431069 126 7666992 127 7908464 128 8155620 129 8408499 130 8667239 131 8931879 132 9202559 133 9479319 134 9762301 135 10051546 136 10347197 137 10649296 138 10957989 139 11273318 140 11595431 141 11924370 142 12260286 143 12603222 144 12953330 145 13310654 146 13675348 147 14047457 148 14427137 149 14814433 150 15209504 151 15612395 152 16023267 153 16442166 154 16869255 155 17304581 156 17748308 157 18200484 158 18661276 159 19130732 160 19609021 161 20096191 162 20592414 163 21097739 164 21612339 165 22136264 166 22669689 167 23212665 168 23765369 169 24327852 170 24900294 171 25482746 172 26075390 173 26678278 174 27291594 175 27915391 176 28549854 177 29195037 178 29851128 179 30518181 180 31196386 181 31885797 182 32586607 183 33298871 184 34022783 185 34758399 186 35505915 187 36265388 188 37037016 189 37820856 190 38617109 191 39425832 192 40247228 193 41081355 194 41928418 195 42788476 196 43661735 197 44548255 198 45448245 199 46361765 200 47289026 201 48230088 202 49185165 203 50154318 204 51137762 205 52135559 206 53147926 207 54174926 208 55216778 209 56273545 210 57345449 211 58432553 212 59535081 213 60653097 214 61786827 215 62936336 216 64101851 217 65283438 218 66481327 219 67695584 220 68926441 221 70173964 222 71438388 223 72719780 224 74018376 225 75334244 226 76667622 227 78018579 228 79387355 229 80774019 230 82178814 231 83601809 232 85043249 233 86503204 234 87981921 235 89479471 236 90996102 237 92531886 238 94087074 239 95661738 240 97256131 241 98870325 242 100504576 243 102158957 244 103833725 245 105528954 246 107244903 247 108981647 248 110739447 249 112518378 250 114318704 251 116140500 252 117984032 253 119849376 254 121736800 255 123646381 256 125578388 257 127532899 258 129510186 259 131510327 260 133533596 261 135580071 262 137650029 263 139743549 264 141860909 265 144002189 266 146167669 267 148357430 268 150571754 269 152810722 270 155074619 271 157363526 272 159677730 273 162017313 274 164382564 275 166773566 276 169190609 277 171633777 278 174103363 279 176599451 280 179122336 281 181672102 282 184249047 283 186853256 284 189485028 285 192144449 286 194831820 287 197547228 288 200290976 289 203063151 290 205864059 291 208693787 292 211552643 293 214440715 294 217358313 295 220305526 296 223282665 297 226289820 298 229327305 299 232395210 300 235493851 301 238623318 302 241783930 303 244975778 304 248199182 305 251454234 306 254741256 307 258060341 308 261411813 309 264795765 310 268212524 311 271662183 312 275145071 313 278661282 314 282211147 315 285794761 316 289412456 317 293064328 318 296750712 319 300471704 320 304227641 321 308018619 322 311844978 323 315706815 324 319604471 325 323538044 326 327507877 327 331514069 328 335556965 329 339636664 330 343753514 331 347907614 332 352099314 333 356328714 334 360596166 335 364901771 336 369245882 337 373628601 338 378050284 339 382511033 340 387011206 341 391550905 342 396130491 343 400750067 344 405409995 345 410110379 346 414851583 347 419633712 348 424457132 349 429321948 350 434228529 351 439176980 352 444167672 353 449200711 354 454276470 355 459395056 356 464556843 357 469761939 358 475010721 359 480303297 360 485640046 361 491021076 362 496446769 363 501917234 364 507432854 365 512993739 366 518600274 367 524252570 368 529951014 369 535695717 370 541487069 371 547325181 372 553210445 373 559142973 374 565123159 375 571151116 376 577227239 377 583351642 378 589524723 379 595746596 380 602017661 381 608338032 382 614708112 383 621128016 384 627598148 385 634118624 386 640689850 387 647311943 388 653985311 389 660710071 390 667486634 391 674315117 392 681195933 393 688129200 394 695115333 395 702154451 396 709246970 397 716393010 398 723592990 399 730847030 400 738155551 401 745518673 402 752936820 403 760410113 404 767938977 405 775523534 406 783164211 407 790861131 408 798614723 409 806425110 410 814292724 411 822217688 412 830200436 413 838241092 414 846340092 415 854497561 416 862713936 417 870989343 418 879324222 419 887718699 420 896173216 421 904687899 422 913263193 423 921899225 424 930596441 425 939354969 426 948175257 427 957057434 428 966001950 429 975008934 430 984078839 431 993211794 432 1002408254 433 1011668349 434 1020992536 435 1030380946 436 1039834037 437 1049351941 438 1058935119 439 1068583703 440 1078298156 441 1088078610 442 1097925531 443 1107839052 444 1117819640 445 1127867429 446 1137982888 447 1148166152 448 1158417692 449 1168737643 450 1179126479 451 1189584335 452 1200111687 453 1210708671 454 1221375765 455 1232113106 456 1242921173 457 1253800104 458 1264750381 459 1275772142 460 1286865871 461 1298031706 462 1309270134 463 1320581294 464 1331965674 465 1343423414 466 1354955004 467 1366560585 468 1378240649 469 1389995337 470 1401825144 471 1413730211 472 1425711035 473 1437767758 474 1449900879 475 1462110541 476 1474397244 477 1486761132 478 1499202708 479 1511722116 480 1524319861 481 1536996087 482 1549751302 483 1562585651 484 1575499643 485 1588493424 486 1601567505 487 1614722033 488 1627957521 489 1641274116 490 1654672334 491 1668152322 492 1681714598 493 1695359310 494 1709086978 495 1722897751 496 1736792150 497 1750770325 498 1764832800 499 1778979725 500 1793211626 501 1807528653 502 1821931335 503 1836419823 504 1850994647 505 1865655959 506 1880404291 507 1895239796 508 1910163008 509 1925174080 510 1940273549 511 1955461568 512 1970738676 513 1986105027 514 2001561162 515 2017107236 516 2032743791 517 2048470983 518 2064289357 519 2080199069 520 2096200666 521 2112294304 522 2128480533 523 2144759510 524 2161131786 525 2177597519 526 2194157262 527 2210811174 528 2227559810 529 2244403329 530 2261342289 531 2278376849 532 2295507569 533 2312734609 534 2330058531 535 2347479496 536 2364998067 537 2382614406 538 2400329079 539 2418142248 540 2436054481 541 2454065940 542 2472177196 543 2490388412 544 2508700160 545 2527112604 546 2545626318 547 2564241467 548 2582958627 549 2601777963 550 2620700054 551 2639725065 552 2658853577 553 2678085756 554 2697422185 555 2716863031 556 2736408878 557 2756059894 558 2775816666 559 2795679362 560 2815648571 561 2835724461 562 2855907624 563 2876198229 564 2896596869 565 2917103714 566 2937719359 567 2958443975 568 2979278159 569 3000222082 570 3021276344 571 3042441116 572 3063717000 573 3085104168 574 3106603224 575 3128214341 576 3149938124 577 3171774747 578 3193724818 579 3215788511 580 3237966436 581 3260258767 582 3282666117 583 3305188661 584 3327827013 585 3350581349 586 3373452285 587 3396439998 588 3419545106 589 3442767786 590 3466108659 591 3489567902 592 3513146138 593 3536843545 594 3560660748 595 3584597926 596 3608655705 597 3632834265 598 3657134235 599 3681555795 600 3706099576 601 3730765758 602 3755554975 603 3780467408 604 3805503692 605 3830664009 606 3855948996 607 3881358836 608 3906894168 609 3932555175 610 3958342499 611 3984256323 612 4010297291 613 4036465587 614 4062761857 615 4089186286 616 4115739521 617 4142421748 618 4169233617 619 4196175314 620 4223247491 621 4250450334 622 4277784498 623 4305250170 624 4332848006 625 4360578194 626 4388441392 627 4416437789 628 4444568045 629 4472832349 630 4501231364 631 4529765279 632 4558434759 633 4587239994 634 4616181651 635 4645259921 636 4674475472 637 4703828496 638 4733319664 639 4762949168 640 4792717681 641 4822625395 642 4852672986 643 4882860647 644 4913189055 645 4943658404 646 4974269373 647 5005022157 648 5035917437 649 5066955408 650 5098136754 651 5129461670 652 5160930842 653 5192544466 654 5224303230 655 5256207331 656 5288257458 657 5320453809 658 5352797076 659 5385287457 660 5417925646 661 5450711841 662 5483646739 663 5516730539 664 5549963939 665 5583347139 666 5616880839 667 5650565240 668 5684401044 669 5718388452 670 5752528169 671 5786820396 672 5821265840 673 5855864703 674 5890617694 675 5925525016 676 5960587379 677 5995804987 678 6031178553 679 6066708281 680 6102394886 681 6138238572 682 6174240057 683 6210399546 684 6246717758 685 6283194899 686 6319831690 687 6356628338 688 6393585566 689 6430703581 690 6467983109 691 6505424357 692 6543028053 693 6580794405 694 6618724143 695 6656817476 696 6695075135 697 6733497330 698 6772084795 699 6810837740 700 6849756901 701 6888842488 702 6928095240 703 6967515368 704 7007103612 705 7046860184 706 7086785826 707 7126880751 708 7167145703 709 7207580895 710 7248187074 711 7288964453 712 7329913781 713 7371035272 714 7412329677 715 7453797211 716 7495438626 717 7537254138 718 7579244502 719 7621409934 720 7663751191 721 7706268489 722 7748962588 723 7791833705 724 7834882601 725 7878109494 726 7921515147 727 7965099779 728 8008864155 729 8052808494 730 8096933564 731 8141239584 732 8185727324 733 8230397004 734 8275249396 735 8320284721 736 8365503752 737 8410906711 738 8456494374 739 8502266963 740 8548225256 741 8594369475 742 8640700401 743 8687218257 744 8733923825 745 8780817329 746 8827899553 747 8875170722 748 8922631622 749 8970282478 750 9018124079 751 9066156650 752 9114380982 753 9162797301 754 9211406400 755 9260208506 756 9309204413 757 9358394349 758 9407779111 759 9457358927 760 9507134596 761 9557106346 762 9607274979 763 9657640724 764 9708204384 765 9758966189 766 9809926944 767 9861086880 768 9912446804 769 9964006947 770 10015768119 771 10067730551 772 10119895055 773 10172261863 774 10224831789 775 10277605066 776 10330582509 777 10383764352 778 10437151413 779 10490743926 780 10544542711 781 10598548002 782 10652760622 783 10707180806 784 10761809378 785 10816646574 786 10871693220 787 10926949553 788 10982416401 789 11038094001 790 11093983184 791 11150084187 792 11206397843 793 11262924390 794 11319664663 795 11376618901 796 11433787940 797 11491172020 798 11548771980 799 11606588060 800 11664621101 801 11722871343 802 11781339630 803 11840026203 804 11898931907 805 11958056984 806 12017402281 807 12076968041 808 12136755113 809 12196763740 810 12256994774 811 12317448458 812 12378125646 813 12439026582 814 12500152122 815 12561502511 816 12623078606 817 12684880653 818 12746909512 819 12809165429 820 12871649266 821 12934361269 822 12997302303 823 13060472615 824 13123873071 825 13187503919 826 13251366027 827 13315459644 828 13379785640 829 13444344264 830 13509136389 831 13574162264 832 13639422764 833 13704918139 834 13770649266 835 13836616396 836 13902820407 837 13969261551 838 14035940709 839 14102858133 840 14170014706 841 14237410680 842 14305046941 843 14372923742 844 14441041970 845 14509401879 846 14578004358 847 14646849662 848 14715938682 849 14785271673 850 14854849529 851 14924672505 852 14994741497 853 15065056761 854 15135619195 855 15206429056 856 15277487243 857 15348794014 858 15420350271 859 15492156272 860 15564212921 861 15636520476 862 15709079844 863 15781891284 864 15854955704 865 15928273364 866 16001845174 867 16075671395 868 16149752939 869 16224090067 870 16298683694 871 16373534081 872 16448642145 873 16524008148 874 16599633009 875 16675516991 876 16751661014 877 16828065342 878 16904730898 879 16981657946 880 17058847411 881 17136299557 882 17214015312 883 17291994941 884 17370239373 885 17448748874 886 17527524375 887 17606566143 888 17685875111 889 17765451546 890 17845296384 891 17925409892 892 18005793008 893 18086446000 894 18167369808 895 18248564701 896 18330031620 897 18411770835 898 18493783290 899 18576069255 900 18658629676 901 18741464823 902 18824575645 903 18907962413 904 18991626077 905 19075566909 906 19159785861 907 19244283206 908 19329059898 909 19414116210 910 19499453099 911 19585070838 912 19670970386 913 19757152017 914 19843616692 915 19930364686 916 20017396961 917 20104713793 918 20192316147 919 20280204299 920 20368379216 921 20456841174 922 20545591143 923 20634629400 924 20723956916 925 20813573969 926 20903481532 927 20993679884 928 21084170000 929 21174952159 930 21266027339 931 21357395819 932 21449058579 933 21541015899 934 21633268761 935 21725817446 936 21818662937 937 21911805516 938 22005246169 939 22098985178 940 22193023531 941 22287361510 942 22382000106 943 22476939602 944 22572180990 945 22667724554 946 22763571288 947 22859721477 948 22956176117 949 23052935493 950 23150000604 951 23247371735 952 23345049887 953 23443035346 954 23541329115 955 23639931481 956 23738843448 957 23838065304 958 23937598056 959 24037441992 960 24137598121 961 24238066731 962 24338848834 963 24439944719 964 24541355399 965 24643081164 966 24745123029 967 24847481285 968 24950156949 969 25053150312 970 25156462394 971 25260093486 972 25364044610 973 25468316058 974 25572908854 975 25677823291 976 25783060394 977 25888620457 978 25994504508 979 26100712841 980 26207246486 981 26314105737 982 26421291627 983 26528804451 984 26636645243 985 26744814299 986 26853312655 987 26962140608 988 27071299196 989 27180788716 990 27290610209 991 27400763972 992 27511251048 993 27622071735 994 27733227078 995 27844717376 996 27956543675 997 28068706275 998 28181206225 999 28294043825 1000 28407220126