0 1 1 6 2 20 3 49 4 105 5 190 6 320 7 501 8 727 9 1026 10 1408 11 1853 12 2391 13 3026 14 3734 15 4579 16 5541 17 6620 18 7838 19 9201 20 10657 21 12328 22 14136 23 16123 24 18293 25 20658 26 23128 27 25905 28 28825 29 31994 30 35388 31 39029 32 42779 33 46942 34 51240 35 55865 36 60755 37 65946 38 71242 39 77071 40 83013 41 89368 42 96026 43 103041 44 110149 45 117924 46 125776 47 134135 48 142833 49 151946 50 161132 51 171133 52 181161 53 191798 54 202808 55 214293 56 225823 57 238330 58 250800 59 263989 60 277583 61 291714 62 305854 63 321147 64 336325 65 352340 66 368790 67 385841 68 402857 69 421216 70 439368 71 458483 72 478061 73 498306 74 518464 75 540169 76 561561 77 584050 78 607028 79 630741 80 654307 81 679638 82 704536 83 730673 84 757323 85 784778 86 812018 87 841255 88 869925 89 899984 90 930578 91 962049 92 993229 93 1026652 94 1059360 95 1093615 96 1128425 97 1164186 98 1199572 99 1237461 100 1274473 101 1313198 102 1352496 103 1392821 104 1432679 105 1475314 106 1516896 107 1560365 108 1604423 109 1649586 110 1694182 111 1741843 112 1788261 113 1836748 114 1885838 115 1936113 116 1985713 117 2038680 118 2090200 119 2143979 120 2198373 121 2254034 122 2308904 123 2367457 124 2424345 125 2483690 126 2543660 127 2604981 128 2665387 129 2729806 130 2792328 131 2857513 132 2923331 133 2990586 134 3056794 135 3127359 136 3195781 137 3267080 138 3339018 139 3412481 140 3484757 141 3561748 142 3636336 143 3714023 144 3792353 145 3872298 146 3950908 147 4034605 148 4115625 149 4199974 150 4284968 151 4371669 152 4456879 153 4547562 154 4635280 155 4726565 156 4818495 157 4912226 158 5004302 159 5102251 160 5196933 161 5295428 162 5394566 163 5495601 164 5594809 165 5700304 166 5802216 167 5908195 168 6014813 169 6123426 170 6230032 171 6343353 172 6452761 173 6566498 174 6680868 175 6797333 176 6911603 177 7033030 178 7150200 179 7271969 180 7394363 181 7518954 182 7641154 183 7770967 184 7896165 185 8026240 186 8156930 187 8289921 188 8420317 189 8558796 190 8692288 191 8830943 192 8970201 193 9111866 194 9250724 195 9398149 196 9540201 197 9687710 198 9835808 199 9986421 200 10134007 201 10290658 202 10441536 203 10598173 204 10755383 205 10915218 206 11071798 207 11237955 208 11397925 209 11563964 210 11730558 211 11899889 212 12065729 213 12241672 214 12411000 215 12586715 216 12762965 217 12942066 218 13117432 219 13303441 220 13482393 221 13668058 222 13854236 223 14043381 224 14228539 225 14424894 226 14613736 227 14809625 228 15006003 229 15205466 230 15400682 231 15607663 232 15806661 233 16013048 234 16219898 235 16429953 236 16635493 237 16853380 238 17062800 239 17279959 240 17497553 241 17718474 242 17934604 243 18163677 244 18383785 245 18611990 246 18840600 247 19072661 248 19299647 249 19540186 250 19771248 251 20010773 252 20250671 253 20494146 254 20732254 255 20984539 256 21226821 257 21477940 258 21729398 259 21984561 260 22234057 261 22498368 262 22752136 263 23015123 264 23278413 265 23545538 266 23806688 267 24083305 268 24348825 269 24623954 270 24899348 271 25178709 272 25451779 273 25740982 274 26018520 275 26306065 276 26593835 277 26885706 278 27170962 279 27473031 280 27762853 281 28063088 282 28363506 283 28668161 284 28965869 285 29281084 286 29583456 287 29896655 288 30209993 289 30527706 290 30838132 291 31166773 292 31481961 293 31808398 294 32134928 295 32465973 296 32789383 297 33131730 298 33460000 299 33799949 300 34139943 301 34484594 302 34821254 303 35177587 304 35519205 305 35872940 306 36226670 307 36585201 308 36935377 309 37305976 310 37661208 311 38029003 312 38396741 313 38769426 314 39133384 315 39518529 316 39887641 317 40269770 318 40651788 319 41038901 320 41416907 321 41816878 322 42200136 323 42596873 324 42993443 325 43395258 326 43787578 327 44202655 328 44600325 329 45011944 330 45423338 331 45840129 332 46247029 333 46677492 334 47089840 335 47516615 336 47943105 337 48375146 338 48796892 339 49243021 340 49670313 341 50112518 342 50554376 343 51001941 344 51438799 345 51900874 346 52343376 347 52801285 348 53258783 349 53722146 350 54174382 351 54652683 352 55110661 353 55584548 354 56057958 355 56537393 356 57005273 357 57500080 358 57973800 359 58463939 360 58953533 361 59449314 362 59933104 363 60444697 364 60934425 365 61441090 366 61947140 367 62459541 368 62959507 369 63488166 370 63994168 371 64517633 372 65040411 373 65569706 374 66086114 375 66632119 376 67154661 377 67695200 378 68234978 379 68781441 380 69314557 381 69878188 382 70417536 383 70975423 384 71532473 385 72096378 386 72646468 387 73228005 388 73784425 389 74359934 390 74934528 391 75516149 392 76083479 393 76683202 394 77256960 395 77850365 396 78442775 397 79042386 398 79627222 399 80245411 400 80836773 401 81448348 402 82058846 403 82676721 404 83279329 405 83916264 406 84525496 407 85155515 408 85784373 409 86420786 410 87041432 411 87697393 412 88324761 413 88973498 414 89620988 415 90276213 416 90915163 417 91590430 418 92236200 419 92903929 420 93570323 421 94244634 422 94902154 423 95597007 424 96261445 425 96948440 426 97634010 427 98327681 428 99004037 429 99718756 430 100402128 431 101108663 432 101813681 433 102526986 434 103222444 435 103957309 436 104659881 437 105386230 438 106110968 439 106844181 440 107559007 441 108314298 442 109036336 443 109782773 444 110527503 445 111280898 446 112015358 447 112791355 448 113533125 449 114299924 450 115064918 451 115838769 452 116593129 453 117390112 454 118151880 455 118939315 456 119724845 457 120519426 458 121293952 459 122112201 460 122894233 461 123702578 462 124508916 463 125324501 464 126119459 465 126959254 466 127761816 467 128591345 468 129418763 469 130255626 470 131071282 471 131932903 472 132756261 473 133607248 474 134456018 475 135314433 476 136151053 477 137034780 478 137879200 479 138751919 480 139622313 481 140502554 482 141360404 483 142266517 484 143132265 485 144026990 486 144919280 487 145821621 488 146700967 489 147629746 490 148517088 491 149434093 492 150348551 493 151273266 494 152174374 495 153126099 496 154035301 497 154974860 498 155911758 499 156859121 500 157782257 501 158757208 502 159688536 503 160650923 504 161610533 505 162580818 506 163526248 507 164524705 508 165478425 509 166463914 510 167446508 511 168439989 512 169407979 513 170430222 514 171406600 515 172415465 516 173421315 517 174438266 518 175429082 519 176475391 520 177474693 521 178507208 522 179536586 523 180577281 524 181591189 525 182661844 526 183684336 527 184740775 528 185793953 529 186858666 530 187895932 531 188991213 532 190037161 533 191117798 534 192195048 535 193284053 536 194344943 537 195465130 538 196534800 539 197639909 540 198741503 541 199855074 542 200939854 543 202085227 544 203178885 545 204308740 546 205434950 547 206573361 548 207682297 549 208853136 550 209971048 551 211125923 552 212277021 553 213440546 554 214573904 555 215770489 556 216912921 557 218093090 558 219269348 559 220458261 560 221616307 561 222838918 562 224006136 563 225211873 564 226413563 565 227628138 566 228811138 567 230060055 568 231252325 569 232483904 570 233711298 571 234951809 572 236160029 573 237435532 574 238653120 575 239910815 576 241164185 577 242430906 578 243664612 579 244966981 580 246210153 581 247494238 582 248773856 583 250067061 584 251326519 585 252656034 586 253925056 587 255235805 588 256541943 589 257861906 590 259147382 591 260504323 592 261799461 593 263137148 594 264470078 595 265817073 596 267128833 597 268513480 598 269835000 599 271199899 600 272559893 601 273934194 602 275272504 603 276685137 604 278033305 605 279425690 606 280813020 607 282214901 608 283580027 609 285020926 610 286396008 611 287816153 612 289231091 613 290660826 614 292053034 615 293522479 616 294924741 617 296372920 618 297815738 619 299273601 620 300693157 621 302191428 622 303621136 623 305097623 624 306568593 625 308054858 626 309502028 627 311029405 628 312486825 629 313991894 630 315491288 631 317006229 632 318481279 633 320038042 634 321523440 635 323057365 636 324585455 637 326129346 638 327632542 639 329218971 640 330732613 641 332295668 642 333852726 643 335425841 644 336957449 645 338573824 646 340115976 647 341708435 648 343294733 649 344897346 650 346457632 651 348104233 652 349675161 653 351297298 654 352913108 655 354545493 656 356134723 657 357811830 658 359411800 659 361063889 660 362709483 661 364371914 662 365990354 663 367698247 664 369327525 665 371009840 666 372685490 667 374378241 668 376026157 669 377765116 670 379423968 671 381136783 672 382842761 673 384566106 674 386243764 675 388014069 676 389702761 677 391446350 678 393182928 679 394937141 680 396644807 681 398446738 682 400165536 683 401940173 684 403707623 685 405492978 686 407230918 687 409064755 688 410813925 689 412619884 690 414418478 691 416235249 692 418003729 693 419869752 694 421649560 695 423487115 696 425317125 697 427165586 698 428964872 699 430863361 700 432674073 701 434543498 702 436405196 703 438285621 704 440115979 705 442047214 706 443889096 707 445790665 708 447684323 709 449596986 710 451458682 711 453422943 712 455296261 713 457230248 714 459156138 715 461101313 716 462994613 717 464992180 718 466897200 719 468863879 720 470822273 721 472800234 722 474725404 723 476756557 724 478693545 725 480693190 726 482684360 727 484695381 728 486652687 729 488717706 730 490686928 731 492719813 732 494744031 733 496788386 734 498778094 735 500877259 736 502878981 737 504945380 738 507002918 739 509080881 740 511103257 741 513236848 742 515271336 743 517371523 744 519462653 745 521574498 746 523629808 747 525798105 748 527865625 749 529999874 750 532124868 751 534270869 752 536359379 753 538562662 754 540663480 755 542832065 756 544991195 757 547171626 758 549293602 759 551532151 760 553666533 761 555869728 762 558063266 763 560278401 764 562434109 765 564708204 766 566876416 767 569114495 768 571342713 769 573592826 770 575782532 771 578092453 772 580294761 773 582567998 774 584831168 775 587116533 776 589340503 777 591686530 778 593923200 779 596231869 780 598530263 781 600851154 782 603109654 783 605492067 784 607763365 785 610107740 786 612441630 787 614798321 788 617091617 789 619510696 790 621816888 791 624197243 792 626566901 793 628959666 794 631288024 795 633744049 796 636085401 797 638502010 798 640907708 799 643336821 800 645700507 801 648193758 802 650570536 803 653023673 804 655465683 805 657931418 806 660330698 807 662861455 808 665273925 809 667763864 810 670242458 811 672745089 812 675180229 813 677748772 814 680197200 815 682724215 816 685239665 817 687779466 818 690250732 819 692857341 820 695341993 821 697906358 822 700458936 823 703036181 824 705543839 825 708188794 826 710709936 827 713311925 828 715901903 829 718516866 830 721061182 831 723744763 832 726302661 833 728942548 834 731570198 835 734223153 836 736804393 837 739526880 838 742121800 839 744799859 840 747465453 841 750156674 842 752775104 843 755536777 844 758168985 845 760885490 846 763589300 847 766319061 848 768974947 849 771776086 850 774445848 851 777201073 852 779943371 853 782711946 854 785405554 855 788246439 856 790954021 857 793748240 858 796529298 859 799336961 860 802068557 861 804949468 862 807695136 863 810528623 864 813348713 865 816195738 866 818965588 867 821886805 868 824670825 869 827543854 870 830403248 871 833289909 872 836098279 873 839060082 874 841882720 875 844795565 876 847694535 877 850621106 878 853468262 879 856470931 880 859332453 881 862285388 882 865224206 883 868190961 884 871077169 885 874120984 886 877021656 887 880014955 888 882993893 889 886001106 890 888926632 891 892011873 892 894951961 893 897985898 894 901005228 895 904053173 896 907018283 897 910145230 898 913125000 899 916199849 900 919259843 901 922348794 902 925353754 903 928522687 904 931542405 905 934658440 906 937759370 907 940889601 908 943934677 909 947145876 910 950205808 911 953363303 912 956505441 913 959677226 914 962762684 915 966016429 916 969116841 917 972316070 918 975499688 919 978713301 920 981839407 921 985135978 922 988277136 923 991518373 924 994743743 925 997999458 926 1001166478 927 1004506155 928 1007688325 929 1010971844 930 1014239238 931 1017537329 932 1020745529 933 1024128592 934 1027352040 935 1030678115 936 1033987805 937 1037328546 938 1040578192 939 1044004921 940 1047269913 941 1050638818 942 1053991076 943 1057374741 944 1060666099 945 1064136774 946 1067443576 947 1070855585 948 1074250683 949 1077677546 950 1081010882 951 1084525783 952 1087874661 953 1091330048 954 1094768258 955 1098238593 956 1101614173 957 1105173580 958 1108564800 959 1112063839 960 1115545433 961 1119059514 962 1122477604 963 1126081797 964 1129515625 965 1133058590 966 1136583840 967 1140141941 968 1143602807 969 1147252066 970 1150728768 971 1154315933 972 1157885111 973 1161487506 974 1164991414 975 1168686019 976 1172205861 977 1175837500 978 1179450878 979 1183097841 980 1186645057 981 1190385288 982 1193948536 983 1197624923 984 1201282773 985 1204974578 986 1208565368 987 1212351505 988 1215958425 989 1219679834 990 1223382428 991 1227119349 992 1230753979 993 1234586302 994 1238237160 995 1242003865 996 1245751475 997 1249533786 998 1253212522 999 1257091311 1000 1260786373