1 1 2 1 3 3 4 9 5 23 6 54 7 120 8 249 9 478 10 864 11 1495 12 2484 13 3969 14 6136 15 9234 16 13561 17 19464 18 27378 19 37845 20 51488 21 69012 22 91260 23 119239 24 154078 25 197026 26 249535 27 313290 28 390144 29 482120 30 591519 31 720954 32 873264 33 1051513 34 1259130 35 1499950 36 1778097 37 2097984 38 2464489 39 2883000 40 3359266 41 3899397 42 4510080 43 5198628 44 5972795 45 6840777 46 7811469 47 8894521 48 10100113 49 11438953 50 12922585 51 14563449 52 16374609 53 18369755 54 20563560 55 22971744 56 25610757 57 28497778 58 31651128 59 35090341 60 38835792 61 42908697 62 47331586 63 52128378 64 57323953 65 62944152 66 69016314 67 75569355 68 82633280 69 90239184 70 98419854 71 107209855 72 116644978 73 126762238 74 137600551 75 149200824 76 161605332 77 174857720 78 189003753 79 204091410 80 220170192 81 237291121 82 255507570 83 274875364 84 295452009 85 317296692 86 340471195 87 365040000 88 391069438 89 418627689 90 447785784 91 478617714 92 511199495 93 545609169 94 581927895 95 620240065 96 660632281 97 703193353 98 748015489 99 795194415 100 844828257 101 897017543 102 951866490 103 1009483128 104 1069978089 105 1133464606 106 1200059904 107 1269885331 108 1343065044 109 1419726009 110 1499999500 111 1584021234 112 1671929953 113 1763867424 114 1859980050 115 1960419009 116 2065338728 117 2174896884 118 2289256128 119 2408584231 120 2533052446 121 2662835506 122 2798113471 123 2939071878 124 3085899984 125 3238790768 126 3397942899 127 3563560890 128 3735853224 129 3915032353 130 4101316794 131 4294931290 132 4496104809 133 4705070544 134 4922068141 135 5147343864 136 5381148466 137 5623737189 138 5875372128 139 6136322400 140 6406861883 141 6687269217 142 6977830305 143 7278838489 144 7590592153 145 7913394721 146 8247557305 147 8593398885 148 8951243769 149 9321421595 150 9704270124 151 10100135424 152 10509369189 153 10932328738 154 11369379960 155 11820897505 156 12287261952 157 12768859809 158 13266086614 159 13779347130 160 14309052361 161 14855619552 162 15419475450 163 16001056503 164 16600805720 165 17219172672 166 17856616914 167 18513608191 168 19190623138 169 19888145278 170 20606668615 171 21346697844 172 22108744884 173 22893328880 174 23700979965 175 24532239474 176 25387656312 177 26267786953 178 27173199378 179 28104473296 180 29062196337 181 30046964052 182 31059384031 183 32100076128 184 33169668478 185 34268797497 186 35398112184 187 36558274350 188 37749954455 189 38973831609 190 40230598059 191 41520959425 192 42845630353 193 44205334513 194 45600809281 195 47032805979 196 48502085337 197 50009417495 198 51555586878 199 53141392440 200 54767642937 201 56435156926 202 58144767840 203 59897324239 204 61693684884 205 63534718737 206 65421310240 207 67354359570 208 69334777513 209 71363485464 210 73441420914 211 75569537709 212 77748800720 213 79980185844 214 82264685700 215 84603309895 216 86997079486 217 89447026978 218 91954202239 219 94519672770 220 97144517952 221 99829829048 222 102576715335 223 105386304378 224 108259736064 225 111198162601 226 114202754874 227 117274702726 228 120415208769 229 123625488384 230 126906776305 231 130260326904 232 133687407778 233 137189299749 234 140767303680 235 144422740764 236 148156945883 237 151971267609 238 155867075253 239 159845759161 240 163908723841 241 168057387961 242 172293191641 243 176617596753 244 181032079809 245 185538131963 246 190137266544 247 194831019360 248 199620941349 249 204508598578 250 209495580024 251 214583497885 252 219773979984 253 225068669769 254 230469234346 255 235977364794 256 241594768321 257 247323168264 258 253164312378 259 259119973155 260 265191939728 261 271382017872 262 277692038550 263 284123858239 264 290679350578 265 297360406366 266 304168942375 267 311106901680 268 318176245044 269 325378950920 270 332717024529 271 340192498194 272 347807422464 273 355563866113 274 363463925490 275 371509724860 276 379703407257 277 388047134484 278 396543096739 279 405193512960 280 414000621406 281 422966679657 282 432093974520 283 441384822378 284 450841559495 285 460466542017 286 470262156159 287 480230818561 288 490374966313 289 500697056953 290 511199578945 291 521885052039 292 532756017009 293 543815035655 294 555064701570 295 566507640504 296 578146499817 297 589983948478 298 602022688128 299 614265453451 300 626715001332 301 639374110857 302 652245594676 303 665332299378 304 678637094353 305 692162871792 306 705912558354 307 719889115545 308 734095528280 309 748534804884 310 763209989064 311 778124160295 312 793280422078 313 808681901938 314 824331763711 315 840233207934 316 856389459792 317 872803769120 318 889479423003 319 906419746170 320 923628088632 321 941107825681 322 958862370810 323 976895176114 324 995209719609 325 1013809505232 326 1032698076085 327 1051879014840 328 1071355930738 329 1091132459589 330 1111212277344 331 1131599100504 332 1152296672795 333 1173308765169 334 1194639189705 335 1216291800025 336 1238270477641 337 1260579131953 338 1283221714489 339 1306202219325 340 1329524669097 341 1353193115003 342 1377211651380 343 1401584416128 344 1426315576389 345 1451409328546 346 1476869913144 347 1502701615321 348 1528908750144 349 1555495662609 350 1582466742910 351 1609826426874 352 1637579180953 353 1665729502224 354 1694281934010 355 1723241066319 356 1752611520488 357 1782397949184 358 1812605052378 359 1843237577791 360 1874300305186 361 1905798046366 362 1937735661511 363 1970118059628 364 2002950182484 365 2036237004608 366 2069983549989 367 2104194892530 368 2138876139624 369 2174032432153 370 2209668961554 371 2245790970280 372 2282403735009 373 2319512566644 374 2357122827751 375 2395239933024 376 2433869332126 377 2473016509689 378 2512687003128 379 2552886403110 380 2593620336023 381 2634894463977 382 2676714502995 383 2719086223489 384 2762015432353 385 2805507972961 386 2849569743745 387 2894206698675 388 2939424828969 389 2985230163095 390 3031628785734 391 3078626838264 392 3126230500089 393 3174445988638 394 3223279578720 395 3272737603015 396 3322826433012 397 3373552479009 398 3424922209864 399 3476942153490 400 3529618877401 401 3582958988712 402 3636969154290 403 3691656101253 404 3747026597120 405 3803087449812 406 3859845528204 407 3917307762631 408 3975481124638 409 4034372626978 410 4093989344575 411 4154338415034 412 4215427017984 413 4277262375080 414 4339851771375 415 4403202555834 416 4467322120272 417 4532217899353 418 4597897392378 419 4664368163806 420 4731637821777 421 4799714018112 422 4868604470521 423 4938316963128 424 5008859324578 425 5080239428037 426 5152465213824 427 5225544689940 428 5299485909755 429 5374296972009 430 5449986043869 431 5526561361465 432 5604031207153 433 5682403909513 434 5761687866841 435 5841891547689 436 5923023467697 437 6005092189595 438 6088106347128 439 6172074645600 440 6257005838277 441 6342908726386 442 6429792183480 443 6517665155989 444 6606536639184 445 6696415677177 446 6787311387730 447 6879232962810 448 6972189644113 449 7066190723064 450 7161245566074 451 7257363615099 452 7354554362720 453 7452827352144 454 7552192202910 455 7652658611455 456 7754236325746 457 7856935145278 458 7960764947239 459 8065735687080 460 8171857372692 461 8279140064408 462 8387593901625 463 8497229103378 464 8608055942064 465 8720084743441 466 8833325913714 467 8947789940116 468 9063487364169 469 9180428781684 470 9298624870315 471 9418086390144 472 9538824156478 473 9660849039849 474 9784171994040 475 9908804056674 476 10034756321543 477 10162039938609 478 10290666142503 479 10420646253121 480 10551991647481 481 10684713759721 482 10818824110081 483 10954334305503 484 11091256011009 485 11229600949703 486 11369380932234 487 11510607857400 488 11653293683049 489 11797450426078 490 11943090192384 491 12090225177475 492 12238867636884 493 12389029886169 494 12540724331356 495 12693963469554 496 12848759858881 497 13005126118464 498 13163074959378 499 13322619185265 500 13483771661768 501 13646545316532 502 13810953170640 503 13977008339239 504 14144724000478 505 14314113395506 506 14485189860415 507 14657966826870 508 14832457790544 509 15008676311120 510 15186636044739 511 15366350744634 512 15547834229064 513 15731100381313 514 15916163182650 515 16103036712970 516 16291735118217 517 16482272610384 518 16674663500989 519 16868922201720 520 17065063191346 521 17263101015717 522 17463050321760 523 17664925858128 524 17868742441595 525 18074514957057 526 18282258392049 527 18491987837401 528 18703718453113 529 18917465468353 530 19133244216505 531 19351070135829 532 19570958734809 533 19792925592155 534 20016986392380 535 20243156926464 536 20471453056677 537 20701890716578 538 20934485947128 539 21169254897361 540 21406213788672 541 21645378914817 542 21886766678566 543 22130393592378 544 22376276242153 545 22624431287232 546 22874875497594 547 23127625754535 548 23382699013880 549 23640112305984 550 23899882773474 551 24162027671935 552 24426564332578 553 24693510162238 554 24962882681671 555 25234699526244 556 25508978408052 557 25785737115920 558 26064993554253 559 26346765743730 560 26631071782872 561 26917929848041 562 27207358232850 563 27499375348864 564 27793999686609 565 28091249815572 566 28391144424175 567 28693702320480 568 28998942392638 569 29306883608889 570 29617545058104 571 29930945950494 572 30247105577495 573 30566043311769 574 30887778648315 575 31212331205185 576 31539720682801 577 31869966863953 578 32203089655489 579 32539109089035 580 32878045279737 581 33219918426263 582 33564748853070 583 33912557011128 584 34263363436089 585 34617188748286 586 34974053695584 587 35333979154111 588 35696986085844 589 36063095538609 590 36432328689520 591 36804706845714 592 37180251401353 593 37558983837624 594 37940925766770 595 38326098932829 596 38714525168048 597 39106226392884 598 39501224660628 599 39899542158151 600 40301201161726 601 40706224037026 602 41114633284351 603 41526451539378 604 41941701528384 605 42360406068248 606 42782588112279 607 43208270750970 608 43637477166624 609 44070230633353 610 44506554563514 611 44946472508470 612 45390008112609 613 45837185113344 614 46288027388161 615 46742558955384 616 47200803927586 617 47662786511589 618 48128531056128 619 48598062052620 620 49071404087963 621 49548581844537 622 50029620148485 623 50514543970489 624 51003378377953 625 51496148535001 626 51992879751385 627 52493597483265 628 52998327284769 629 53507094807995 630 54019925852544 631 54536846366304 632 55057882396389 633 55583060089138 634 56112405740280 635 56645945795725 636 57183706801872 637 57725715405609 638 58271998405114 639 58822582750650 640 59377495494241 641 59936763789672 642 60500414943930 643 61068476418003 644 61640975775920 645 62217940684752 646 62799398966694 647 63385378599871 648 63975907666738 649 64571014354078 650 65170727005735 651 65775074123424 652 66384084314484 653 66997786291880 654 67616208927585 655 68239381253394 656 68867332408032 657 69500091637153 658 70137688347378 659 70780152107116 660 71427512593017 661 72079799589972 662 72737043045811 663 73399273072128 664 74066519890078 665 74738813830377 666 75416185388664 667 76098665226330 668 76786284115655 669 77479072939809 670 78177062748879 671 78880284760705 672 79588770305353 673 80302550825113 674 81021657931201 675 81746123404599 676 82475979139857 677 83211257145095 678 83951989599378 679 84698208853560 680 85449947373417 681 86207237739646 682 86970112705920 683 87738605199739 684 88512748264884 685 89292575061417 686 90078118924420 687 90869413364850 688 91666492011313 689 92469388610064 690 93278137084434 691 94092771535689 692 94913326184120 693 95739835369044 694 96572333608920 695 97410855602215 696 98255436167806 697 99106110244978 698 99962912954239 699 100825879598190 700 101695045601232 701 102570446509568 702 103452118052715 703 104340096144378 704 105234416821464 705 106135116244081 706 107042230757754 707 107955796894306 708 108875851310169 709 109802430786384 710 110735572291525 711 111675312982584 712 112621690142578 713 113574741180549 714 114534503695200 715 115501015475784 716 116474314439003 717 117454438629009 718 118441426281753 719 119435315825881 720 120436145818921 721 121443954947281 722 122458782091321 723 123480666326253 724 124509646857609 725 125545763021243 726 126589054349124 727 127639560570240 728 128697321545349 729 129762377266978 730 130834767925944 731 131914533912265 732 133001715749184 733 134096354093169 734 135198489801166 735 136308163931514 736 137425417677241 737 138550292366064 738 139682829528378 739 140823070898175 740 141971058345608 741 143126833876992 742 144290439703530 743 145461918242239 744 146641312047778 745 147828663812446 746 149024016435655 747 150227413024860 748 151438896826644 749 152658511226720 750 153886299820149 751 155122306412274 752 156366574949064 753 157619149517113 754 158880074414610 755 160149394152280 756 161427153382977 757 162713396901684 758 164008169717239 759 165311517053280 760 166623484277086 761 167944116899577 762 169273460647800 763 170611561465878 764 171958465443095 765 173314218813897 766 174678868031139 767 176052459767041 768 177435040840513 769 178826658217153 770 180227359083265 771 181637190846819 772 183056201064009 773 184484437439255 774 185921947899990 775 187368780597624 776 188824983833337 777 190290606058078 778 191765695948128 779 193250302406071 780 194744474485812 781 196248261392577 782 197761712559256 783 199284877647378 784 200817806471353 785 202360548998472 786 203913155426034 787 205475676182325 788 207048161850080 789 208630663166484 790 210223231101084 791 211825916856775 792 213438771792478 793 215061847423138 794 216695195498431 795 218338868003754 796 219992917082112 797 221657395034120 798 223332354397503 799 225017847948090 800 226713928620912 801 228420649510201 802 230138063949690 803 231866225513614 804 233605187937009 805 235355005115712 806 237115731187465 807 238887420532920 808 240670127695138 809 242463907379589 810 244268814536064 811 246084904359684 812 247912232209595 813 249750853608969 814 251600824327725 815 253462200383545 816 255335037959761 817 257219393405353 818 259115323318489 819 261022884547545 820 262942134108177 821 264873129183323 822 266815927207560 823 268770585868128 824 270737163021189 825 272715716691826 826 274706305159224 827 276708986957701 828 278723820792144 829 280750865538009 830 282790180327330 831 284841824549754 832 286905857767153 833 288982339713624 834 291071330382330 835 293172890026539 836 295287079073408 837 297413958123984 838 299553588040878 839 301706029949311 840 303871345150066 841 306049595119486 842 308240841597991 843 310445146591128 844 312662572281684 845 314893181029688 846 317137035461769 847 319394198472210 848 321664733134224 849 323948702699953 850 326246170690674 851 328557200897860 852 330881857293609 853 333220204030644 854 335572305533371 855 337938226498944 856 340318031806846 857 342711786518889 858 345119555971128 859 347541405774930 860 349977401725703 861 352427609802897 862 354892096262775 863 357370927639489 864 359864170652953 865 362371892208841 866 364894159492225 867 367431039968655 868 369982601291169 869 372548911300295 870 375130038118554 871 377726050151544 872 380337015994089 873 382963004430238 874 385604084528640 875 388260325643635 876 390931797320532 877 393618569295609 878 396320711592364 879 399038294522610 880 401771388590881 881 404520064494432 882 407284393220370 883 410064446046753 884 412860294446120 885 415672010085492 886 418499664924384 887 421343331215911 888 424203081409438 889 427078988150578 890 429971124380095 891 432879563335014 892 435804378450384 893 438745643359280 894 441703431992595 895 444677818580154 896 447668877551592 897 450676683536353 898 453701311464378 899 456742836567226 900 459801334278057 901 462876880231632 902 465969550365901 903 469079420923128 904 472206568348978 905 475351069292517 906 478513000708704 907 481692439859520 908 484889464212155 909 488104151439009 910 491336579521089 911 494586826749145 912 497854971620953 913 501141092841313 914 504445269426361 915 507767580704709 916 511108106213817 917 514466925699995 918 517844119223628 919 521239767160320 920 524653950096357 921 528086748828706 922 531538244471160 923 535008518455489 924 538497652425984 925 542005728239457 926 545532828072310 927 549079034421690 928 552644429999113 929 556229097730464 930 559833120863994 931 563456582971479 932 567099567840920 933 570762159476544 934 574444442207730 935 578146500690175 936 581868419797666 937 585610284622078 938 589372180583239 939 593154193430100 940 596956409131572 941 600778913876528 942 604621794184605 943 608485136907378 944 612369029118264 945 616273558112521 946 620198811518994 947 624144877301296 948 628111843646769 949 632099798966484 950 636108832007935 951 640139031856224 952 644190487822078 953 648263289441849 954 652357526591160 955 656473289486094 956 660610668570263 957 664769754514809 958 668950638333003 959 673153411381441 960 677378165246161 961 681624991742641 962 685893983031361 963 690185231619003 964 694498830243609 965 698834871874583 966 703193449829214 967 707574657773880 968 711978589608249 969 716405339465278 970 720855001828704 971 725327671534255 972 729823443652884 973 734342413490769 974 738884676707776 975 743450329318674 976 748039467575401 977 752652187967064 978 757288587339378 979 761948762895885 980 766632812079248 981 771340832571252 982 776072922413220 983 780829180007239 984 785609703996478 985 790414593265186 986 795243947060095 987 800097864991650 988 804976446913344 989 809879792921720 990 814808003478759 991 819761179413114 992 824739421798464 993 829742831953513 994 834771511565370 995 839825562690790 996 844905087633537 997 850010188944384 998 855140969545489 999 860297532731640 1000 865479982046626