95 17 12 970768718 332561367 594671250 494420500 157549337 419086247 970509931 625513196 79090400 17637397 938352457 153549883 65353571 635556501 555408975 522509556 883504217 30761175 725013607 60569609 686403423 108821827 96512662 977301124 618172467 112241804 466999891 264711610 395606588 493360540 840850895 557464984 55135113 541200955 539510622 281464990 962112958 398660454 329013331 52162896 70673504 992695279 223277550 415058402 242103647 789498416 459817205 309708088 849827052 38030743 3686885 96951174 523756137 316537957 850626400 74432233 428469152 71102031 660999105 931736348 280798230 62554047 539006629 482693560 229451571 570214795 350365446 25576181 743804980 324202728 880643174 539455144 885489253 380693558 218122720 973829671 964801776 989720867 211826746 903750580 64982119 140876628 859044059 528046806 933692339 865124682 379334542 774245914 625612509 435714332 763938859 313912569 142954995 404384883 645721039 140193377 414491094 341529059 957319517 599677967 373664783 259266362 31081641 959416093 165391290 383473172 661969001 127508721 623583560 25064769 153404502 746510339 35655652 686063144 391880084 547003557 739726306 879732792 5911897 614650584 458255011 780563839 791413311 478837593 200044859 40863056 992782314 702755565 488509748 371197728 146216352 561960259 311812890 41934027 216729573 264089673 850697850 537154611 323500350 937160841 928957135 370705133 444091047 222498004 701565405 61173311 858075834 494612410 153943567 620281799 83620688 963184330 447194198 787327339 240617244 474705528 658801548 449192385 10091375 476939163 420794560 330578960 770631532 499170022 339856420 13067193 839827563 790029775 823691025 182544272 181786695 437127993 524255273 154255709 834574667 972665803 995589608 187244186 114294736 349445336 562712363 220442602 492038260 630233474 134064693 56053714 16490855 75702504 714977440 471074369 784612684 221514800 175930520 454301373 235466427 505689569 437406348 377875241 141459411 399617611 491117346 865578117 804748667 306908995 318417043 600565659 112612462 941784692 116088822 944858958 416794976 53072255 862815329 996834500 157875399 123377802 330677775 66628977 413005502 57939238 352963478 309148838 249346699 579282889 397389227 65838482 62801576 158954731 507297807 364591043 370596013 697205630 305571353 927239778 794451088 392204406 385429338 387418850 79174931 510264444 631558827 956237023 306354881 990942953 299519610 119120298 944287220 540102217 916910534 111233725 752757149 949862402 482911780 774460205 825332620 633524114 368404550 479796669 795477809 541666883 559447611 498327539 765964611 631560848 531699919 814437563 802213213 995027918 793761410 894028401 299160753 506800784 323512080 926425259 585965392 573728153 579396959 252043985 199612570 396974106 166850268 158131220 581054488 968777313 121449129 462470070 93391802 165976905 422974895 543245454 472163568 580246330 555905785 535622041 858396044 452976848 76629620 647172789 497847745 421787983 574141039 358651651 662135856 578697453 970839044 230479477 805071590 687175530 429578288 949281711 854414374 411449881 504093519 744817200 952161807 355507534 745152700 475126598 197959685 636990735 197810205 712288498 249330402 697395495 887942085 948256631 395472654 360031732 818930858 188846102 565757578 140037092 461459983 551094667 433097651 783244583 384307609 202856829 499652343 841246107 422159316 845930995 434749625 746613791 545226641 626537935 629073966 462815737 49216427 485466533 814407629 212955962 134126973 999671391 491913265 69760567 489833925 558839586 243444467 361210239 869487491 541586139 794890232 876849407 423894615 464404554 149296450 422535033 543348143 904551740 447103740 178205957 917715748 258143210 178837346 518313554 541511059 359185470 341397349 53371389 30213523 998430119 489096195 603181015 288767930 480029134 338579254 711550446 278103076 944451801 757326911 30664108 389227779 117481330 342028601 152311539 747470232 990059444 238583856 68842369 917950681 338707685 351350822 983731851 299580759 942760171 885199429 913466026 807713716 228869749 914498530 826104027 790712094 701340261 724777703 170212551 754214216 25217903 711909364 810086402 686598038 809489888 418314279 856660993 732490456 695330247 527039961 46585390 448681556 306084595 166223977 917221256 52963183 464536033 770807701 49442376 851311166 395654915 8022065 36190400 526636740 269953323 614098190 958848351 348589704 116420517 353563252 980876192 333824279 71267517 829237555 240746714 988527953 38040172 660625319 151819990 440910767 635957103 588209746 91696695 975014672 286488997 575462178 342071744 674704243 858342550 586697047 888515474 263193914 137298462 187039707 412950973 39762560 986115222 59505145 911787415 132289618 921713656 491957292 506225758 624817372 896427406 302053656 608130825 258023795 894815913 976163073 854323059 398959931 658713315 64808758 133178855 421465262 166554150 279335765 339082008 38488948 131662616 474761841 74836437 451022867 629395564 652267026 331529863 252855056 387934324 856427300 679102643 640192071 901109342 290344780 534948234 861532773 438993403 846294851 874437831 4328004 69456320 607693860 910609119 273399272 180371627 219587493 619010088 281978884 524107133 335082826 276054473 710079861 518914235 353178957 46629362 856915310 968896597 482885471 843511853 791514134 947002553 56271314 676101730 766986731 520431375 545001522 430232473 564713756 702082605 537245581 482730674 569670010 659267468 471736491 151860277 379708631 447430895 178595596 256821015 244600231 108889606 37833934 915059193 995961356 768027329 79936434 321472932 863303027 241448549 886103448 725065853 828727455 394336737 11109312 371911929 282822518 156911215 432370461 688783511 718790434 697540309 348525519 364674835 953104984 612817838 169618411 562455605 753346226 977500140 114263672 290464119 31517551 218831933 195883407 714628907 359457670 198292119 149799379 528465589 825332664 63748444 982263835 240773255 174184457 632993864 969464853 933656733 956738343 33083491 790114346 23794085 680201859 932735333 880646097 801674966 341740520 646987403 308746283 941069505 768325230 705185364 815123191 301311598 704544685 173698365 473912285 321367408 52609054 153639851 988732442 550217328 316158635 768422093 72667754 624458303 735946440 989544681 844324427 644304892 953809283 696833619 631636987 908603038 891654620 506827242 847631108 864040168 99881015 232675210 541124134 157352197 398227135 730108308 11663779 537635770 986283602 921816313 265039445 139686358 542939441 900940405 909773683 780230267 653516990 205727021 289638490 393808500 840806465 339927573 108879193 271542113 679068220 144507139 820003424 884309957 189205306 729456666 669515409 217836114 716740246 986213822 721737071 395460012 365034869 362898017 270900655 960493094 492565648 478640085 856984910 959153021 538783401 816734132 795564435 507860413 294180256 460373961 632333121 258009337 13938723 12563510 939643911 85093411 231207582 165134800 359502913 25246488 554790493 543217529 862961296 980876109 608737686 220367360 25730881 181642326 117232179 696458057 995294189 249862636 386852863 527719627 100650709 859194454 87400888 562159667 896999931 617371575 819606027 384760157 266383674 299604522 330101617 832081790 209370671 702604281 925521632 432120514 189958592 700772102 604785351 502124998 390017939 987510283 684367289 671847519 115185072 382761564 425884262 887524881 53171561 941225298 889264508 689258961 326875702 307591567 964647575 53603719 719505983 889480297 870797765 188331140 246473515 17047141 230739608 571831773 919778600 804853841 987652294 964196658 790230274 842800466 756596054 168715381 646332738 812178978 54351993 264533767 741492349 690337391 2639529 370482310 878709318 295187795 157770810 442739373 62471099 752719165 84550708 842448691 677602450 338039219 989303660 984427344 556235127 624315673 274693822 816040822 501308429 185889682 104174243 74990715 102662405 755762611 889259149 828539918 460112886 780359227 728621170 685796270 637091789 65405211 423060906 325732493 565982665 601374734 845633450 453710643 676683269 933106748 6718820 278980667 63383882 299284074 287787049 751615230 848593592 839891215 768376376 116657123 987471294 85953765 381973858 234969537 406206589 578596626 908129054 488964984 204041590 527789773 836730400 172955042 214739698 2449192 955956538 414394372 31976728 343748169 169088235 504704029 881384148 866181295 820980507 422012722 685345017 814421296 59395945 752244722 197485110 54157806 31249797 428166542 114407956 159350544 487829942 85424067 413105588 572203137 289022466 290648913 566162495 82228092 481115225 625857188 679912896 235651461 926923325 768510328 344012403 882923186 538855486 495631579 317599633 305485714 728533388 294585487 731523806 700104516 867823168 269805100 421693190 723776953 487382592 489257051 125851128 338214333 329425506 630338209 294694319 288615041 332397252 707484250 433918893 571285034 692515962 400194551 141972748 595090793 379510660 662380168 273454777 50244061 600336799 813465734 559275158 852339407 341489073 266302058 340072444 368381914 982861068 399635239 664507336 717343774 962489788 791120780 339203185 348618380 614545407 355020365 206943414 881086266 863056676 712202574 296147168 845324121 621682321 256555945 551412612 466376663 327545524 426394759 957972056 724534184 186900149 139358933 560491010 286693800 452194267 577462933 767795940 839905990 182966283 462101049 156435855 906076960 372831740 573343056 885204001 669215469 499913221 866948432 853793803 479406158 4616023 5778625 64044018 990965301 852284459 893291171 560701180 750812258 13422531 323959930 48022689 275241763 46946385 670337563 560765832 648138538 915347871 798307867 303627200 432877399 707270019 72857520 432641567 173794773 266502868 360148431 892580483 691104881 944642089 525207034 238118634 618421110 504500278 331282398 295070245 690086325 867694160 6827003 144402551 40535502 154565144 286828701 753370811 354329672 160559200 379727330 554937981 630870596 711946279 948267454 634412481 712552548 251999824 555892783 287731836 612323457 131148479 851473145 980838287 737282249 969473000 7094291 957873162 581689026 687977153 949279870 384719267 70006213 830109114 780257928 130384815 452303738 191077425 886738026 207628042 212783529 746319164 188025440 474501270 833079699 94091768 353396556 184396828 345355530 539204404 91457525 994734968 441248304 220278417 877711321 500229534 719125995 535098246 781042083 965072967 949398906 869265777 181368742 548139557 494090118 981655964 587045445 694795386 726935484 710754040 376781565 786924154 732723942 407650163 677178441 243335061 278321040 799851569 626402844 860259844 879035478 849003787 733324488 439062984 242963962 665944881 390169406 892840797 446061627 4356111 924241945 291186860 506892099 538005176 90855960 281521657 289236223 381855720 713623575 178404940 420457760 646855628 690179041 448579953 497370726 785885324 491888837 741810448 600232452 84018702 219401965 217065395 747772607 343512310 910799225 837498640 562407970 292769082 853931472 812387919 523347819 55552207 549410994 94761700 239003184 691356408 895118545 148696688 434827210 449524661 319524151 719966123 83520039 173408761 446265514 477247430 914816806 625524541 749262252 494889614 183275138 701861107 296625718 912884992 431324550 3009676 986686532 902559260 923174810 896470793 296931146 291481928 165612820 11360537 493657005 11904705 524797211 887467142 710703762 75680523 775458093 910941157 942867580 850868005 844873583 910353626 977271409 314828307 522353377 858226194 913209395 81921059 492069014 842066039 689869859 21014948 834504139 380548507 514545467 119823120 116655585 589388178 574025894 519617010 87773848 578348562 702227448 454643142 103887022 727177161 696045504 33620420 232910391 70217792 991988531 554060814 959333232 350273472 405478980 454395666 266004314 969573580 215656701 800347867 642410478 398928381 59741995 916148406 107136848 321733699 524864380 931068560 327045189 445286302 809172106 689564133 849157071 251039242 39571179 917860420 12544309 1095258 204105403 926311649 622995823 800852321 319619360 283501573 43884585 543359567 601004903 180526836 296627977 56572910 581677873 34659118 760731279 558786788 89936708 131799515 547449038 538025108 493863783 230268471 608993895 366569306 453088957 240363789 949872083 242689036 416027407 592409742 780784042 726699149 861920176 193092297 821886070 973075391 729488572 110821465 140948191 511214426 149696253 370649323 983404598 509543221 521783487 821903248 340542203 815372094 100856836 489408308 118135048 355414204 254987989 569192127 106920853 20690774 681125738 515378333 647879242 212536712 356341172 506322246 536103537 459767662 802535824 107472259 733698033 238876021 639046326 496867267 170372408 93329287 525400367 284502373 188827457 710143402 842955794 406459790 725998200 107475302 71277629 26339245 636717043 577363762 633985558 925526220 953072417 561200154 766634229 176663410 988883253 526413663 514443531 745029921 305972484 834275 56272966 565560094 461299484 779939244 851761534 327636676 779297662 570837411 752741549 524538840 298111784 788838810 851753652 347795378 489630234 528854440 414393276 459770930 602076658 445715234 724945121 948862252 224881315 869704732 960857251 714970680 711649690 891942456 737095320 756057052 542821567 394755656 662224103 990339193 918655867 160422326 867028949 533593104 269063674 301394602 22176182 881396850 198174984 804180763 96277499 501592421 656186686 87806097 908179694 387853802 392630989 458440698 316497461 857157536 699935226 132400374 133037627 733150887 274451675 423461755 990748412 682798037 694772002 663440183 248010871 346970720 349773784 54447387 746556085 792462660 258582367 657067299 670654903 58360198 219532705 144049357 238286680 557126786 5691233 787209618 446122238 364484275 554528012 824910263 864733265 68150686 275323918 351310666 302961784 75195289 998110020 390029032 547249331 293696495 390713185 92671673 813424306 318907104 832211775 263414476 99569224 234666005 533662529 919931936 368968413 91751230 542643226 626399820 82247142 675403374 656207414 383639118 765496631 438813733 574608108 980393654 866231355 618666380 905338436 97166890 378556064 528615725 517996379 902113898 321549673 180562998 225653696 713352848 140833884 819079082 119622776 989437261 647858738 294103846 377946289 627225367 296206805 327975824 846823032 184727455 942387122 847367804 772604446 438592871 53685261 154376559 593460653 851742811 112251272 361219812 59818074 906348583 526608104 409621004 73201238 569068317 65786961 826297781 202719931 187305435 100761304 934726660 580930863 688436574 431738059 640952865 905535463 879204380 647390636 128839621 144125591 766146927 91523212 829436153 924070733 464092306 955301077 636089769 849121060 419930661 440025888 842741454 157571121 787944411 984237813 990533021 71423934 719388819 50607362 595756073 514886656 128141520 48629720 563035645 983777322 77262397 571078838 855085676 586189182 453834573 311206495 646841291 862863123 360401634 866612433 94263918 136448394 117150248 679113971 684920627 612083396 10277195 607440490 2149069 610277772 649102097 308165424 270250399 784396503 232827252 338638196 134627037 671200673 941154494 841273894 466699172 193982791 680883431 205829712 395635877 986464778 751428109 764695085 638275641 389446546 758799941 682194214 271676333 256219312 737800612 766554113 832739355 172182432 731959471 983226248 73943212 581554455 808526238 149811355 750634139 68484711 900361927 342760704 890025481 699069803 25707809 409428392 828506480 419333384 224067418 105499577 163804503 605639246 591076487 262650352 312554943 206674970 422321622 726947839 865104888 514183723 328832730 893632540 236914863 13033549 607033614 40345137 578312054 378930523 196286769 988676936 548587895 262503610 319957687 286149396 984329763 998383722 548864550 252848954 176328812 94849534 484037887 420516145 118173034 961321604 986927978 909759250 193299837 545357197 362046751 545732606 607122020