50 50 39 963015890 811102489 130656998 592722796 948889454 471238533 275095669 681394171 325418730 590568888 431937458 919279309 907555424 452053223 167857369 689141548 266518464 361987558 587596170 970325581 247585740 665487653 676512753 132846122 93537932 269087653 538530022 961246794 536602584 999265866 792087155 159021375 242289797 524427169 358704130 459751201 246167261 187963267 484186995 33667578 380501354 531655163 998773009 646437244 979574083 399768148 910739555 482055949 396270784 897524087 452184255 200732127 728181459 632097090 857838459 90590195 191420586 440487534 191387753 944228055 197060056 62896224 381537571 553761439 968284803 199112496 452163070 317200794 290888014 476054471 343048663 825254844 845748202 758672876 226383995 741745214 947301995 128725634 402133089 73745646 351166801 70585458 840898247 416906215 199786785 637742259 617362411 73745440 787586456 1380421 641748691 265255042 118020965 603503442 229241812 250646930 70628780 997718357 642868516 626781280 364119198 297949801 273544036 775652893 59126736 158195255 447126515 928183928 333187529 656979049 483158448 303848336 808431232 165881504 422783384 824221097 560873020 871317715 20380319 552972936 705708071 173984271 467102265 180241917 340018696 247028750 447169478 771173748 848854950 489943551 575886675 458476004 16900885 64662176 421393546 327021716 609453571 960668825 178246535 38911998 478319413 773452228 401283568 132445440 630132309 21633292 402631304 75779167 428793079 939893950 473412988 933299220 601313159 320730251 764064829 118517403 598758190 563655262 891210652 469056918 410804760 973210208 879093197 109471628 647230052 574489910 513086181 113474383 464376332 904905826 155584631 704146808 268161997 983703560 55121719 426781345 323843964 469931397 552201752 664805490 343636026 916512089 97775201 195367057 501863534 872631428 707104900 146498763 861591302 779863849 135780477 623541203 415957664 86591787 585846983 322267808 214607430 370217931 957149964 726406153 158638234 942764754 543200633 891713078 41595272 173076651 314584917 93246758 439771184 503037406 669400084 583279309 431582693 507598695 194574735 283805819 952469962 277024747 196815732 922147720 118273097 785593149 944222346 579122656 702068868 17456630 213674669 782695045 782956358 993766610 295899574 651810629 291010219 445056084 342779901 559079102 734366468 680072256 438199330 970637718 854814279 821934131 482649277 962452023 811418788 960372057 295651855 278612403 145977172 703141828 838465142 578429964 772010805 220662765 651161739 186643150 745221020 582786817 393738497 350820768 330355543 809531364 379414798 903759492 592356714 152383077 890248222 986137845 741389134 692731112 833118087 902943273 324257206 213673691 451494008 838636655 976544730 313153514 523641505 667502958 487504475 56526262 853054576 194974660 950159369 58277362 499437402 558611237 726315232 77772672 748838036 700486910 329271899 81849805 379414884 915431130 55432414 965261766 480975303 90185291 46543892 459907321 183259132 661472324 525707540 925101205 702253236 426967507 832833596 8886803 806985169 760843664 941345818 267450727 549164819 850556491 483420612 393198450 153533279 932040203 11608557 910851121 682561360 187830555 9564117 464967255 598585353 192997371 460381601 580764226 800121919 244724346 248188154 481516593 10232304 64065571 319157429 857149361 583547142 943291847 611186826 129776091 884635710 74059209 253287882 214034419 28646919 732507784 933893641 435076271 280980981 576463495 908814092 381501550 613571248 663929192 26945015 287699081 690016692 136931284 902369189 1002157 375163906 842854195 888205627 113349697 126763729 501903032 771632285 538425332 121767066 244371583 890036764 945938950 794402405 644864571 454595008 316246261 489546141 705847206 444334010 673532072 922940013 89383198 684404397 333605850 268954983 612080966 45609578 666145340 965049070 454755826 376760423 491446204 36695207 381638245 911564447 463517128 544831766 368414117 160831934 425910656 862421968 828246133 12763520 523441363 734048868 767108426 125141668 414142930 434540132 955115922 546632870 257764052 483460612 187988014 13196167 299029298 432547832 982458507 579458864 8425562 479689233 783571535 304638779 331247640 762762405 339115633 463297826 839498549 766427803 811861595 493440944 314360589 654294751 63313676 735979827 764481297 433396213 631084444 15744114 634120796 362414519 610236091 914828011 193852895 529666035 551726978 621001294 896647482 787617440 731830849 499800624 15455404 266092489 551578299 584258001 89668753 582221513 801716081 422132818 65051961 616771425 26421329 740820064 983351580 394385084 616395181 751299005 436648021 56797849 947309606 801302395 447145841 792987464 428712825 889524419 646704971 901781708 646687981 366488966 851513625 742668967 339646167 367651580 675610055 733652902 221216271 427088967 1291334 750462986 802132552 606626446 330629167 596130306 359054316 309241075 446984863 939256411 610143463 996058636 304103423 621436606 595434638 173751901 997889063 142168368 505008327 578313365 604136037 399537634 136934271 700371537 803606895 31938481 215338062 649852669 975399429 75929128 15033050 403341294 772602664 718795486 704954934 314567727 262396440 981795015 691654406 313986794 814033382 405292483 520936317 342711480 594064507 762360963 222758423 677154825 596371055 306397888 412703656 807089522 676527661 159585922 809095607 395062473 604340725 920228777 556836260 898617111 617466351 556184240 558373432 200372507 187619287 48177530 747082527 987843235 975240227 24117757 454163858 774707886 223234752 777469599 370499623 618040676 829919195 723905747 750522267 494666526 132881373 225063211 986194922 191827955 323964549 511473184 351227496 51705658 791182118 842188936 526437302 345999062 484701588 772992322 225090797 888808109 420213834 312082471 973418866 219005144 882228548 817046848 632106803 950257148 414633146 39225504 800060205 774856651 557859544 744075026 765636116 434842923 300465356 825964527 657075599 727985106 329245011 906727297 647498640 179976331 955709561 818305915 680020652 288655352 122836378 511578341 852361376 338212172 195246312 548251978 332815636 690622829 202636521 573052156 79320789 941280724 613761625 98017586 937395714 746782263 225522237 851320441 867138069 221562052 882940816 400319331 615618965 562479877 347672290 608311227 951099751 914756654 927906778 766019593 792023454 957371850 592328295 799722916 450378684 990454263 268716027 504697548 632351401 234197460 544939880 16742212 122247256 838836720 805152051 178833618 856837410 843428749 369959056 557224814 736832197 219406366 206523366 699531608 864825837 340616397 647706080 951347192 693060210 832174438 762616372 131707297 272739997 449106180 476765839 986374023 604468152 410541492 178310338 435813209 822754083 286725187 986701945 8969015 362888001 381406366 844110465 366614382 458144026 970128598 581318226 939480159 713581338 145628489 743060202 82316375 444534490 988061699 377731718 909275495 729746270 38512339 856439989 846737992 928335800 999313606 496301674 146868601 568512480 683401378 76570338 605863609 689726200 509729341 355899346 768462863 754328227 400309210 363852347 477591562 905588458 487484391 435386901 794243392 402838169 429923137 472644707 327858390 39975897 129148765 390600736 775243874 390636776 761207878 449167046 233083098 74291691 217429200 956437491 70418202 579914397 796343058 905961557 730634946 801665200 623511442 674297395 234732643 189999086 742348734 771958145 119776571 103740234 242351877 340547236 226277840 721496988 751845301 333610293 718369090 395727086 529194979 822107695 509818596 857845467 612369971 970803166 704997495 698532118 288851843 637125376 38345303 77114501 186704439 246558 578119898 211807837 837233846 980108809 153559114 742429680 838040688 829639768 63733592 67226163 138590466 947428747 787718452 432219302 721509346 761254072 899271706 578269733 623699281 57736692 582107969 10821861 39598987 204254694 701782965 694104793 187929324 555035423 612744344 87330503 380016606 897177325 955030610 993601472 542863308 185747038 794222239 946973683 112640837 249069665 719088265 73997947 646550191 191564825 956843754 91903030 627987624 327513754 492319467 223282299 457877539 425119742 423531969 74820697 178233107 68678801 79970088 696405223 648477231 433585728 367733123 235867964 869763233 359508179 738428838 872124923 369983870 297450417 740985370 787118763 298021277 858455137 873922145 636922808 544037763 171877742 385844936 491310151 592826064 967493114 113702107 155714728 149413978 814066590 616898169 92212900 848081194 724391492 366955304 464522 330398897 32567355 730775335 117909978 824859158 188583291 970295090 16382413 17838789 61213130 506016364 905708506 927637558 530652263 948295868 109944762 572534047 255180745 380758776 707290188 192384768 13108551 302168373 830386710 6096682 105385345 221878540 513466297 676919771 635407960 195990843 66962143 995585768 650216244 579229164 2686729 295453994 842985833 283266513 434542393 638016335 323546478 778450735 652655007 775832632 670057917 482321248 702752339 352655899 654456164 968786193 669908629 877911366 962975884 374421674 112902908 987233471 114488191 901245555 211067055 124819249 890335817 502105666 630379844 755296133 285353776 23745250 113236378 197845983 679515475 523336067 740756774 623026450 614435384 697555679 275547298 171879076 906296414 343261005 366540272 353717457 915214675 145807366 283692466 533058758 58816454 979816604 431263660 768170480 714931050 908324679 801215815 724994430 890954935 842233648 74277948 635218261 658967722 455021005 434411977 346705723 926385927 751511291 413251978 152553671 454828748 741831210 63501411 82862625 973935582 802765665 729077524 576233993 47019054 740070258 182301127 116813126 489750125 746108783 615707473 385424571 519441999 234002570 12487313 943638600 693316422 345901252 86282507 605454115 137508179 340402393 264592783 867187458 240273409 117794577 523600782 801199412 705526549 584077772 449038620 538326957 256007431 398024109 810804844 63310262 818728460 665486701 706272666 41565732 585527994 271420654 720621076 342673481 619861885 595941143 675507360 407713501 749660765 818233489 935514040 971018674 185965114 362248787 685084620 679579179 393827036 137708479 634375636 73985395 595616575 457104109 289572185 771875051 858106901 167542328 870180230 966532368 633119750 432075662 30864361 523882892 756211602 187902873 171589273 992263175 88004097 368776060 291754763 729479324 237623972 406746587 588522276 351944782 244573571 804279018 876676587 61062779 620926258 329521483 393041048 111146193 929210019 968247109 982955484 852030764 299989822 750354041 126804391 864699487 700669719 760927778 90992473 13613656 658327528 313052622 51450945 668046186 973649255 555532421 972250868 382848147 264477682 306220460 359376547 574923275 508787208 14410194 797971256 56757722 732482872 406043065 968349452 234027993 360342485 358706174 687767397 596375979 409704152 467786231 176610963 276253568 492025509 911374904 593745631 727608529 163239336 720111890 558045044 408959097 700622528 668410170 942231818 664855230 156264505 367295324 569777740 827185473 431682672 321057279 772137118 766003948 410066475 653250914 221245788 160833278 5247642 845539647 835113771 674191501 607134131 734122085 381041804 100877447 319275449 653735876 884149229 109770719 685448702 702849312 389508655 814914118 609210413 993673270 176896316 46926822 751047230 878759552 743519892 956992436 138989735 761094592 242576332 149031140 538938227 694403687 157370758 72046979 88435234 701379948 905491512 589136744 281679773 579448267 366372347 743050552 396930412 996164018 427218143 949782279 388744008 477249247 967881498 384744870 660793071 494227603 415197634 284289145 102430682 500008273 73947728 238169466 633899064 790131493 564189018 653408556 587177787 100055108 594632537 783059855 915040573 582435443 414308559 706959 368183684 700707205 720763857 635156973 575571724 56240746 632611990 625792387 902659981 113993804 383495478 800194443 856408831 778410666 207829442 522200443 280626047 209468412 676987312 223959926 789902363 150976039 374817924 146794483 440125114 735888580 337506429 578331252 735500745 418210763 546555788 965332770 571814190 603381494 483319510 139783513 715052783 456081798 648315552 333836257 618601810 330807241 561498339 557233997 421287009 179888243 620029738 14280838 418773282 530961244 590511211 664317323 512640962 44023423 744530449 734397898 374284464 252445923 294950351 619154674 561845307 691551320 851371321 662617689 669470762 558726416 220200019 303797863 339292633 879900657 833947507 821883330 21698278 178658065 686683106 848169906 723861133 850325221 443718926 323710646 52162840 132820892 97793314 197790235 860752706 737681234 262512510 997333215 627375322 703896041 461353041 623804404 210640275 165319546 264311686 278538652 426032813 216661174 556634058 380524132 407273895 512338414 234846849 368699715 363827978 730933032 615931519 830873052 388971216 818780645 847685464 832448813 818207700 535845663 781812565 216104887 852291467 434475209 707224107 640498362 896023669 958632973 596347169 844303395 787121060 447811515 521560459 242197933 734752911 496433841 752559885 411116136 301956300 714971610 707387581 284395161 759732748 205323190 885664250 925748982 737875249 669241486 549125603 747155972 316092527 46318005 313575861 206915573 111482696 614298152 854203873 472207638 841108022 47808301 663573278 673076942 545965937 545501168 884612210 918300517 133052773 843625075 220929033 816467009 683236208 345575217 384919740 817669509 525795325 471392532 977152630 117463464 631512719 610983426 428948564 704318002 400018510 290399343 554398652 3935257 453138148 553672872 463737447 822575959 661487667 735765300 141445397 436845534 858598167 325950760 344233832 592013234 966307371 284347766 108840254 528494736 732506561 540715677 505799929 744785117 538981519 497172936 550898595 435805466 520517438 133268121 90992869 384748581 948729917 620222244 399119981 364446831 931095132 119270891 754016557 292289170 28114883 185262627 482003260 16906945 329462822 762945018 537920581 849544754 93357891 595558856 452417304 407347615 683233572 321108808 702760837 348538199 701403585 590424297 442847323 192286004 707941459 991459147 478644778 382108475 274436248 214829880 350180134 726849105 707214704 103410400 371433484 587182191 372063291 347534434 127022702 964881927 68226622 739456366 443223423 22047064 645652798 501724124 33266962 455823418 343607681 221011829 684392713 527288793 991798652 423837193 718227440 915274084 333030255 636284547 712058767 136425568 547137386 242760081 382380666 317228604 748790776 261834685 244929155 130173174 688487603 339188059 431350690 221725287 492113978 929972366 46605153 644502207 248161878 415713600 918048632 379560904 698514685 209526234 862741788 79859325 863961216 341010443 833549285 287626414 11090931 389297306 151661213 524555309 984942679 91245023 162584610 526439638 331849188 794892372 605021303 714884739 733619690 418597032 94263599 246166895 996295447 843209995 374724856 423790431 683751118 830030172 286833586 363974584 209526524 806718848 387512493 819135572 262434128 36345342 702542389 791235400 237201874 898528646 368250616 44922923 487178590 502374311 456827307 149787894 554585598 923295399 791273954 170801820 758711140 962412815 9400306 212118405 75376690 154126299 530448848 208180211 997186318 886662016 748943875 951338423 620677734 603871687 748745390 895091075 565040941 447400501 19322039 840395198 23015597 549322661 981327842 909409548 716566297 192393898 286012171 649437196 850410642 955826071 167153386 71624738 100369617 834234558 648644666 398336763 742544759 573079028 258996134 994746901 165491569 310187809 175688699 776226402 476560205 733273385 732346100 433121484 799811516 890580438 157971376 1221854 64257675 712330839 853722824 162374013 974990746 875310306 67931702 237694977 979801731 832042155 47719962 814678642 25991568 294771148 937109911 810946650 405414976 890792414 81682239 688048206 115649741 574360754 905704670 517727857 928740887 769260071 319401228 318553345 736182001 653193863 661582209 57465551 535949584 525206614 395243048 365371929 750122653 398425886 920238853 675048985 173179933 444391581 101241670 329254395 700132322 666061502 876937304 445211485 727892410 287719463 922322040 685932139 451889544 576234527 891991381 245051761 479479234 618380967 515226732 681187504 232277353 437233735 763572832 543432694 899611170 511555096 244187680 33476602 74142812 247813994 742107671 128397819 364270270 483709985 516495845 235579731 5702531 399781439 978344513 736111320 643787163 137745598 492021666 799234358 108257514 704461749 708814454 918315583 26078592 952299381 546537362 34501755 277356002 9137025 462777110 417938609 821132470 961414492 657467461 43748604 988361871 963092929 642196563 965284909 68454068 865973832 277882028 195929630 809951200 28102756 496765231 851768532 833566773 802662048 285658342 296414159 164762356 509136060 439234870 649922773 540631136 894005523 791373667 33284234 548572375 791468652 677501964 249252545 394110186 240574749 902573467 686039833 201169513 299973172 816068107 393768104 186320076 369514568 471537198 75798935 543605776 198956672 359281838 584519077 946546348 46147795 935433767 898037746 813755239 367732036 457624755 322390777 567074910 985560351 208802563 339356478 731694750 808962176 443758985 382094094 998654318 314002870 657760108 796770281 985205799 92842852 199424094 26186561 725638117 652077834 943292342 403991305 269609059 671458963 520484992 338203277 814349617 609126905 852890342 317289105 216767461 393495418 795112514 524127139 500821866 275050689 746866662 259397475 851600540 993619399 913953328 524388543 576965113 918438500 784366823 848506893 365458438 674862778 270288204 285023032 648003058 815581169 349729445 246871888 837877011 340418788 819424151 971798017 459072033 511226185 170319160 43876473 261445899 150708898 552789569 545780524 301003747 572081517 585384341 145687827 303688875 519303044 381816672 865495125 310437860 987308479 466579478 414574258 67221487 536445313 596356923 897401267 300634488 524285939 26344950 614671572 173317646 62023406 420123626 27402673 79789931 395040589 469859928 335643979 995294129 486813294 825449654 295171824 592032003 197596421 783927099 64755333 635731958 516531316 745834871 579113176 325751072 489210246 796973214 584805538 472002729 180003906 564047447 767431233 404381279 789772471 47343772 229207501 473116006 345600206 676981915 547481943 237648715 133550567 98790141 372801834 778829657 613569595 700209487 239260343 75282843 254351906 557634658 817146767 826117587 94884077 284359190 899177655 710861002 197128574 302884516 102501367 754274257 632386598 431850071 235287260 257915435 60380062 401947389 862004468 639796073 802819679 813698351 255032878 68419796 228681703 444501794 244144822 257537196 424695667 168975373 860359985 961059515 178888601 359947498 771580449 726617509 489753115 888900791 461402256 226161875 116916818 418590580 521557541 69612780 754132160 679254074 634689958 399628035 207321825 595288608 314614318 127108440 896941504 869366220 866498481 647182511 187640258 462435684 759231121 307552852 219997170 12698403 292636697 84062221 967435856 428208640 958337807 521704482 426911276 943577691 511972955 616708042 876268910 724723033 196480032 184731764 62598869 691480274 673950612 117752134 274198615 303257482 633248535 73983889 1600756 409329293 260964233 352687144 699570464 701569748 10810580 257878920 813558543 487760814 891993631 287498169 106114878 705731417 82897950 435585456 342499087 468560440 182637883 616010368 816207738 689849664 813069962 964342724 94227041 584331024 819454264 565728985 617430408 676769286 465485505 625776479 296111220 121765303 815259716 858998937 155727934 344273959 601373613 339549656 77461946 839371777 69042873 411236046 204756596 188463576 21529455 950481949 645118278 135992205 917751745 81848601 873361936 294468272 411027 630953242 900968809 661640495 555240771 490026304 522104951 969287424 92507006 512167418 880865443 405242467 279881847 722603556 264027820 591531983 943840929 677028455 893617844 400823895 700937727 425333407 287062094 616610255 132065953 883355965 476787982 989147354 495558990 904992194 336400774 461476536 285612266 639645236 149151369 784414687 828895252 255128922 250822086 490922010 601843150 751887396 140824853 778675973 244611705 142948826 756944312 40175230 298550619 959805600 221227477 210728030 281195856 143208728 165096246 644073061 747209881 739170956 794167999 319426369 513626670 538496834 501238331 833619744 736996352 530216239 133150701 856161510 975236564 646792683 931686963 963969576 432945668 385884875 754055795 739206117 105700391 337312441 207565970 330551428 395944906 472458683 400790024 732913277 675162372 471688849 236755491 352233692 727015765 886957983 710440729 611243507 464771757 694490547 18505689 904175529 528240331 420133680 145253413 571346032 243616523 311257116 107846580 65962646 297061749 416291827 173965314 104727490 656506732 392285010 682561927 306218097 945325468 636444427 984815784 316572792 186077230 825018285 503721158 698962918 160743914 824493739 17188316 417296391 521945496 40093969 519908958 730171019 958148568 786696236 408835104 651395404 402803497 595352933 394110760 662226211 254110433 470402145 249500718 675647126 658455200 665054035 376595404 712274013 739551684 44878693 509566097 828872144 596814686 719686163 633962411 665016984 363031376 355189255 543560464 855534247 508302674 238858854 80896197 247822499 477019520 42984865 101635789 748461464 797709812 121573448 179080648 19164900 655245705 376261742 84148546 441426858 202062593 172343421 553396319 652942003 204119251 527072127 630422150 13185118 958747938 705159828 859213229 999251823 979969035 890431347 675279775 8751307 657608335 30266160 934747745 63470579 992099836 718917452 647464214 130380723 806309668 247940017 116992839 184217473 476991308 639091173 745898211 802052982 67147976 125412239 585449308 152804371 454438969 304088710 293116353 458306281 634478970 967274358 419537272 162902901 265338440 506674464 162839621 976117519 182205751 805431121 756174123 798301415 75334140 365083499 826630974 253490405 300206126 529714116 377048242 62588292 303833600 475725887 169800133 368815130 899642551 789519534 538905151 497129149 427914846 856371286 595338040 537564111 168294345 245660134 992440055 70481521 430266855 217331453 243017497 562061227 505674351 746513352 557339946 891987395 450573846 590484042 22400179 136205234 836828943 687328758 675771492 509862988 488909368 233355100 670153163 386919049 107201695 946756787 6374785 606305227 928626803 103728158 123599849 4334781 89280507 786338693 319008920 283855217 398827510 451757288 882262841 348534484 161230574 54267962 870478236 643774186 730420491 722390081 312309105 291164301 443416108 946930053 367310097 771572909 871863384 509081214 354598255 932712810 514184318 993407093 326465055 13705292 950838648 649459667 430726615 596740322 647769362 466099741 412688216 534380625 899988527 51248641 314166176 886680910 284819221 381081161 623891092 27675587 922521684 966704792 531857810 765118599 852247877 586251963 925248372 462631506 881299156 998979913 472866408 501549014 972976121 387518137 861947121 331994744 426239957 76987723 53992160 228064855 731337861 917882779 791759897 954537822 751284316 815690561 914530344 859561949 604884520 78198609 533725032 437695494 247683023 429597333 633283085 454106282 609390405 505189051 296234316 284128713 806778118 401467736 107875788 84006900 975166273 642029591 336688536 350871903 658655286 334619443 300771754 283595291 188734237 687072640 836750373 706803305 115918994 486879203 672008823 964106658 549871901 26253225 323586037 561334516 598948041 43951039 97004216 951810867 258190829 59864872 710331795 327502073 967670647 469348573 764532819 450015526 334038356 235825600 683689082 512163830 259319555 354572032 624661138 561822698 283948624 600572229 738372223 843613964 1844407 212245220 93439216 676863360 677518699 834838926 145946671 43501296 335654929 588777939 216006558 199064306 434643187 848381094 111397436 534747371 551524279 783211190 471456238 602464144 155271503 515305100 354870465 550905862 822309811 242004299 333122732 512521913 57803986 270553274 383671479 681208703 596431991 88360786 163839886 974770346 140328602 229426804 679122371 140024665 537659665 441566410 454905746 141397266 637511134 314427266 776944307 86740135 163696875 222771857 306241519 32835868 220930222 350239511 782293677 968868101 634901444 917841634 309602781 920062322 165031341 192226563 538132277 202368817 428573050 484870094 13495752 703820397 883076081 236118436 499884736 230081253 46140084 807460583 375421071 92432785