0 0 1 1 2 29 3 132 4 358 5 755 6 1371 7 2254 8 3452 9 5013 10 6985 11 9416 12 12354 13 15847 14 19943 15 24690 16 30136 17 36329 18 43317 19 51148 20 59870 21 69531 22 80179 23 91862 24 104628 25 118525 26 133601 27 149904 28 167482 29 186383 30 206655 31 228346 32 251504 33 276177 34 302413 35 330260 36 359766 37 390979 38 423947 39 458718 40 495340 41 533861 42 574329 43 616792 44 661298 45 707895 46 756631 47 807554 48 860712 49 916153 50 973925 51 1034076 52 1096654 53 1161707 54 1229283 55 1299430 56 1372196 57 1447629 58 1525777 59 1606688 60 1690410 61 1776991 62 1866479 63 1958922 64 2054368 65 2152865 66 2254461 67 2359204 68 2467142 69 2578323 70 2692795 71 2810606 72 2931804 73 3056437 74 3184553 75 3316200 76 3451426 77 3590279 78 3732807 79 3879058 80 4029080 81 4182921 82 4340629 83 4502252 84 4667838 85 4837435 86 5011091 87 5188854 88 5370772 89 5556893 90 5747265 91 5941936 92 6140954 93 6344367 94 6552223 95 6764570 96 6981456 97 7202929 98 7429037 99 7659828 100 7895350 101 8135651 102 8380779 103 8630782 104 8885708 105 9145605 106 9410521 107 9680504 108 9955602 109 10235863 110 10521335 111 10812066 112 11108104 113 11409497 114 11716293 115 12028540 116 12346286 117 12669579 118 12998467 119 13332998 120 13673220 121 14019181 122 14370929 123 14728512 124 15091978 125 15461375 126 15836751 127 16218154 128 16605632 129 16999233 130 17399005 131 17804996 132 18217254 133 18635827 134 19060763 135 19492110 136 19929916 137 20374229 138 20825097 139 21282568 140 21746690 141 22217511 142 22695079 143 23179442 144 23670648 145 24168745 146 24673781 147 25185804 148 25704862 149 26231003 150 26764275 151 27304726 152 27852404 153 28407357 154 28969633 155 29539280 156 30116346 157 30700879 158 31292927 159 31892538 160 32499760 161 33114641 162 33737229 163 34367572 164 35005718 165 35651715 166 36305611 167 36967454 168 37637292 169 38315173 170 39001145 171 39695256 172 40397554 173 41108087 174 41826903 175 42554050 176 43289576 177 44033529 178 44785957 179 45546908 180 46316430 181 47094571 182 47881379 183 48676902 184 49481188 185 50294285 186 51116241 187 51947104 188 52786922 189 53635743 190 54493615 191 55360586 192 56236704 193 57122017 194 58016573 195 58920420 196 59833606 197 60756179 198 61688187 199 62629678 200 63580700 201 64541301 202 65511529 203 66491432 204 67481058 205 68480455 206 69489671 207 70508754 208 71537752 209 72576713 210 73625685 211 74684716 212 75753854 213 76833147 214 77922643 215 79022390 216 80132436 217 81252829 218 82383617 219 83524848 220 84676570 221 85838831 222 87011679 223 88195162 224 89389328 225 90594225 226 91809901 227 93036404 228 94273782 229 95522083 230 96781355 231 98051646 232 99333004 233 100625477 234 101929113 235 103243960 236 104570066 237 105907479 238 107256247 239 108616418 240 109988040 241 111371161 242 112765829 243 114172092 244 115589998 245 117019595 246 118460931 247 119914054 248 121379012 249 122855853 250 124344625 251 125845376 252 127358154 253 128883007 254 130419983 255 131969130 256 133530496 257 135104129 258 136690077 259 138288388 260 139899110 261 141522291 262 143157979 263 144806222 264 146467068 265 148140565 266 149826761 267 151525704 268 153237442 269 154962023 270 156699495 271 158449906 272 160213304 273 161989737 274 163779253 275 165581900 276 167397726 277 169226779 278 171069107 279 172924758 280 174793780 281 176676221 282 178572129 283 180481552 284 182404538 285 184341135 286 186291391 287 188255354 288 190233072 289 192224593 290 194229965 291 196249236 292 198282454 293 200329667 294 202390923 295 204466270 296 206555756 297 208659429 298 210777337 299 212909528 300 215056050 301 217216951 302 219392279 303 221582082 304 223786408 305 226005305 306 228238821 307 230487004 308 232749902 309 235027563 310 237320035 311 239627366 312 241949604 313 244286797 314 246638993 315 249006240 316 251388586 317 253786079 318 256198767 319 258626698 320 261069920 321 263528481 322 266002429 323 268491812 324 270996678 325 273517075 326 276053051 327 278604654 328 281171932 329 283754933 330 286353705 331 288968296 332 291598754 333 294245127 334 296907463 335 299585810 336 302280216 337 304990729 338 307717397 339 310460268 340 313219390 341 315994811 342 318786579 343 321594742 344 324419348 345 327260445 346 330118081 347 332992304 348 335883162 349 338790703 350 341714975 351 344656026 352 347613904 353 350588657 354 353580333 355 356588980 356 359614646 357 362657379 358 365717227 359 368794238 360 371888460 361 374999941 362 378128729 363 381274872 364 384438418 365 387619415 366 390817911 367 394033954 368 397267592 369 400518873 370 403787845 371 407074556 372 410379054 373 413701387 374 417041603 375 420399750 376 423775876 377 427170029 378 430582257 379 434012608 380 437461130 381 440927871 382 444412879 383 447916202 384 451437888 385 454977985 386 458536541 387 462113604 388 465709222 389 469323443 390 472956315 391 476607886 392 480278204 393 483967317 394 487675273 395 491402120 396 495147906 397 498912679 398 502696487 399 506499378 400 510321400 401 514162601 402 518023029 403 521902732 404 525801758 405 529720155 406 533657971 407 537615254 408 541592052 409 545588413 410 549604385 411 553640016 412 557695354 413 561770447 414 565865343 415 569980090 416 574114736 417 578269329 418 582443917 419 586638548 420 590853270 421 595088131 422 599343179 423 603618462 424 607914028 425 612229925 426 616566201 427 620922904 428 625300082 429 629697783 430 634116055 431 638554946 432 643014504 433 647494777 434 651995813 435 656517660 436 661060366 437 665623979 438 670208547 439 674814118 440 679440740 441 684088461 442 688757329 443 693447392 444 698158698 445 702891295 446 707645231 447 712420554 448 717217312 449 722035553 450 726875325 451 731736676 452 736619654 453 741524307 454 746450683 455 751398830 456 756368796 457 761360629 458 766374377 459 771410088 460 776467810 461 781547591 462 786649479 463 791773522 464 796919768 465 802088265 466 807279061 467 812492204 468 817727742 469 822985723 470 828266195 471 833569206 472 838894804 473 844243037 474 849613953 475 855007600 476 860424026 477 865863279 478 871325407 479 876810458 480 882318480 481 887849521 482 893403629 483 898980852 484 904581238 485 910204835 486 915851691 487 921521854 488 927215372 489 932932293 490 938672665 491 944436536 492 950223954 493 956034967 494 961869623 495 967727970 496 973610056 497 979515929 498 985445637 499 991399228 500 997376750 501 1003378251 502 1009403779 503 1015453382 504 1021527108 505 1027625005 506 1033747121 507 1039893504 508 1046064202 509 1052259263 510 1058478735 511 1064722666 512 1070991104 513 1077284097 514 1083601693 515 1089943940 516 1096310886 517 1102702579 518 1109119067 519 1115560398 520 1122026620 521 1128517781 522 1135033929 523 1141575112 524 1148141378 525 1154732775 526 1161349351 527 1167991154 528 1174658232 529 1181350633 530 1188068405 531 1194811596 532 1201580254 533 1208374427 534 1215194163 535 1222039510 536 1228910516 537 1235807229 538 1242729697 539 1249677968 540 1256652090 541 1263652111 542 1270678079 543 1277730042 544 1284808048 545 1291912145 546 1299042381 547 1306198804 548 1313381462 549 1320590403 550 1327825675 551 1335087326 552 1342375404 553 1349689957 554 1357031033 555 1364398680 556 1371792946 557 1379213879 558 1386661527 559 1394135938 560 1401637160 561 1409165241 562 1416720229 563 1424302172 564 1431911118 565 1439547115 566 1447210211 567 1454900454 568 1462617892 569 1470362573 570 1478134545 571 1485933856 572 1493760554 573 1501614687 574 1509496303 575 1517405450 576 1525342176 577 1533306529 578 1541298557 579 1549318308 580 1557365830 581 1565441171 582 1573544379 583 1581675502 584 1589834588 585 1598021685 586 1606236841 587 1614480104 588 1622751522 589 1631051143 590 1639379015 591 1647735186 592 1656119704 593 1664532617 594 1672973973 595 1681443820 596 1689942206 597 1698469179 598 1707024787 599 1715609078 600 1724222100 601 1732863901 602 1741534529 603 1750234032 604 1758962458 605 1767719855 606 1776506271 607 1785321754 608 1794166352 609 1803040113 610 1811943085 611 1820875316 612 1829836854 613 1838827747 614 1847848043 615 1856897790 616 1865977036 617 1875085829 618 1884224217 619 1893392248 620 1902589970 621 1911817431 622 1921074679 623 1930361762 624 1939678728 625 1949025625 626 1958402501 627 1967809404 628 1977246382 629 1986713483 630 1996210755 631 2005738246 632 2015296004 633 2024884077 634 2034502513 635 2044151360 636 2053830666 637 2063540479 638 2073280847 639 2083051818 640 2092853440 641 2102685761 642 2112548829 643 2122442692 644 2132367398 645 2142322995 646 2152309531 647 2162327054 648 2172375612 649 2182455253 650 2192566025 651 2202707976 652 2212881154 653 2223085607 654 2233321383 655 2243588530 656 2253887096 657 2264217129 658 2274578677 659 2284971788 660 2295396510 661 2305852891 662 2316340979 663 2326860822 664 2337412468 665 2347995965 666 2358611361 667 2369258704 668 2379938042 669 2390649423 670 2401392895 671 2412168506 672 2422976304 673 2433816337 674 2444688653 675 2455593300 676 2466530326 677 2477499779 678 2488501707 679 2499536158 680 2510603180 681 2521702821 682 2532835129 683 2544000152 684 2555197938 685 2566428535 686 2577691991 687 2588988354 688 2600317672 689 2611679993 690 2623075365 691 2634503836 692 2645965454 693 2657460267 694 2668988323 695 2680549670 696 2692144356 697 2703772429 698 2715433937 699 2727128928 700 2738857450 701 2750619551 702 2762415279 703 2774244682 704 2786107808 705 2798004705 706 2809935421 707 2821900004 708 2833898502 709 2845930963 710 2857997435 711 2870097966 712 2882232604 713 2894401397 714 2906604393 715 2918841640 716 2931113186 717 2943419079 718 2955759367 719 2968134098 720 2980543320 721 2992987081 722 3005465429 723 3017978412 724 3030526078 725 3043108475 726 3055725651 727 3068377654 728 3081064532 729 3093786333 730 3106543105 731 3119334896 732 3132161754 733 3145023727 734 3157920863 735 3170853210 736 3183820816 737 3196823729 738 3209861997 739 3222935668 740 3236044790 741 3249189411 742 3262369579 743 3275585342 744 3288836748 745 3302123845 746 3315446681 747 3328805304 748 3342199762 749 3355630103 750 3369096375 751 3382598626 752 3396136904 753 3409711257 754 3423321733 755 3436968380 756 3450651246 757 3464370379 758 3478125827 759 3491917638 760 3505745860 761 3519610541 762 3533511729 763 3547449472 764 3561423818 765 3575434815 766 3589482511 767 3603566954 768 3617688192 769 3631846273 770 3646041245 771 3660273156 772 3674542054 773 3688847987 774 3703191003 775 3717571150 776 3731988476 777 3746443029 778 3760934857 779 3775464008 780 3790030530 781 3804634471 782 3819275879 783 3833954802 784 3848671288 785 3863425385 786 3878217141 787 3893046604 788 3907913822 789 3922818843 790 3937761715 791 3952742486 792 3967761204 793 3982817917 794 3997912673 795 4013045520 796 4028216506 797 4043425679 798 4058673087 799 4073958778 800 4089282800 801 4104645201 802 4120046029 803 4135485332 804 4150963158 805 4166479555 806 4182034571 807 4197628254 808 4213260652 809 4228931813 810 4244641785 811 4260390616 812 4276178354 813 4292005047 814 4307870743 815 4323775490 816 4339719336 817 4355702329 818 4371724517 819 4387785948 820 4403886670 821 4420026731 822 4436206179 823 4452425062 824 4468683428 825 4484981325 826 4501318801 827 4517695904 828 4534112682 829 4550569183 830 4567065455 831 4583601546 832 4600177504 833 4616793377 834 4633449213 835 4650145060 836 4666880966 837 4683656979 838 4700473147 839 4717329518 840 4734226140 841 4751163061 842 4768140329 843 4785157992 844 4802216098 845 4819314695 846 4836453831 847 4853633554 848 4870853912 849 4888114953 850 4905416725 851 4922759276 852 4940142654 853 4957566907 854 4975032083 855 4992538230 856 5010085396 857 5027673629 858 5045302977 859 5062973488 860 5080685210 861 5098438191 862 5116232479 863 5134068122 864 5151945168 865 5169863665 866 5187823661 867 5205825204 868 5223868342 869 5241953123 870 5260079595 871 5278247806 872 5296457804 873 5314709637 874 5333003353 875 5351339000 876 5369716626 877 5388136279 878 5406598007 879 5425101858 880 5443647880 881 5462236121 882 5480866629 883 5499539452 884 5518254638 885 5537012235 886 5555812291 887 5574654854 888 5593539972 889 5612467693 890 5631438065 891 5650451136 892 5669506954 893 5688605567 894 5707747023 895 5726931370 896 5746158656 897 5765428929 898 5784742237 899 5804098628 900 5823498150 901 5842940851 902 5862426779 903 5881955982 904 5901528508 905 5921144405 906 5940803721 907 5960506504 908 5980252802 909 6000042663 910 6019876135 911 6039753266 912 6059674104 913 6079638697 914 6099647093 915 6119699340 916 6139795486 917 6159935579 918 6180119667 919 6200347798 920 6220620020 921 6240936381 922 6261296929 923 6281701712 924 6302150778 925 6322644175 926 6343181951 927 6363764154 928 6384390832 929 6405062033 930 6425777805 931 6446538196 932 6467343254 933 6488193027 934 6509087563 935 6530026910 936 6551011116 937 6572040229 938 6593114297 939 6614233368 940 6635397490 941 6656606711 942 6677861079 943 6699160642 944 6720505448 945 6741895545 946 6763330981 947 6784811804 948 6806338062 949 6827909803 950 6849527075 951 6871189926 952 6892898404 953 6914652557 954 6936452433 955 6958298080 956 6980189546 957 7002126879 958 7024110127 959 7046139338 960 7068214560 961 7090335841 962 7112503229 963 7134716772 964 7156976518 965 7179282515 966 7201634811 967 7224033454 968 7246478492 969 7268969973 970 7291507945 971 7314092456 972 7336723554 973 7359401287 974 7382125703 975 7404896850 976 7427714776 977 7450579529 978 7473491157 979 7496449708 980 7519455230 981 7542507771 982 7565607379 983 7588754102 984 7611947988 985 7635189085 986 7658477441 987 7681813104 988 7705196122 989 7728626543 990 7752104415 991 7775629786 992 7799202704 993 7822823217 994 7846491373 995 7870207220 996 7893970806 997 7917782179 998 7941641387 999 7965548478 1000 7989503500