20 100 476378378 981771955 529921441 523888279 325692343 762902090 820988204 775679521 76690885 295793697 795683156 507946554 150190660 66182387 442651653 788104710 747292880 330022702 467089271 58401355 24940051 867945131 287749734 882484314 627955518 533710681 858723902 568876281 14139381 183177334 639484266 7922998 787714450 295733519 947025022 671567128 658581611 92035046 681480822 158445914 797364275 450196178 966605157 869807530 276585900 810621419 415490063 184834683 681039311 91934183 790338844 690115029 472738234 191169446 962991500 939726388 835167725 847754051 962115835 340178757 79899970 431626567 714599429 824030055 629928841 120238256 64980282 959764433 710584597 160180381 561276775 678606618 388957727 927345829 464794170 471262610 515267612 68454237 334782545 660649324 351678993 935334340 238717891 580233749 404337973 845982199 544074328 2566594 709434536 500150648 72476395 293878276 338241438 217669923 418152943 272781696 659888382 501608592 981843016 346768460 100 657029328 691150134 328119591 316099563 806452662 621119723 590565888 784624763 637531443 42521861 3962234 888592151 753366125 851785393 14684598 425268943 851828802 214337793 371800747 946607197 560546353 262267879 320966875 512996729 467702698 649015892 151441186 675596047 316920019 168975661 935827201 469986952 563253066 218431978 639000493 37498314 288712230 557485337 838258531 273888968 39022803 41538037 336771387 451170275 654784457 316405519 3032792 531853178 17803585 787076251 262189174 437601733 619991053 7816404 273059604 605048621 292140332 538966235 930349538 160690712 485777481 361413349 120667495 27489375 629099632 576291149 7884765 866393411 976509771 470480967 969549102 24449419 584515869 11074590 491712397 220289022 21066164 209283797 70995743 745280999 653890737 695978562 970687873 890281568 443120295 602900829 423054742 936122338 171557652 585771689 482773556 556748614 266870924 769339081 734638659 62631025 788050224 18350177 814615158 231792408 100 107122949 790807367 190447150 701534078 741351991 372094325 941981469 770727359 177426651 497506493 797037062 387813139 785269656 926615618 799540903 69834534 204264603 534833727 314725872 826827411 41228402 289273750 991436564 543274565 99180150 377552782 306078099 948028147 496015045 839387661 856648543 250831284 445408772 890649274 350551801 238634703 810057272 453848281 370538912 764313824 217871997 44797546 543618514 614653982 924797487 287652515 138012002 944170090 265306721 419126849 447528615 387885663 938095268 258200822 878613747 641661353 539901529 810714667 396801520 176267351 422357897 33189612 695842133 782977313 203849002 444096561 439774440 23275200 26304276 732983470 529835855 972771639 40897895 135757969 309050647 765488384 168846021 213896574 927743333 778159365 902574174 50255915 735729446 499825444 453977805 64384316 362708682 704753454 18357279 825617384 125861704 927627157 167263270 774600284 565798171 553631744 886661869 461210683 291492425 593059814 100 704713070 992654750 769174424 328239153 169780009 477078102 580080009 367419679 495119764 482400910 280739042 172059305 693656013 13958350 855569890 39592926 308921293 402898615 701744700 520945391 976368471 790256011 472788106 669717456 645793238 729009380 42359393 388190191 54387727 53106031 883314235 244610162 308958240 620971746 752140902 420987160 492457196 589355970 533722399 388580895 179512456 544355803 404273498 498489828 729605280 431747479 261539856 433214528 426847783 494885884 311802804 595344025 906722757 192378119 889221043 792433195 402237841 913412761 802598196 949876704 184364901 506902261 337939262 437832234 643471911 446958601 454741152 132253285 284777959 559206126 828004545 391226305 424364246 770237896 707972832 775395845 367496528 68543160 800308215 978628480 894135896 440497859 486537962 615174457 525645636 576499601 571998480 96999176 80012919 462863721 727629128 944987594 728353995 217263411 901184149 784933386 902168099 422597072 650246711 34828098 100 310336234 240124132 30996736 711964813 402904533 762633806 735758449 588662330 325268297 640937764 384931077 309516528 724955952 232606110 301335121 245877290 387383205 64664846 998610008 379573713 33102590 697470435 55979510 763062915 322034090 252196966 984016821 832947208 639731196 795219087 35840946 714988057 572836488 407484899 924882391 947330353 595856377 81121769 939600444 396260049 217623071 263494035 780892501 83262297 221412511 360722029 441247749 799150269 899315816 992224906 475702651 39988464 878195183 701191710 715152754 1918434 612704533 467462825 723487759 102457877 812399412 547464344 910232090 287374187 529725965 70692845 166159261 473720153 380601073 715708250 549848891 361074055 285297382 518980542 595990044 380308150 847974279 338067854 688009359 477520803 98425925 821372381 936926792 128819455 93673826 401669906 49340531 332469933 283816724 94477902 902241330 341810462 39045479 529475381 207568634 221857742 583923107 317516845 187990461 782448410 100 244966041 31507000 620813925 922176378 55512488 583018894 465336811 175816218 526588242 410593511 982838591 102331715 333834108 126548417 293958777 160567023 809006263 54480684 158272958 646969646 288288469 619127318 566329696 414567469 786860490 697094840 801079024 453767002 364584515 315521592 979709316 592573508 65215449 855473423 773154101 473018188 489744283 738845463 906680627 594857922 91220623 641913550 25162156 437925528 316365983 588037522 49427299 317415545 274026118 88119481 220199819 52580712 885269455 3757834 199407314 771039836 780642140 926091271 723311519 721087222 769846025 229165932 697713185 394809677 928176087 436807659 997407182 753161552 35847029 695329916 825194753 339582241 40336779 926230641 699606569 68780416 101397275 538766794 26877434 539513409 31356437 682216735 150909381 669975569 321028686 833628342 242055798 958831951 393774497 926859073 927930539 151924884 129267518 933026738 633364005 783446355 903407087 529811539 763805373 210021153 100 35518213 957752090 862878824 611756060 94931362 994965964 622420798 823589597 821670306 482625809 568500857 293874749 230201490 508530122 27359456 711834651 209908825 264935201 380385834 836535635 442631136 96608079 535292393 347850368 665031038 216251917 822124206 811982710 180046121 733421440 645932113 696008721 692575753 233265623 562559657 319230650 899100709 433581533 129286914 688051540 906564713 100786265 405845961 849331560 72899801 767454955 352969659 138465475 576335144 914128664 892158261 473986588 320767473 432109956 162347877 491073595 747931922 201750615 352123769 673626681 908026835 499000607 546669057 911911030 19072296 740835381 809705999 430549560 826426200 172805812 434882611 652259793 90133800 811330416 115939870 767693930 750045202 769649393 813166120 16931518 967615400 297512847 854506138 23072994 7120858 539938878 137676345 563445975 445275878 495158854 93587649 350899051 885594523 988547211 718173468 579515748 129237753 623784998 129479160 537392418 100 291922591 368563097 80770592 428984108 480904762 789723631 626438795 952296865 452783152 960581219 219426354 572944919 632784415 126268273 545358919 203982778 45843487 874447620 515167909 392987107 309585508 838521280 240986307 258546689 509161738 767669878 901570009 691257607 760491646 586472306 298988659 148482186 112955140 898985343 31238883 398434788 820708651 532175937 100246694 670908558 739521595 76832755 943169570 637606345 583583461 257297236 682589960 125686127 104778300 287916130 603140828 293090173 368706364 811396775 475899530 892515199 227242282 435477222 938711704 888888614 820534525 75336189 851241495 941012416 706542377 10433021 242615541 5561653 158457545 227374685 886714584 412684175 810919610 643723433 782706503 145169701 603885364 96845873 986881210 360431675 324641083 457100799 123058598 194668595 580137804 866249179 19483943 828709813 718152537 878843346 215797102 865189048 531794335 564718277 404564657 850085905 962095347 455078339 635586361 147284876 100 781575505 378580859 239283961 621484540 431203452 746106535 466114082 549710606 734522117 961371111 472612345 219273472 441094577 964479542 473242435 60253722 295263 624170570 632114547 412103330 206323357 958202963 177929056 668712677 519266517 553354454 61633956 76410395 157241348 884592530 539115296 318160055 634377703 551380895 259722626 524793184 558734069 323062580 367872197 502233575 200607840 308826954 744494622 570897447 351695494 728072581 380546591 842880578 315625332 842279612 17954287 584623858 277111942 131193979 38811671 987554065 793839033 131518354 397357209 364809622 20897617 865845015 334112865 340087616 397416018 442428558 726829742 584597830 469872463 76802950 505265807 788346665 580176910 325337901 877165807 927394568 770503367 945569955 630084555 480850784 355984545 516361857 50678411 80968785 40840380 939152363 619747586 97768308 755985236 902713735 126933397 93687739 617502165 474569686 644692182 142366070 668160892 97855969 282438600 516257688 100 380338631 756394281 208702786 536075980 122001619 589791492 191812748 322430605 478287663 336365018 982793871 64826166 369174553 429966842 365879066 301945158 978164483 536641018 265292114 899006443 19359288 233730637 107049754 756536261 996218652 504436090 355008826 833926603 929329834 561806744 985498161 612012464 500579388 798180447 584082058 88300152 229740640 403606448 488995940 949660014 472950384 513009733 788251307 805008412 376439970 64091424 571540316 937702307 490879938 397261736 342351254 6664079 477048929 9708716 872497701 795911582 684776210 796413819 590589993 140543908 816425686 24637290 818785467 655881536 375464192 918399055 552462776 823306601 741099533 158120108 913910798 812175554 526327930 341448103 62229523 7288439 315892406 842546238 480621993 659145475 154351203 2403936 143725688 648606502 981472199 34430459 822994072 762794630 2738873 730102768 351996030 507256615 584429340 757394248 268292977 788222170 613094192 153481903 629466893 619740252 100 866779390 190206355 603034562 218206328 266052403 151972012 65195822 778597975 53003937 56821840 292898406 468229712 581781238 476592889 995518147 597765734 38248332 557338285 223515149 524109568 886669531 396724594 778946065 359606044 66014155 134361253 639997081 574834031 70896520 946608939 554042682 764290661 890751200 224407607 813642030 24131813 746211579 713520001 714924234 240948138 950354411 917465703 502845704 365061510 401984493 697850391 99115357 646649259 873964766 251200689 482890159 296254944 829207291 66307233 128449625 938121010 781643612 17083547 86877394 411559958 900954204 799139589 558822644 68259218 855639466 51933416 31375697 562371890 859463445 838451845 278319316 423981511 795999292 165856221 52474337 369825340 89618104 210749241 338157683 682452554 864434845 607811979 18754337 9953508 805201935 591039848 837910309 531872807 600920873 635514554 899132466 886815681 638491958 746210126 577722305 182911889 785931344 853143187 726632991 280649164 100 214062217 755906616 688793222 3773142 644207493 582191851 647041714 101167292 25351035 936428875 760225257 731698612 634249796 652186783 426557305 271249830 211292376 610497448 757062901 148968443 585470573 131709833 357218652 887610132 830869584 62818421 408926113 82202734 677285821 154123005 731664785 65453238 250685323 475365099 170262701 369156329 585015564 904307402 845157367 974631746 7632928 416695726 370162168 854549424 983819413 997447728 881413453 892611711 242937520 541277391 884741790 419938060 525999324 893430749 437888265 112391928 242229242 471617193 991621435 107573968 88167229 249939747 987921248 893070349 475288047 528026051 983641040 707345741 720288830 457180454 497820557 265402839 184527903 572813607 544305481 835391639 279638003 991997371 72174724 964902928 961438500 22528015 271857354 555999477 80373996 357408245 704652043 424225415 859973839 99868720 459419995 648769744 503407186 92093045 425400131 709781970 373550219 400715252 688051832 742130807 100 91563656 74483500 550026202 626566426 782395248 895239902 196415230 342308526 579015233 254145670 672272390 336323173 141867862 139996703 825533468 980298867 590289929 571699467 713374199 393785377 894378399 410137140 445799092 499146651 95699486 101755734 551580187 446297001 920748005 827578464 246114884 579771411 793338220 730408526 85437043 877298510 747724170 517868512 45512154 343805396 192623993 644447228 193116784 566641080 799440256 377757080 905546170 977542738 423262319 817241308 785505977 554212065 450693349 982593376 148521177 50986815 524225289 699259535 628908691 19345958 972434123 162744264 364990017 29299525 779863402 107713027 577911563 937348547 909397585 620684351 960191261 438036506 414302853 518311854 529152370 10993657 803842217 882904171 401710937 352443246 540116220 102142909 952870432 219691295 101197818 970169579 720107460 502183022 396717859 165240840 953719444 960649830 889933985 718451083 267833612 837723589 436416723 725085930 289020290 548595801 100 744404972 421313762 396711709 961433717 151899065 253061584 916306366 649304111 629160071 115893039 679324140 342983193 552751870 190883042 528391920 921811757 76010150 276318505 370725467 711699195 319851236 295630861 394069094 764456861 204493283 586176160 131468891 429715331 517962784 670181351 527900777 156179170 65185022 569335892 550148569 551757595 7771689 89019173 769409602 940547295 123807641 580904268 333163316 187289024 539072349 315418875 106276210 311380184 302746229 546190641 901289029 748794988 36292166 897966921 159320 93486747 447273896 359218580 493625009 155141597 297669011 606561209 797432268 79273458 168975634 67684359 713031751 53568274 56110844 820291168 501567382 802753929 547519329 507046824 986057372 236061374 983423259 414998167 506057115 663380235 525062961 178887228 178784246 585112563 200062700 566373835 224765763 541407991 322728850 206964527 955350233 968328699 57061587 801576461 743431060 128901224 480982979 344839738 570006311 85781696 100 69511084 921168255 951916595 603191385 247817246 906836436 661562226 616594797 697639353 557969925 463657392 528761880 839235272 625890572 736185797 107137351 652739794 761406726 213901036 922213908 83224214 241796781 310704806 72864420 909382070 515070601 905369385 269713764 726154395 201387250 981484297 584357324 964121013 357708491 929328326 66248159 852235116 376867073 569693419 982941309 693474673 65729307 785770246 330029377 295412325 649485218 363845619 357147810 19740083 781117536 634692060 437046880 93378697 609077729 560199167 751829745 16778744 819386009 908092930 99217240 163234863 466373493 752844740 510152227 249280761 534084219 517331592 98460253 718256089 507962025 756224775 490749924 450100319 144546390 759858759 447784360 758265184 616185677 389228980 280429677 380715676 324400799 374029940 597883503 983146693 838980092 109824253 140415105 556540761 745896008 513423630 929136878 100410807 975783928 257760776 161354619 338929154 381565301 360012681 723503004 100 482617549 372583191 397469605 267845777 8959031 323627981 794691152 674660535 401025458 697362195 230129336 351277740 81640205 975111259 56048757 321850693 153912024 614987908 264615987 460535030 365677559 322235588 488923008 443432695 216225736 715576460 442132830 968229388 507499348 290628701 606341742 505242431 982868278 991034996 92248733 63645188 518567761 554679298 810092241 423195389 445331815 308791657 573890361 962046053 986692304 603948068 747248996 237420148 491399795 683599698 146258434 144198904 129363228 927742741 586858725 343402221 828218176 967118643 523825742 654334778 792068095 385396992 181120180 731714806 383286991 396044610 470468490 287623879 26615351 72452618 141520871 993669803 186478086 144893372 713945505 561192033 290015302 154026816 39367854 503974425 18099937 583667581 911525251 593894192 366945398 745869009 695922176 496617100 385793694 18871408 837082353 180567990 531389057 434881979 546658004 175232519 607357846 24967850 131376907 312461915 100 953858513 987741918 143296586 569621273 708601493 658487118 578718023 925844382 968327768 187248807 686673949 66951159 589907592 83427879 248169478 494331145 210080617 533650331 726127188 497077490 675136689 485999151 398772674 318333778 856458470 401933521 919001573 439302047 523635844 62646111 118685959 451786333 393127180 584576836 851992653 975409021 538018465 223763851 812751601 461972376 168896580 523062551 968276998 572737456 877207625 111591457 646254396 156957380 19484234 362735591 920263865 991884739 240108151 541939427 263308906 516905188 533470973 811843359 165433135 404517660 826094413 968491993 717874867 892056915 521935532 893111741 884341985 965911296 335978714 857575114 849687934 5704016 877695277 390504194 189473106 503073986 602683974 772191992 790829866 284767105 112586903 873942696 157146892 371968672 471690253 768380931 427426810 109484045 42456786 795518453 652768221 758163250 440055574 779308007 361114395 772525895 965109695 278992300 961482686 953048810 100 278270513 499962772 974044386 676194362 477487033 70257337 484424952 708059708 20515951 701396300 539566951 410761022 214806802 388873127 715636884 66615694 801351269 831410999 103824195 139361754 200208145 723743221 821487205 548779666 173865175 934597450 737458102 439292523 316966643 902692979 56656695 57239993 362455712 283428722 955851319 721876372 972508290 859590981 13134393 449473368 992579820 325109849 674585194 932925781 319214471 980900629 446380054 967765672 981236951 234448076 348019106 577286521 452925596 635679934 502113698 934727070 619199307 69062124 517557627 949859224 212317572 130344133 754902412 981661920 681568444 677414531 274178468 166283981 249317118 873013573 224551723 296377624 475143567 341784336 354432789 460198792 453546022 151091360 151328087 904971730 904689720 265330396 975006123 787076064 472495389 910651413 789901700 911743037 469183816 991861629 635693941 869804077 942071364 595153114 755095776 390402205 981792857 247153387 533757190 270489954 100 683977505 203512359 663026389 485748929 783954831 774938896 72286065 710157209 528911423 575679282 75790966 62883420 359718440 337861486 85314643 605247054 32034944 210667274 31619364 185815863 25588439 447341640 236612649 843453951 774050747 270497835 979619281 937759556 802547723 766764758 80096167 156422273 872260895 557571031 102716309 986965027 942262344 127288782 37027264 383050722 855627074 75094343 684746022 197090389 70471107 399185325 592569975 205736471 846345777 753245974 926002225 585041840 357335066 809082462 677286206 133863875 193238287 757854107 710617018 16642312 351539542 316846451 635315779 206186796 843338053 803935616 361964628 764887136 113242681 520983016 860752603 381332893 6457024 532860875 961699629 409218751 963256271 372049319 513596480 773306339 863065373 948449882 265882185 699062451 234168606 56716752 956627787 199870043 556728695 565780546 948417318 628555774 173854192 916375239 860779023 578647045 681448215 650170387 146868436 519162269 100 305604886 953990861 257827598 923544274 149338589 416993200 810126934 523729652 681553350 655260407 945049789 261642116 226414140 697257550 218298443 783736478 731947447 961124870 315901311 787385109 798682379 797895459 976218224 886918032 799102439 860111434 974561031 398978896 885692106 333420593 542710950 659309640 383723672 205699832 731125324 711988987 849983280 715368275 690098063 509997099 457499677 237870422 412899817 98679633 290218452 764949637 924621515 336513763 912210446 441450730 979693117 703157500 322933824 608768706 81550495 834135928 193726107 841262909 37148684 672486747 667817815 756241282 757474911 78888340 957421273 595870331 192204912 3589586 357556021 553130165 449583905 303743590 764227664 648537674 577993833 764469375 517484817 461997891 630623718 266902187 348289620 392958384 354691467 104444347 168534575 680401458 557286477 655346216 683364479 204673293 935049011 904534824 748570770 916554425 869064250 852764219 361359847 876667085 773719645 381741021