1 1 2 5 15 52 203 877 4140 21147 115975 678570 4213597 27644437 190899322 384714192 497698617 10588505 275913060 450478 127084677 984457239 854375050 519707425 639610513 86612507 942564467 103946127 285248271 613467451 449051059 6672062 179091589 908659870 451578155 615208721 186894040 280187941 160907815 695050856 437264171 444021065 594664297 515601208 728029108 596310577 704771482 29948842 860872600 236506541 932197508 806732577 586991015 743860570 726848402 24207554 221949280 341928143 179562116 644748986 324439767 165247662 987645977 294175174 810322012 837952687 721917010 560043969 636442705 608322274 608276805 911100164 905229788 736235580 838249720 71735513 343468809 895720851 566000556 937590272 782776957 396492695 110971399 37809459 254360691 397921413 302073802 980402914 523703560 823786376 522464103 550977171 489252962 343485265 697357129 587501993 536133490 835336859 3547284 702177912 142398910 684092245 437114930 818434219 887413157 512329213 911710602 931434683 576543298 885578142 606408183 137979602 579718491 613943783 409166945 467521390 50445227 635016469 816924881 995800449 10134420 636077831 938512950 945232303 160972305 899333818 532809980 606226688 240523818 653732337 884623602 232538628 342500923 60036299 854086405 342957177 851819393 408204108 327008665 678349560 221526455 410952250 463908393 475142454 78620541 241144667 501919816 984078660 724282257 234521346 355599542 802753255 416009188 910740695 812348681 439632486 960534033 883093895 542745842 819514012 556129174 371994740 856965898 35629134 612646687 147740556 342730809 514973217 341385030 292528541 391578172 125002522 832968806 118487703 732633064 350925031 912430109 221297627 564219174 557259497 224790865 586361476 333951081 380727539 39154864 341736125 392653826 619859182 76041691 209819013 117851151 76977976 827685146 877477413 396017708 695883383 344217939 277155545 805429566 571038090 325069421 631689922 416921995 70458009 889039555 568711491 896230173 490857300 955876686 145944146 834297775 273020847 80209177 398628740 780333415 147097907 41311133 997736596 646959343 308542794 414083122 942429297 424539141 203406767 285542488 359101437 604295229 132480669 48756667 142160570 983099692 833902450 620876295 53753544 410913453 103849538 388058846 567951645 139236159 591206237 906689138 276860793 937741080 177773587 238765082 862720262 310077345 626959905 497495597 128326954 640533843 462027577 639527569 788076193 493544265 236922919 73384823 385078326 357534383 915504940 707968902 272200312 90854776 7025502 932439978 734872389 321307399 433697579 100665385 190701643 847661185 458100949 119538118 125807549 877146632 640221767 921602340 651511583 89285235 360686222 378965818 364806910 347481326 680369938 787350963 153262748 711973181 769601410 353812330 409028253 53010229 792282318 496933829 341829217 261525055 906850318 821126164 494312712 923915019 78085895 389702057 712436612 868315805 82332639 148846176 521381076 407953150 798814828 206159887 291956472 296793567 761138641 210027623 264173101 588433125 665810375 42544429 828396306 222951889 457992316 416484712 333763142 902488285 219941717 416489097 480835040 46896468 821109075 544459264 76050899 594713612 843245207 817026703 451688204 656679946 231633864 523598598 750045721 314181434 983420086 418788357 187438308 460293279 487435218 568592176 213026562 385065555 649757722 727113572 918416270 292786337 252966786 705193802 97586948 993656683 791166787 244382786 63831671 155262437 945695213 958719070 494876229 704402492 442256775 177132996 5028928 174505721 618044900 335615909 845136607 338843438 813574486 177941912 356346843 577023423 965868846 788133907 703646596 541964579 152464566 358358937 667079587 263659840 11177981 123234209 580930828 293882632 990979008 109380365 697305574 411012149 989626063 676671901 35682333 583188892 727325585 529357422 60869879 760472929 415041815 131163527 551307632 210185487 884094571 916171079 897879286 235839345 38743592 117668152 555098666 725224180 778099513 701527660 56830821 542548374 295829263 387364232 101168843 378567578 924125170 815895363 899042775 44811471 499455161 21360161 296532574 185592940 936365431 721438776 552733069 353748835 226240543 537876975 410540640 128255023 551842737 639317741 850650087 62402838 799383131 655659388 836796893 664048644 994889061 513224082 242976878 748199884 976936520 89388934 249568881 208842732 197904214 669723911 699379617 326052989 600899616 371565926 258801951 339118825 849158525 857512166 299225929 188098162 763276024 294699202 490078680 307801594 434497213 909053563 779913966 889858800 526666901 213292100 36501756 295745364 437574091 670122584 14506183 251825106 706081256 147215650 256642415 36902208 178831347 758011529 218530074 187225940 226744575 560980742 614935108 833838105 300321877 405637079 780696850 160757663 952574076 755392821 710448776 718215507 896609266 197457394 568143692 304566015 979920848 908458640 135876270 153633593 241222375 119179285 959646090 805729086 693923873 136804365 189740329 127417687 446419941 953520406 184349996 35929364 500173316 20088000 941867111 294877321 249829657 7545657 66943270 858934367 585099792 316501910 284169716 522490279 828706205 629165683 315439344 930764246 89248742 566861757 231386232 31434225 21642626 809380208 553611686 305007859 276077199 751745811 596952122 779326285 520404364 732215820 22258578 40871914 561953368 97057141 368413927 991607397 442502276 495714272 854486787 667190051 100085077 480883837 471358723 544857858 443109595 480387466 83330835 226547687 227554074 977747985 634553979 349852853 565508167 54103427 461529727 3213899 413299423 181627455 391795356 489684788 314235717 291977671 854218834 711097927 901145143 540902920 720787792 859056298 731548699 230833134 81881937 36431064 836925824 633196612 201044879 73874685 940762749 803377799 865139505 403096395 501094247 661003414 408177963 639776700 781521736 137079981 964697037 843117045 555488055 47186058 667767540 31289041 380404564 419964371 349795409 772529099 318813210 778604952 336673382 258569536 673120294 598435328 760512342 818767443 856129288 181551778 827333521 526510235 555293443 297751011 639841233 795861134 213586623 294589250 975271174 310010175 751147927 262705314 852020960 530103046 888705848 48264594 793912134 970388152 624052472 458173102 810326967 187290110 557893604 282000345 375749715 630578319 230398698 60223281 619466284 860250531 480213524 90924150 251022609 707369645 952814728 672206970 48384797 921997003 254553091 38632622 250953518 755955546 535712914 491230054 904926662 904634838 416382313 222282444 845290378 288225687 751797956 943019707 450528920 727962009 351201822 752085938 163863249 23144876 439009054 364330316 949996968 327616460 690369812 366145179 447966736 956854337 299796915 335223004 973627518 927307267 382964170 463793667 583229236 140011941 641897831 941797796 405511746 653490918 635144993 963706688 333763117 39788311 468232494 315314476 191466703 9689841 871608805 143459259 345934187 244406324 687646351 521236456 574146713 622877046 564015872 90053702 430855148 816848494 381762102 65644838 205531593 899974723 452005249 98147893 920581392 914728821 127507984 927622722 269002486 219377364 436750894 862772027 991409559 838701346 945804688 545078480 384917336 79844575 189378565 726920508 136190828 437984520 367335218 783441840 17472051 350434508 699723673 918822758 739475471 71976917 413275040 853168178 773678824 313702527 868219432 105069194 924263570 28499105 17274264 520610035 270688488 823887037 765219935 749101200 956913797 455932645 900794761 299286541 112031968 823062574 315313607 643559693 114295103 367610507 719033240 13498767 476343937 555234505 372261489 72621088 121422192 885046487 135447002 654876088 806575321 96301701 704738208 537871746 564198602 67205848 912165872 557992400 328116713 98765167 606874347 762408863 399070335 473530328 419156918 375922379 35976672 509489508 297197097 925436859 408702529 704886879 952952435 890222564 923748748 860472938 821742958 673748401 792353791 718280139 530630442 377491961 86864732 575891546 101807389 870513123 253077650 860015205 712616102 456138475 684638904 340716163 828208571 523905293 419247508 397586367 864733727 765379872 49696125 129476164 249091288 26054018 486000062 194771908 603242217 863018213 912093575 703562811 92930226 324073460 390870282 482216309 358559391 634670097 950050829 566453828 216779276 390301511 589983674 413677358 236146910 784425924 240111847 63159879 972185995 332913593 26876123 244161387 689979631 900372333 166445063 173907693 754000718 924118702 353003358 672932807 467139683 663767680 584624194 863457476 275910093 857907252 394803670 369363659 234309161 356072325 715706150 313990528 745145679 732832892 685943199 339658480 375943149 680249655 474188346 452975117 289119528 979370553 683279766 339160470 373324753 337449891 399217640 70107896 643649521 892485943 960307597 44560026 754947586 129207397 16980704 510359904 56906410 311967726 325608266 419759271 65218595 734317114 290342578 481571753 773265776 469188435 65873942 94680095 321337642 424843462 371129706 329692238 966353344 864748590 535143679 774024708 650834828 14536508 477455288 439395624 829925486 525311591 398854151 73370206 558848860 693612105 623025776 707441748 767568362 927400901 627510444 424232771 508359801 318598238 608297671 583639769 463066808 746802241 773433245 364468440 882989995 334113505 321079656 585616029 673580338 128417738 286779932 621507590 818938958 89727625 354656166 833340823 513970029 220603155 716316969 936145508 980429425 599133209 821428383 746097393 263779725 532983483 767125301 928310064 163490562 494156142 680460743 721647314 698154360 720592542 505982305 533204734 503420343 253031856 389371958 963622894 821476340 45564744 756582217 487016374 807626666 78387283 995971298 114230341 392246947 574216159