0 1 1 6 2 19 3 45 4 91 5 164 6 268 7 408 8 595 9 835 10 1127 11 1479 12 1896 13 2378 14 2945 15 3605 16 4345 17 5183 18 6127 19 7158 20 8308 21 9598 22 10997 23 12528 24 14205 25 15992 26 17936 27 20066 28 22327 29 24758 30 27382 31 30132 32 33073 33 36253 34 39587 35 43125 36 46902 37 50822 38 54971 39 59411 40 64021 41 68873 42 74017 43 79314 44 84874 45 90784 46 96881 47 103254 48 109971 49 116852 50 124034 51 131624 52 139411 53 147512 54 156016 55 164688 56 173695 57 183175 58 192863 59 202899 60 213396 61 224066 62 235109 63 246689 64 258481 65 270659 66 283363 67 296238 68 309520 69 323410 70 337517 71 352044 72 367161 73 382448 74 398180 75 414590 76 431215 77 448298 78 466042 79 483948 80 502333 81 521473 82 540827 83 560673 84 581250 85 601982 86 623231 87 645311 88 667597 89 690413 90 714037 91 737802 92 762118 93 787348 94 812777 95 838770 96 865647 97 892652 98 920246 99 948836 100 977611 101 1006988 102 1037332 103 1067784 104 1098859 105 1131019 106 1163351 107 1196319 108 1230336 109 1264442 110 1299209 111 1335149 112 1371241 113 1408007 114 1445911 115 1483878 116 1522540 117 1562470 118 1602533 119 1643304 120 1685301 121 1727336 122 1770104 123 1814234 124 1858471 125 1903454 126 1949758 127 1996068 128 2043145 129 2091685 130 2140307 131 2189709 132 2240526 133 2291318 134 2342915 135 2396075 136 2449285 137 2503313 138 2558857 139 2614338 140 2670658 141 2728648 142 2786657 143 2845518 144 2905995 145 2966372 146 3027626 147 3090656 148 3153667 149 3217568 150 3283192 151 3348672 152 3415063 153 3483343 154 3551567 155 3620715 156 3691692 157 3762482 158 3834221 159 3907961 160 3981601 161 4056203 162 4132747 163 4209054 164 4286344 165 4365754 166 4445021 167 4525284 168 4607601 169 4689632 170 4772684 171 4857974 172 4943071 173 5029202 174 5117506 175 5205468 176 5294485 177 5385865 178 5477003 179 5569209 180 5663706 181 5757806 182 5852999 183 5950679 184 6048061 185 6146549 186 6247453 187 6347898 188 6449470 189 6553660 190 6657497 191 6762474 192 6869991 193 6976988 194 7085150 195 7196060 196 7306555 197 7418228 198 7532572 199 7646328 200 7761283 201 7879123 202 7996487 203 8115063 204 8236440 205 8357162 206 8479121 207 8604101 208 8728537 209 8854223 210 8982847 211 9110742 212 9239908 213 9372238 214 9503957 215 9636960 216 9773037 217 9908312 218 10044896 219 10184786 220 10323991 221 10464518 222 10608262 223 10751124 224 10895329 225 11042989 226 11189891 227 11338149 228 11489766 229 11640422 230 11792459 231 11948099 232 12102901 233 12259097 234 12418801 235 12577458 236 12737530 237 12901360 238 13064273 239 13228614 240 13396611 241 13563476 242 13731794 243 13904024 244 14075251 245 14247944 246 14424448 247 14599728 248 14776495 249 14957335 250 15137087 251 15318339 252 15503556 253 15687458 254 15872885 255 16062545 256 16251025 257 16441043 258 16635187 259 16827918 260 17022208 261 17220898 262 17418317 263 17617308 264 17820585 265 18022352 266 18225716 267 18433646 268 18640207 269 18848378 270 19061002 271 19272012 272 19484653 273 19702033 274 19917947 275 20135505 276 20357682 277 20578142 278 20800271 279 21027311 280 21252781 281 21479933 282 21711877 283 21941994 284 22173814 285 22410724 286 22645961 287 22882914 288 23124831 289 23364812 290 23606534 291 23853524 292 24098731 293 24345692 294 24597796 295 24847848 296 25099675 297 25356955 298 25612343 299 25869519 300 26132016 301 26392346 302 26654489 303 26922269 304 27188041 305 27455639 306 27728743 307 27999558 308 28272220 309 28550710 310 28827077 311 29105304 312 29389221 313 29670728 314 29954120 315 30243530 316 30530695 317 30819758 318 31114702 319 31407108 320 31701433 321 32001973 322 32300147 323 32600253 324 32906430 325 33209942 326 33515411 327 33827291 328 34136677 329 34448033 330 34765657 331 35080482 332 35397298 333 35720728 334 36041537 335 36364350 336 36693627 337 37019972 338 37348346 339 37683536 340 38015971 341 38350448 342 38691592 343 39029664 344 39369799 345 39716959 346 40061231 347 40407579 348 40760796 349 41110802 350 41462909 351 41822249 352 42178561 353 42536987 354 42902491 355 43264638 356 43628920 357 44000650 358 44369213 359 44739924 360 45117921 361 45492416 362 45869084 363 46253414 364 46634431 365 47017634 366 47408338 367 47795388 368 48184645 369 48581785 370 48975467 371 49371369 372 49774986 373 50174798 374 50576855 375 50987015 376 51393565 377 51802373 378 52219117 379 52631898 380 53046958 381 53470348 382 53889977 383 54311898 384 54741975 385 55167932 386 55596206 387 56033036 388 56465947 389 56901188 390 57344812 391 57784152 392 58225843 393 58676323 394 59122727 395 59571495 396 60028872 397 60481802 398 60937121 399 61401461 400 61861561 401 62324063 402 62795407 403 63262134 404 63731284 405 64209694 406 64683701 407 65160144 408 65645661 409 66126392 410 66609584 411 67102274 412 67590391 413 68080982 414 68580886 415 69075828 416 69573265 417 70080445 418 70582883 419 71087829 420 71602326 421 72111686 422 72623579 423 73145459 424 73662421 425 74181929 426 74711233 427 75235218 428 75761770 429 76298560 430 76830257 431 77364534 432 77908851 433 78447668 434 78989090 435 79541000 436 80087635 437 80636888 438 81196432 439 81750288 440 82306783 441 82874023 442 83435807 443 84000243 444 84575220 445 85144322 446 85716101 447 86298881 448 86876017 449 87455843 450 88046467 451 88631022 452 89218288 453 89816818 454 90409517 455 91004940 456 91611417 457 92211632 458 92814596 459 93429086 460 94037551 461 94648778 462 95271322 463 95887404 464 96506269 465 97136929 466 97761371 467 98388609 468 99027426 469 99659582 470 100294559 471 100941599 472 101582221 473 102225677 474 102880981 475 103529418 476 104180710 477 104844340 478 105501353 479 106161234 480 106833231 481 107498156 482 108165974 483 108846404 484 109520011 485 110196524 486 110885428 487 111567048 488 112251595 489 112949035 490 113639447 491 114332799 492 115038816 493 115737338 494 116438825 495 117153485 496 117860905 497 118571303 498 119294647 499 120010278 500 120728908 501 121460998 502 122185637 503 122913288 504 123654165 505 124387112 506 125123096 507 125872826 508 126614887 509 127359998 510 128118622 511 128869092 512 129622633 513 130390213 514 131149907 515 131912685 516 132689262 517 133457462 518 134228771 519 135014411 520 135791941 521 136572593 522 137367337 523 138153474 524 138942754 525 139746664 526 140542241 527 141340974 528 142154091 529 142958372 530 143765834 531 144588224 532 145402051 533 146219072 534 147050776 535 147873408 536 148699255 537 149540335 538 150372623 539 151208139 540 152058636 541 152899826 542 153744269 543 154604249 544 155455201 545 156309419 546 157178923 547 158038878 548 158902120 549 159781210 550 160651037 551 161524164 552 162412881 553 163291808 554 164174060 555 165072470 556 165961375 557 166853618 558 167761762 559 168659868 560 169561333 561 170479273 562 171387467 563 172299033 564 173226810 565 174144302 566 175065191 567 176002871 568 176930557 569 177861653 570 178809277 571 179746362 572 180686878 573 181644508 574 182591897 575 183542730 576 184510407 577 185467292 578 186427646 579 187405436 580 188372731 581 189343508 582 190331452 583 191308344 584 192288739 585 193286899 586 194274311 587 195265239 588 196273656 589 197270762 590 198271409 591 199290149 592 200297881 593 201309167 594 202338271 595 203355798 596 204376900 597 205416430 598 206444693 599 207476544 600 208526541 601 209564696 602 210606464 603 211666994 604 212715991 605 213768614 606 214839718 607 215898708 608 216961345 609 218043085 610 219113027 611 220186629 612 221279046 613 222359078 614 223442795 615 224545955 616 225637045 617 226731833 618 227845777 619 228947058 620 230052058 621 231176848 622 232289297 623 233405478 624 234541155 625 235663892 626 236790386 627 237937016 628 239071027 629 240208808 630 241366432 631 242510832 632 243659023 633 244827703 634 245983487 635 247143075 636 248322852 637 249489122 638 250659221 639 251850161 640 253027921 641 254209523 642 255411667 643 256600014 644 257792224 645 259005634 646 260205581 647 261409404 648 262634121 649 263844752 650 265059284 651 266295374 652 267517711 653 268743962 654 269991466 655 271224588 656 272461645 657 273720625 658 274965563 659 276214449 660 277484946 661 278740766 662 280000559 663 281282639 664 282550381 665 283822109 666 285115813 667 286394538 668 287677270 669 288982660 670 290273417 671 291568194 672 292885311 673 294187148 674 295493030 675 296821940 676 298135915 677 299453948 678 300794692 679 302119848 680 303449083 681 304801723 682 306139127 683 307480623 684 308845200 685 310193882 686 311546681 687 312923261 688 314284297 689 315649463 690 317038087 691 318410502 692 319787068 693 321187798 694 322572677 695 323961720 696 325374597 697 326770952 698 328171496 699 329596586 700 331005511 701 332418638 702 333855982 703 335276484 704 336701209 705 338150869 706 339584051 707 341021469 708 342483486 709 343928342 710 345377459 711 346851899 712 348309541 713 349771457 714 351258361 715 352727778 716 354201490 717 355700920 718 357183233 719 358669854 720 360181851 721 361676036 722 363174554 723 364699184 724 366206371 725 367717904 726 369255208 727 370774368 728 372297895 729 373847935 730 375380207 731 376916859 732 378479676 733 380024018 734 381572765 735 383148425 736 384705985 737 386267963 738 387856507 739 389426238 740 391000408 741 392601898 742 394184957 743 395772468 744 397386945 745 398982272 746 400582076 747 402209606 748 403818367 749 405431618 750 407072242 751 408693372 752 410319013 753 411972793 754 413607467 755 415246665 756 416913642 757 418560782 758 420212471 759 421892711 760 423553501 761 425218853 762 426912397 763 428585754 764 430263694 765 431970604 766 433657721 767 435349434 768 437069751 769 438769532 770 440473934 771 442207724 772 443921371 773 445639652 774 447386956 775 449113368 776 450844435 777 452605315 778 454345703 779 456090759 780 457865256 781 459618506 782 461376449 783 463164629 784 464931961 785 466703999 786 468505903 787 470286198 788 472071220 789 473886910 790 475681397 791 477480624 792 479310141 793 481117688 794 482930000 795 484773410 796 486595255 797 488421878 798 490279222 799 492114228 800 493954033 801 495825373 802 497674787 803 499529013 804 501414390 805 503277062 806 505144571 807 507044051 808 508921237 809 510803273 810 512716897 811 514607442 812 516502858 813 518430688 814 520335857 815 522245910 816 524187987 817 526106612 818 528030146 819 529986536 820 531919891 821 533858168 822 535828912 823 537775824 824 539727679 825 541712839 826 543674591 827 545641299 828 547640916 829 549616322 830 551596709 831 553610849 832 555601201 833 557596547 834 559625251 835 561629358 836 563638480 837 565681810 838 567700973 839 569725164 840 571783161 841 573816176 842 575854244 843 577926974 844 579975151 845 582028394 846 584115898 847 586178028 848 588245245 849 590347585 850 592424987 851 594507489 852 596624706 853 598716158 854 600812735 855 602944895 856 605051725 857 607163693 858 609310837 859 611431818 860 613557958 861 615720148 862 617856617 863 619998258 864 622175535 865 624326252 866 626482166 867 628674596 868 630840907 869 633012428 870 635220052 871 637400712 872 639586603 873 641809483 874 644005847 875 646207455 876 648445632 877 650656442 878 652872521 879 655126061 880 657352681 881 659584583 882 661853527 883 664094694 884 666341164 885 668625574 886 670882661 887 673145064 888 675444981 889 677716712 890 679993784 891 682309274 892 684597031 893 686890142 894 689221246 895 691523748 896 693831625 897 696178405 898 698497043 899 700821069 900 703183566 901 705517046 902 707855939 903 710234219 904 712583941 905 714939089 906 717333193 907 719697858 908 722067970 909 724477960 910 726858977 911 729245454 912 731671371 913 734067428 914 736468970 915 738910880 916 741323395 917 743741408 918 746199352 919 748627008 920 751060183 921 753534223 922 755978447 923 758428203 924 760918380 925 763377842 926 765842861 927 768349241 928 770825377 929 773307083 930 775829707 931 778321182 932 780818248 933 783357178 934 785865437 935 788379300 936 790934577 937 793458272 938 795987596 939 798559286 940 801099871 941 803646098 942 806234242 943 808790364 944 811352149 945 813956809 946 816529931 947 819108729 948 821729946 949 824318702 950 826913159 951 829550999 952 832156861 953 834768437 954 837422941 955 840044538 956 842671870 957 845343100 958 847981913 959 850626474 960 853314471 961 855969116 962 858629534 963 861334364 964 864006331 965 866684084 966 869405788 967 872093688 968 874787395 969 877526035 970 880231367 971 882942519 972 885698136 973 888419498 974 891146705 975 893919365 976 896658265 977 899403023 978 902192767 979 904947798 980 907708708 981 910515598 982 913288277 983 916066848 984 918890925 985 921679832 986 924474656 987 927315986 988 930122647 989 932935238 990 935793862 991 938616852 992 941445793 993 944321773 994 947162627 995 950009445 996 952902822 997 955760102 998 958623371 999 961534211 1000 964409461