0 1 1 1 2 4 3 10 4 25 5 49 6 103 7 184 8 331 9 554 10 911 11 1424 12 2204 13 3278 14 4817 15 6896 16 9746 17 13487 18 18480 19 24882 20 33192 21 43683 22 56994 23 73512 24 94131 25 119340 26 150300 27 187732 28 233065 29 287248 30 352153 31 428944 32 519949 33 626737 34 752095 35 897994 36 1067924 37 1264241 38 1491155 39 1751672 40 2050724 41 2391962 42 2781368 43 3223220 44 3724568 45 4290666 46 4929636 47 5647704 48 6454485 49 7357155 50 8366844 51 9492126 52 10745649 53 12137379 54 13682011 55 15390880 56 17280751 57 19364884 58 21662119 59 24187636 60 26962996 61 30005272 62 33338773 63 36983144 64 40965446 65 45307889 66 50041064 67 55189718 68 60788000 69 66864005 70 73455446 71 80593760 72 88321143 73 96672342 74 105694068 75 115425336 76 125917377 77 137213466 78 149370429 79 162435768 80 176471937 81 191531779 82 207683383 83 224984926 84 243511372 85 263326195 86 284511271 87 307136656 88 331291144 89 357051364 90 384514448 91 413763560 92 444904208 93 478027556 94 513247496 95 550663184 96 590398505 97 632560565 98 677283284 99 724683378 100 774904809 101 828073893 102 884346447 103 943858344 104 1006777299 105 1073250606 106 1143457887 107 1217557848 108 1295744044 109 1378186546 110 1465092889 111 1556646592 112 1653069178 113 1754557603 114 1861349632 115 1973655610 116 2091729592 117 2215797623 118 2346130058 119 2482968632 120 2626602491 121 2777289008 122 2935336172 123 3101019548 124 3274665977 125 3456569204 126 3647077665 127 3846503232 128 4055215989 129 4273548741 130 4501893231 131 4740603186 132 4990095012 133 5250743301 134 5522989179 135 5807231176 136 6103935148 137 6413523550 138 6736490248 139 7073281564 140 7424419432 141 7790377390 142 8171705452 143 8568904360 144 8982555773 145 9413187575 146 9861413132 147 10327791110 148 10812966593 149 11317529015 150 11842159043 151 12387476816 152 12954198647 153 13542979320 154 14154570807 155 14789662524 156 15449046276 157 16133446044 158 16843693533 159 17580551544 160 18344891694 161 19137515589 162 19959339256 163 20811203038 164 21694067440 165 22608816121 166 23556454078 167 24537908272 168 25554233023 169 26606398522 170 27695508484 171 28822581248 172 29988769937 173 31195141022 174 32442902213 175 33733168040 176 35067200873 177 36446168567 178 37871388167 179 39344080838 180 40865623836 181 42437291559 182 44060521551 183 45736647072 184 47467165968 185 49253470344 186 51097124256 187 52999578576 188 54962463648 189 56987295112 190 59075769616 191 61229467552 192 63450158161 193 65739486505 194 68099294500 195 70531298266 196 73037412409 197 75619424089 198 78279327287 199 81018980120 200 83840456027 201 86745690866 202 89736837551 203 92815909664 204 95985146684 205 99246639830 206 102602715233 207 106055548944 208 109607553762 209 113260990551 210 117018366288 211 120882026562 212 124854572616 213 128938442379 214 133136331378 215 137450769864 216 141884555587 217 146440311028 218 151120936252 219 155929154020 220 160867966729 221 165940197400 222 171148959145 223 176497175152 224 181988069341 225 187624673561 226 193410322559 227 199348156826 228 205441630772 229 211693993433 230 218108818979 231 224689473944 232 231439652276 233 238362837986 234 245462854104 235 252743302020 236 260208133944 237 267861078066 238 275706215796 239 283747402104 240 291988857381 241 300434563275 242 309088879260 243 317955923566 244 327040194769 245 336345947659 246 345877830187 247 355640233600 248 365637955327 249 375875533468 250 386357914951 251 397089784708 252 408076249940 253 419322142304 254 430832729381 255 442613000456 256 454668383510 257 467004025433 258 479625525896 259 492538189286 260 505747787072 261 519259792557 262 533080149030 263 547214498688 264 561668968455 265 576449369310 266 591562011924 267 607012888008 268 622808492001 269 638954996322 270 655459091533 271 672327130648 272 689566000465 273 707182247083 274 725182953559 275 743574859054 276 762365255788 277 781561075867 278 801169820791 279 821198628656 280 841655210264 281 862546909676 282 883881660464 283 905667012536 284 927911122352 285 950621759276 286 973807302680 287 997475741360 288 1021635691641 289 1046295361629 290 1071463604724 291 1097148862530 292 1123360225545 293 1150106368845 294 1177396634655 295 1205239931400 296 1233645853155 297 1262623556470 298 1292182887295 299 1322333250280 300 1353084758476 301 1384447064506 302 1416430548649 303 1449045126880 304 1482301446730 305 1516209687499 306 1550780779808 307 1586025166154 308 1621954060376 309 1658578184159 310 1695909034586 311 1733957612504 312 1772735714699 313 1812254621048 314 1852526428172 315 1893562711596 316 1935375867801 317 1977977767932 318 2021381125425 319 2065598106912 320 2110641742917 321 2156524512813 322 2203259764239 323 2250860289282 324 2299339770436 325 2348711312365 326 2398988932555 327 2450186066152 328 2502317065660 329 2555395696678 330 2609436665128 331 2664454066924 332 2720462961544 333 2777477793782 334 2835513976700 335 2894586303944 336 2954710561229 337 3015901890911 338 3078176451500 339 3141549753302 340 3206038327649 341 3271658052767 342 3338425852563 343 3406357973040 344 3475471730823 345 3545783759616 346 3617311768791 347 3690072779724 348 3764084914980 349 3839365583460 350 3915933321069 351 3993805944856 352 4073002404094 353 4153540923949 354 4235440888216 355 4318720930030 356 4403400867856 357 4489499764129 358 4577037872014 359 4666034683216 360 4756510907471 361 4848486465602 362 4941982524068 363 5037019454864 364 5133618881201 365 5231801626214 366 5331589792469 367 5433004654088 368 5536068793145 369 5640803957535 370 5747233208871 371 5855378768790 372 5965264201788 373 6076912203087 374 6190346840223 375 6305591305536 376 6422670169632 377 6541607121936 378 6662427260224 379 6785154770848 380 6909815278912 381 7036433491984 382 7165035562528 383 7295646719296 384 7428293666977 385 7563002155345 386 7699799441476 387 7838711821226 388 7979767104089 389 8122992131969 390 8268415292423 391 8416063973240 392 8565967140203 393 8718152752826 394 8872650355151 395 9029488478384 396 9188697271260 397 9350305836510 398 9514344927729 399 9680844245808 400 9849835149234 401 10021347937023 402 10195414599792 403 10372066034514 404 10551334864104 405 10733252610931 406 10917852530242 407 11105166769768 408 11295229245139 409 11488072729276 410 11683731798364 411 11882239878772 412 12083632207273 413 12287942863648 414 12495207774137 415 12705461671760 416 12918741172397 417 13135081691393 418 13354520534303 419 13577093798762 420 13802839509716 421 14031794446913 422 14263997354867 423 14499485725368 424 14738299022532 425 14980475450154 426 15226055222520 427 15475077255252 428 15727582512984 429 15983610653946 430 16243203393156 431 16506401131416 432 16773246365557 433 17043780238771 434 17318046029884 435 17596085656126 436 17877943178353 437 18163661287795 438 18453284859643 439 18746857358944 440 19044424475407 441 19346030480420 442 19651721878247 443 19961543746580 444 20275543437428 445 20593766834600 446 20916262138037 447 21243076071080 448 21574257681638 449 21909854532545 450 22249916553768 451 22594492147446 452 22943632125792 453 23297385764565 454 23655804758262 455 24018939256224 456 24386841870231 457 24759563623014 458 25137158043828 459 25519677064024 460 25907175130369 461 26299705082794 462 26697322321501 463 27100080594808 464 27508036256545 465 27921243999571 466 28339761131383 467 28763643289342 468 29192948771468 469 29627734159427 470 30068058741959 471 30513980082128 472 30965558459432 473 31422852418292 474 31885923266768 475 32354830530440 476 32829636546128 477 33310401858612 478 33797189833512 479 34290062034768 480 34789082895561 481 35294314998789 482 35805823845396 483 36323673076242 484 36847929260073 485 37378657095669 486 37915924259311 487 38459796507496 488 39010342624243 489 39567629463742 490 40131726917791 491 40702702938232 492 41280628565356 493 41865572848450 494 42457607976505 495 43056804137216 496 43663234668314 497 44276970895859 498 44898087348032 499 45526656489050 500 46162754037752 501 46806453638471 502 47457832200746 503 48116964548984 504 48783928826139 505 49458801036480 506 50141660556588 507 50832584613564 508 51531653817657 509 52238946618756 510 52954544904513 511 53678528347392 512 54410980112661 513 55151981139349 514 55901615870383 515 56659966511314 516 57427118827492 517 58203156290773 518 58988165989147 519 59782232705800 520 60585444851404 521 61397888520430 522 62219653492040 523 63050827171772 524 63891500707496 525 64741762861886 526 65601706151564 527 66471420696296 528 67351000428317 529 68240536824263 530 69140125232204 531 70049858532774 532 70969833489921 533 71900144388231 534 72840889455459 535 73792164379920 536 74754068853399 537 75726700016136 538 76710159023991 539 77704544469084 540 78709959020356 541 79726502721580 542 80754279755005 543 81793391665336 544 82843944148174 545 83906040249109 546 84979787227192 547 86065289628670 548 87162656276272 549 88271993267273 550 89393410988126 551 90527017087088 552 91672923565535 553 92831239622474 554 94002078874436 555 95185552122656 556 96381774598865 557 97590858706478 558 98812921344741 559 100048076519016 560 101296442796297 561 102558135836487 562 103833275874375 563 105121980224358 564 106424370842460 565 107740566697335 566 109070691466479 567 110414865826528 568 111773215176496 569 113145861900952 570 114532933175008 571 115934553090928 572 117350850600160 573 118781951557528 574 120227986690864 575 121689083617504 576 123165374897393 577 124656989910137 578 126164063048036 579 127686725508986 580 129225113517689 581 130779360090281 582 132349603340759 583 133935978103256 584 135538624381307 585 137157678884226 586 138793283505135 587 140445576828480 588 142114702695036 589 143800801564134 590 145504019224449 591 147224498068560 592 148962385833090 593 150717826843815 594 152490970844560 595 154281964094050 596 156090958343560 597 157918101844315 598 159763548355090 599 161627448119560 600 163509956964451 601 165411227125636 602 167331416498044 603 169270679370500 604 171229175706185 605 173207061846824 606 175204499885513 607 177221648216624 608 179258671063421 609 181315728934889 610 183392988184511 611 185490611435834 612 187608767235444 613 189747620321193 614 191907341433027 615 194088097486296 616 196290061414356 617 198513402310002 618 200758295364120 619 203024911846692 620 205313429206392 621 207624020954818 622 209956866798484 623 212312142490552 624 214690030060741 625 217090707503515 626 219514359172060 627 221961165367822 628 224431312767505 629 226924983979483 630 229442368070603 631 231983649955904 632 234549021092639 633 237138668769452 634 239752786834055 635 242391564948644 636 245055199419284 637 247743882281456 638 250457812299845 639 253197183951432 640 255962198459574 641 258753052742697 642 261569950552008 643 264413091247110 644 267282681107328 645 270178922002941 646 273102022741446 647 276052187703744 648 279029628295975 649 282034551409390 650 285067171049044 651 288127696687336 652 291216344928289 653 294333327825394 654 297478864653421 655 300653170046680 656 303856465950961 657 307088969653499 658 310350905771159 659 313642494244046 660 316963962433196 661 320315532931307 662 323697435843863 663 327109896489584 664 330553147718456 665 334027417575164 666 337532941728624 667 341069950949208 668 344638683725040 669 348239373626940 670 351872261962296 671 355537585102320 672 359235587249433 673 362966507574957 674 366730593176628 675 370528086101986 676 374359236344137 677 378224288826781 678 382123496515519 679 386057107209928 680 390025376848387 681 394028556183814 682 398066904127423 683 402140674385416 684 406250128920332 685 410395524391370 686 414577125812681 687 418795192875296 688 423049993645034 689 427341790844699 690 431670855671648 691 436037453880170 692 440441859799448 693 444884342295471 694 449365178829306 695 453884641378584 696 458443010617515 697 463040561635080 698 467677578318924 699 472354338950988 700 477071130632409 701 481828234838028 702 486625941965137 703 491464536681184 704 496344312679909 705 501265557904381 706 506228569344847 707 511233638219938 708 516281064900484 709 521371143880381 710 526504178911339 711 531680467846952 712 536900317819868 713 542164030043318 714 547471915116392 715 552824277611660 716 558221431594952 717 563663685084038 718 569151355611548 719 574684754640392 720 580264203256941 721 585890016368943 722 591562518616812 723 597282028440438 724 603048874034337 725 608863377370479 726 614725870285875 727 620636678284272 728 626596136845479 729 632604575093776 730 638662332151831 731 644769740764396 732 650927143786852 733 657134877584116 734 663393288744589 735 669702717343576 736 676063513702558 737 682476021607165 738 688940595203288 739 695457581986574 740 702027339927632 741 708650220323825 742 715326584970542 743 722056788966800 744 728841198025583 745 735680171047250 746 742574077662692 747 749523280666800 748 756528153608433 749 763589063176950 750 770706386933493 751 777880495461576 752 785111770334937 753 792400586125935 754 799747328420967 755 807152375781174 756 814616117901436 757 822138937331359 758 829721227874623 759 837363376165504 760 845065780116544 761 852828830446624 762 860652929274496 763 868538471403328 764 876485863158400 765 884495503524896 766 892567803034688 767 900703164854912 768 908902003822913 769 917164727287457 770 925491754391684 771 933883496765258 772 942340377857177 773 950862813577937 774 959451231782823 775 968106052662840 776 976827708479883 777 985616623806282 778 994473235310607 779 1003397971946448 780 1012391274891036 781 1021453577478894 782 1030585325396241 783 1039786956460912 784 1049058920868178 785 1058401660919119 786 1067815631421616 787 1077301279159666 788 1086859063554088 789 1096489435975747 790 1106192860458466 791 1115969792959912 792 1125820702232051 793 1135746048819020 794 1145746306191260 795 1155821939584916 796 1165973427188969 797 1176201238931504 798 1186505857826777 799 1196887758494480 800 1207347428774477 801 1217885348085201 802 1228502009092191 803 1239197896012554 804 1249973506445844 805 1260829329407505 806 1271765867431443 807 1282783614440184 808 1293883077902052 809 1305064756646586 810 1316329163186488 811 1327676801257972 812 1339108188418456 813 1350623833421194 814 1362224258868388 815 1373909978530264 816 1385681520165397 817 1397539402560643 818 1409484158631292 819 1421516312292830 820 1433636401617329 821 1445844955648835 822 1458142517729435 823 1470529622031392 824 1483006817167151 825 1495574642550836 826 1508233652065319 827 1520984390366516 828 1533827416722612 829 1546763281030968 830 1559792547945429 831 1572915772720104 832 1586133525394566 833 1599446366579601 834 1612854871817064 835 1626359607074070 836 1639961153395104 837 1653660082220581 838 1667456980097686 839 1681352423940064 840 1695347005915831 841 1709441308411510 842 1723635929216500 843 1737931456308856 844 1752328493099329 845 1766827633157434 846 1781429485635197 847 1796134649693240 848 1810943740225217 849 1825857362103203 850 1840876135962551 851 1856000672386718 852 1871231597874380 853 1886569528720019 854 1902015097285991 855 1917568925699856 856 1933231652187720 857 1949003904710148 858 1964886327480336 859 1980879554291496 860 1996984235344272 861 2013201010388292 862 2029530535611720 863 2045973456720528 864 2062530436015465 865 2079202125158485 866 2095989192563284 867 2112892295973298 868 2129912109915241 869 2147049298213957 870 2164304541635983 871 2181678510087208 872 2199171890574355 873 2216785359211598 874 2234519609245919 875 2252375322999704 876 2270353200088748 877 2288453929043282 878 2306678215848281 879 2325026755370816 880 2343500259965114 881 2362099430835011 882 2380824986834304 883 2399677635503226 884 2418658102195512 885 2437767100918551 886 2457005363526090 887 2476373610492600 888 2495872580303931 889 2515502999901264 890 2535265614402924 891 2555161157349340 892 2575190380491385 893 2595354023968660 894 2615652846298465 895 2636087594219200 896 2656659033014965 897 2677367916157285 898 2698215015697135 899 2719201091839090 900 2740326923536676 901 2761593277727141 902 2783000940266939 903 2804550684962120 904 2826243304572140 905 2848079579771774 906 2870060310360968 907 2892186283882844 908 2914458307178216 909 2936877174796494 910 2959443700619436 911 2982158686202664 912 3005022952608189 913 3028037308397463 914 3051202581813132 915 3074519588562246 916 3097989164068161 917 3121612131183447 918 3145389332653315 919 3169321598475472 920 3193409778717367 921 3217654710663448 922 3242057251703479 923 3266618246408572 924 3291338559633796 925 3316219043236540 926 3341260569537565 927 3366463997823992 928 3391830207882350 929 3417360066429413 930 3443054460862328 931 3468914265327134 932 3494940374831984 933 3521133671097497 934 3547495056742910 935 3574025421063344 936 3600725674435839 937 3627596713729626 938 3654639457079940 939 3681854809077312 940 3709243695615249 941 3736807029005502 942 3764545743048453 943 3792460757776680 944 3820553014897833 945 3848823442314391 946 3877272989641351 947 3905902592651014 948 3934713209016220 949 3963705782378695 950 3992881278469519 951 4022240648950816 952 4051784867611984 953 4081514894135464 954 4111431710521376 955 4141536284472080 956 4171829606198816 957 4202312651576744 958 4232986419028304 959 4263851892601376 960 4294910079083921 961 4326161970696137 962 4357608582591908 963 4389250915318554 964 4421089992395961 965 4453126822698489 966 4485362438268279 967 4517797856306328 968 4550434117377435 969 4583272247165970 970 4616313294759471 971 4649558294325600 972 4683008303632828 973 4716664365331702 974 4750527545872033 975 4784598896545936 976 4818879492484642 977 4853370393621751 978 4888072683930064 979 4922987431984258 980 4958115730599112 981 4993458657151019 982 5029017313296818 983 5064792785214536 984 5100786183565187 985 5136998603328020 986 5173431164168636 987 5210084970030116 988 5246961149582729 989 5284060815733304 990 5321385106320873 991 5358935143215600 992 5396712073425693 993 5434717027949241 994 5472951162963711 995 5511415618595034 996 5550111560356020 997 5589040137500025 998 5628202524875619 999 5667599881030168 1000 5707233390148084