0 0 1 1 2 7 3 33 4 106 5 265 6 561 7 1057 8 1828 9 2961 10 4555 11 6721 12 9582 13 13273 14 17941 15 23745 16 30856 17 39457 18 49743 19 61921 20 76210 21 92841 22 112057 23 134113 24 159276 25 187825 26 220051 27 256257 28 296758 29 341881 30 391965 31 447361 32 508432 33 575553 34 649111 35 729505 36 817146 37 912457 38 1015873 39 1127841 40 1248820 41 1379281 42 1519707 43 1670593 44 1832446 45 2005785 46 2191141 47 2389057 48 2600088 49 2824801 50 3063775 51 3317601 52 3586882 53 3872233 54 4174281 55 4493665 56 4831036 57 5187057 58 5562403 59 5957761 60 6373830 61 6811321 62 7270957 63 7753473 64 8259616 65 8790145 66 9345831 67 9927457 68 10535818 69 11171721 70 11835985 71 12529441 72 13252932 73 14007313 74 14793451 75 15612225 76 16464526 77 17351257 78 18273333 79 19231681 80 20227240 81 21260961 82 22333807 83 23446753 84 24600786 85 25796905 86 27036121 87 28319457 88 29647948 89 31022641 90 32444595 91 33914881 92 35434582 93 37004793 94 38626621 95 40301185 96 42029616 97 43813057 98 45652663 99 47549601 100 49505050 101 51520201 102 53596257 103 55734433 104 57935956 105 60202065 106 62534011 107 64933057 108 67400478 109 69937561 110 72545605 111 75225921 112 77979832 113 80808673 114 83713791 115 86696545 116 89758306 117 92900457 118 96124393 119 99431521 120 102823260 121 106301041 122 109866307 123 113520513 124 117265126 125 121101625 126 125031501 127 129056257 128 133177408 129 137396481 130 141715015 131 146134561 132 150656682 133 155282953 134 160014961 135 164854305 136 169802596 137 174861457 138 180032523 139 185317441 140 190717870 141 196235481 142 201871957 143 207628993 144 213508296 145 219511585 146 225640591 147 231897057 148 238282738 149 244799401 150 251448825 151 258232801 152 265153132 153 272211633 154 279410131 155 286750465 156 294234486 157 301864057 158 309641053 159 317567361 160 325644880 161 333875521 162 342261207 163 350803873 164 359505466 165 368367945 166 377393281 167 386583457 168 395940468 169 405466321 170 415163035 171 425032641 172 435077182 173 445298713 174 455699301 175 466281025 176 477045976 177 487996257 178 499133983 179 510461281 180 521980290 181 533693161 182 545602057 183 557709153 184 570016636 185 582526705 186 595241571 187 608163457 188 621294598 189 634637241 190 648193645 191 661966081 192 675956832 193 690168193 194 704602471 195 719261985 196 734149066 197 749266057 198 764615313 199 780199201 200 796020100 201 812080401 202 828382507 203 844928833 204 861721806 205 878763865 206 896057461 207 913605057 208 931409128 209 949472161 210 967796655 211 986385121 212 1005240082 213 1024364073 214 1043759641 215 1063429345 216 1083375756 217 1103601457 218 1124109043 219 1144901121 220 1165980310 221 1187349241 222 1209010557 223 1230966913 224 1253220976 225 1275775425 226 1298632951 227 1321796257 228 1345268058 229 1369051081 230 1393148065 231 1417561761 232 1442294932 233 1467350353 234 1492730811 235 1518439105 236 1544478046 237 1570850457 238 1597559173 239 1624607041 240 1651996920 241 1679731681 242 1707814207 243 1736247393 244 1765034146 245 1794177385 246 1823680041 247 1853545057 248 1883775388 249 1914374001 250 1945343875 251 1976688001 252 2008409382 253 2040511033 254 2072995981 255 2105867265 256 2139127936 257 2172781057 258 2206829703 259 2241276961 260 2276125930 261 2311379721 262 2347041457 263 2383114273 264 2419601316 265 2456505745 266 2493830731 267 2531579457 268 2569755118 269 2608360921 270 2647400085 271 2686875841 272 2726791432 273 2767150113 274 2807955151 275 2849209825 276 2890917426 277 2933081257 278 2975704633 279 3018790881 280 3062343340 281 3106365361 282 3150860307 283 3195831553 284 3241282486 285 3287216505 286 3333637021 287 3380547457 288 3427951248 289 3475851841 290 3524252695 291 3573157281 292 3622569082 293 3672491593 294 3722928321 295 3773882785 296 3825358516 297 3877359057 298 3929887963 299 3982948801 300 4036545150 301 4090680601 302 4145358757 303 4200583233 304 4256357656 305 4312685665 306 4369570911 307 4427017057 308 4485027778 309 4543606761 310 4602757705 311 4662484321 312 4722790332 313 4783679473 314 4845155491 315 4907222145 316 4969883206 317 5033142457 318 5097003693 319 5161470721 320 5226547360 321 5292237441 322 5358544807 323 5425473313 324 5493026826 325 5561209225 326 5630024401 327 5699476257 328 5769568708 329 5840305681 330 5911691115 331 5983728961 332 6056423182 333 6129777753 334 6203796661 335 6278483905 336 6353843496 337 6429879457 338 6506595823 339 6583996641 340 6662085970 341 6740867881 342 6820346457 343 6900525793 344 6981409996 345 7063003185 346 7145309491 347 7228333057 348 7312078038 349 7396548601 350 7481748925 351 7567683201 352 7654355632 353 7741770433 354 7829931831 355 7918844065 356 8008511386 357 8098938057 358 8190128353 359 8282086561 360 8374816980 361 8468323921 362 8562611707 363 8657684673 364 8753547166 365 8850203545 366 8947658181 367 9045915457 368 9144979768 369 9244855521 370 9345547135 371 9447059041 372 9549395682 373 9652561513 374 9756561001 375 9861398625 376 9967078876 377 10073606257 378 10180985283 379 10289220481 380 10398316390 381 10508277561 382 10619108557 383 10730813953 384 10843398336 385 10956866305 386 11071222471 387 11186471457 388 11302617898 389 11419666441 390 11537621745 391 11656488481 392 11776271332 393 11896974993 394 12018604171 395 12141163585 396 12264657966 397 12389092057 398 12514470613 399 12640798401 400 12768080200 401 12896320801 402 13025525007 403 13155697633 404 13286843506 405 13418967465 406 13552074361 407 13686169057 408 13821256428 409 13957341361 410 14094428755 411 14232523521 412 14371630582 413 14511754873 414 14652901341 415 14795074945 416 14938280656 417 15082523457 418 15227808343 419 15374140321 420 15521524410 421 15669965641 422 15819469057 423 15970039713 424 16121682676 425 16274403025 426 16428205851 427 16583096257 428 16739079358 429 16896160281 430 17054344165 431 17213636161 432 17374041432 433 17535565153 434 17698212511 435 17861988705 436 18026898946 437 18192948457 438 18360142473 439 18528486241 440 18697985020 441 18868644081 442 19040468707 443 19213464193 444 19387635846 445 19562988985 446 19739528941 447 19917261057 448 20096190688 449 20276323201 450 20457663975 451 20640218401 452 20823991882 453 21008989833 454 21195217681 455 21382680865 456 21571384836 457 21761335057 458 21952537003 459 22144996161 460 22338718030 461 22533708121 462 22729971957 463 22927515073 464 23126343016 465 23326461345 466 23527875631 467 23730591457 468 23934614418 469 24139950121 470 24346604185 471 24554582241 472 24763889932 473 24974532913 474 25186516851 475 25399847425 476 25614530326 477 25830571257 478 26047975933 479 26266750081 480 26486899440 481 26708429761 482 26931346807 483 27155656353 484 27381364186 485 27608476105 486 27836997921 487 28066935457 488 28298294548 489 28531081041 490 28765300795 491 29000959681 492 29238063582 493 29476618393 494 29716630021 495 29958104385 496 30201047416 497 30445465057 498 30691363263 499 30938748001 500 31187625250 501 31438001001 502 31689881257 503 31943272033 504 32198179356 505 32454609265 506 32712567811 507 32972061057 508 33233095078 509 33495675961 510 33759809805 511 34025502721 512 34292760832 513 34561590273 514 34831997191 515 35103987745 516 35377568106 517 35652744457 518 35929522993 519 36207909921 520 36487911460 521 36769533841 522 37052783307 523 37337666113 524 37624188526 525 37912356825 526 38202177301 527 38493656257 528 38786800008 529 39081614881 530 39378107215 531 39676283361 532 39976149682 533 40277712553 534 40580978361 535 40885953505 536 41192644396 537 41501057457 538 41811199123 539 42123075841 540 42436694070 541 42752060281 542 43069180957 543 43388062593 544 43708711696 545 44031134785 546 44355338391 547 44681329057 548 45009113338 549 45338697801 550 45670089025 551 46003293601 552 46338318132 553 46675169233 554 47013853531 555 47354377665 556 47696748286 557 48040972057 558 48387055653 559 48735005761 560 49084829080 561 49436532321 562 49790122207 563 50145605473 564 50502988866 565 50862279145 566 51223483081 567 51586607457 568 51951659068 569 52318644721 570 52687571235 571 53058445441 572 53431274182 573 53806064313 574 54182822701 575 54561556225 576 54942271776 577 55324976257 578 55709676583 579 56096379681 580 56485092490 581 56875821961 582 57268575057 583 57663358753 584 58060180036 585 58459045905 586 58859963371 587 59262939457 588 59667981198 589 60075095641 590 60484289845 591 60895570881 592 61308945832 593 61724421793 594 62142005871 595 62561705185 596 62983526866 597 63407478057 598 63833565913 599 64261797601 600 64692180300 601 65124721201 602 65559427507 603 65996306433 604 66435365206 605 66876611065 606 67320051261 607 67765693057 608 68213543728 609 68663610561 610 69115900855 611 69570421921 612 70027181082 613 70486185673 614 70947443041 615 71410960545 616 71876745556 617 72344805457 618 72815147643 619 73287779521 620 73762708510 621 74239942041 622 74719487557 623 75201352513 624 75685544376 625 76172070625 626 76660938751 627 77152156257 628 77645730658 629 78141669481 630 78639980265 631 79140670561 632 79643747932 633 80149219953 634 80657094211 635 81167378305 636 81680079846 637 82195206457 638 82712765773 639 83232765441 640 83755213120 641 84280116481 642 84807483207 643 85337320993 644 85869637546 645 86404440585 646 86941737841 647 87481537057 648 88023845988 649 88568672401 650 89116024075 651 89665908801 652 90218334382 653 90773308633 654 91330839381 655 91890934465 656 92453601736 657 93018849057 658 93586684303 659 94157115361 660 94730150130 661 95305796521 662 95884062457 663 96464955873 664 97048484716 665 97634656945 666 98223480531 667 98814963457 668 99409113718 669 100005939321 670 100605448285 671 101207648641 672 101812548432 673 102420155713 674 103030478551 675 103643525025 676 104259303226 677 104877821257 678 105499087233 679 106123109281 680 106749895540 681 107379454161 682 108011793307 683 108646921153 684 109284845886 685 109925575705 686 110569118821 687 111215483457 688 111864677848 689 112516710241 690 113171588895 691 113829322081 692 114489918082 693 115153385193 694 115819731721 695 116488965985 696 117161096316 697 117836131057 698 118514078563 699 119194947201 700 119878745350 701 120565481401 702 121255163757 703 121947800833 704 122643401056 705 123341972865 706 124043524711 707 124748065057 708 125455602378 709 126166145161 710 126879701905 711 127596281121 712 128315891332 713 129038541073 714 129764238891 715 130492993345 716 131224813006 717 131959706457 718 132697682293 719 133438749121 720 134182915560 721 134930190241 722 135680581807 723 136434098913 724 137190750226 725 137950544425 726 138713490201 727 139479596257 728 140248871308 729 141021324081 730 141796963315 731 142575797761 732 143357836182 733 144143087353 734 144931560061 735 145723263105 736 146518205296 737 147316395457 738 148117842423 739 148922555041 740 149730542170 741 150541812681 742 151356375457 743 152174239393 744 152995413396 745 153819906385 746 154647727291 747 155478885057 748 156313388638 749 157151247001 750 157992469125 751 158837064001 752 159685040632 753 160536408033 754 161391175231 755 162249351265 756 163110945186 757 163975966057 758 164844422953 759 165716324961 760 166591681180 761 167470500721 762 168352792707 763 169238566273 764 170127830566 765 171020594745 766 171916867981 767 172816659457 768 173719978368 769 174626833921 770 175537235335 771 176451191841 772 177368712682 773 178289807113 774 179214484401 775 180142753825 776 181074624676 777 182010106257 778 182949207883 779 183891938881 780 184838308590 781 185788326361 782 186742001557 783 187699343553 784 188660361736 785 189625065505 786 190593464271 787 191565567457 788 192541384498 789 193520924841 790 194504197945 791 195491213281 792 196481980332 793 197476508593 794 198474807571 795 199476886785 796 200482755766 797 201492424057 798 202505901213 799 203523196801 800 204544320400 801 205569281601 802 206598090007 803 207630755233 804 208667286906 805 209707694665 806 210751988161 807 211800177057 808 212852271028 809 213908279761 810 214968212955 811 216032080321 812 217099891582 813 218171656473 814 219247384741 815 220327086145 816 221410770456 817 222498447457 818 223590126943 819 224685818721 820 225785532610 821 226889278441 822 227997066057 823 229108905313 824 230224806076 825 231344778225 826 232468831651 827 233596976257 828 234729221958 829 235865578681 830 237006056365 831 238150664961 832 239299414432 833 240452314753 834 241609375911 835 242770607905 836 243936020746 837 245105624457 838 246279429073 839 247457444641 840 248639681220 841 249826148881 842 251016857707 843 252211817793 844 253411039246 845 254614532185 846 255822306741 847 257034373057 848 258250741288 849 259471421601 850 260696424175 851 261925759201 852 263159436882 853 264397467433 854 265639861081 855 266886628065 856 268137778636 857 269393323057 858 270653271603 859 271917634561 860 273186422230 861 274459644921 862 275737312957 863 277019436673 864 278306026416 865 279597092545 866 280892645431 867 282192695457 868 283497253018 869 284806328521 870 286119932385 871 287438075041 872 288760766932 873 290088018513 874 291419840251 875 292756242625 876 294097236126 877 295442831257 878 296793038533 879 298147868481 880 299507331640 881 300871438561 882 302240199807 883 303613625953 884 304991727586 885 306374515305 886 307761999721 887 309154191457 888 310551101148 889 311952739441 890 313359116995 891 314770244481 892 316186132582 893 317606791993 894 319032233421 895 320462467585 896 321897505216 897 323337357057 898 324782033863 899 326231546401 900 327685905450 901 329145121801 902 330609206257 903 332078169633 904 333552022756 905 335030776465 906 336514441611 907 338003029057 908 339496549678 909 340995014361 910 342498434005 911 344006819521 912 345520181832 913 347038531873 914 348561880591 915 350090238945 916 351623617906 917 353162028457 918 354705481593 919 356253988321 920 357807559660 921 359366206641 922 360929940307 923 362498771713 924 364072711926 925 365651772025 926 367235963101 927 368825296257 928 370419782608 929 372019433281 930 373624259415 931 375234272161 932 376849482682 933 378469902153 934 380095541761 935 381726412705 936 383362526196 937 385003893457 938 386650525723 939 388302434241 940 389959630270 941 391622125081 942 393289929957 943 394963056193 944 396641515096 945 398325317985 946 400014476191 947 401709001057 948 403408903938 949 405114196201 950 406824889225 951 408540994401 952 410262523132 953 411989486833 954 413721896931 955 415459764865 956 417203102086 957 418951920057 958 420706230253 959 422466044161 960 424231373280 961 426002229121 962 427778623207 963 429560567073 964 431348072266 965 433141150345 966 434939812881 967 436744071457 968 438553937668 969 440369423121 970 442190539435 971 444017298241 972 445849711182 973 447687789913 974 449531546101 975 451380991425 976 453236137576 977 455096996257 978 456963579183 979 458835898081 980 460713964690 981 462597790761 982 464487388057 983 466382768353 984 468283943436 985 470190925105 986 472103725171 987 474022355457 988 475946827798 989 477877154041 990 479813346045 991 481755415681 992 483703374832 993 485657235393 994 487617009271 995 489582708385 996 491554344666 997 493531930057 998 495515476513 999 497504996001 1000 499500500500