107142858 153846155 5263158 529230773 562500004 669985780 751585629 111020409 714935070 521946064 532923621 850055541 92405064 811217516 786908749 172733012 722927563 951125945 536731638 691234255 882381896 813488952 144090443 805857351 931683520 832137392 626664676 94465716 240259742 167992230 823415639 289621283 507135682 983897710 723598324 767555918 725976943 422897288 45438154 814546832 716207397 925305786 489515893 886650595 327870634 526842068 436669490 935258329 333944116 77864074 855831471 974929292 472805646 623407272 24897172 727652631 188012748 801751950 657224249 909429002 703411923 432323554 219719485 255635558 314421423 275407265 984251782 591830167 435820207 802681502 848672553 464075524 807330716 115231522 364323139 645963331 264429882 998702543 68996020 35256770 323223485 27420322 346629261 387977931 684962089 48370836 904266350 437186578 430464503 273526545 183042209 245330689 981676470 792645179 890769482 143625603 582696966 775672648 959675152 957678516 898140126 801159466 184751682 519105435 976087792 561217112 179873073 598634590 627536776 297617363 281194734 777805218 105657109 368666343 607747844 465819541 773842628 137138204 856545695 483811730 503922491 870168884 964824642 417906691 54919682 736060625 181866840 870085967 977386106 295263796 589148541 470511818 776883610 198911889 414607038 240548493 842253660 260429900 94433144 756092882 91699896 2619217 409540572 891388224 166348920 508497340 584233105 209140432 64495212 608141734 997926074 49980707 818782236 614208165 457235981 304039342 435492571 21611669 170978555 44909474 535497880 595801216 330516356 710268639 763850466 425617537 922324666 548326452 532291226 970875803 399236190 346735675 169341824 377212807 97755895 575427481 349238574 937467987 134520620 709861655 804703994 519687361 43828274 505060840 955656004 23273431 222364474 275397605 4312217 755413191 326708975 158339109 723530992 643960870 696085437 677083263 94360422 29191963 924210415 859856116 853031714 409812156 38034401 937576995 850881456 809648133 639811890 326330827 826325278 295070576 651258971 927775407 697581123 111212641 274997424 317190437 821874020 284929352 822702746 650421853 222728141 262286713 987094408 765053558 221913202 869764919 195611717 769795210 586997890 216813674 302248755 455567449 38386603 272862113 703153897 517881302 631467785 979742308 621635791 111103305 595249463 874572465 869146635 59785165 812908261 707075478 515237384 218269098 725126541 398464941 41025172 19153248 406891656 482113318 397586522 773760045 592258541 619331519 507459976 373021663 396927057 428810998 658622270 93746147 884873778 755017039 578132029 455726140 613723451 565016347 581607370 497468450 875542797 572185684 986819940 348612061 371296663 978324006 294838459 749911763 784962796 269960831 421834300 827680815 955491412 95856474 551397569 49844710 287600103 749533608 717338260 230751520 986699578 109817485 460579467 90288799 654273424 804120781 801397106 9646879 955078830 704620743 850214772 857807325 339869642 209651329 579830117 746783219 13535180 340443881 756088223 988435911 814847197 7572199 230420498 4454374 553175662 107546234 335272028 581293566 476642259 808130281 190608403 955999658 315275481 311359189 981733357 75908563 326141549 782471833 543215006 25291127 334413209 337578290 987378570 375854791 978488496 286297943 345944983 761526326 266367323 404273133 511447261 61737482 636167040 328568591 787933215 542910808 335194668 451227297 244613376 733448527 145383637 961839418 842910389 131431464 44248543 767016357 788182986 478622168 107750100 861705363 875610820 435264145 22948892 696999346 565848587 989656472 940820308 50112846 779869068 299098212 980656231 854690453 986962186 115225421 809969573 962030671 346298695 562761159 919614061 748914008 54103675 262156820 51154476 868992109 581036900 544471742 342795755 306424556 929671362 841663119 238858754 125171788 857506000 666637068 907785016 133074010 799481396 447286573 169356543 192319909 645940715 513288179 115093692 558444251 517805310 376002536 150520444 463491065 410099212 307622405 915929947 653946208 255107796 268887599 105317709 777694965 403625942 839254786 338337101 961158648 442579852 132068950 923411933 133284798 926971069 144572296 922782374 753558678 202990940 475599008 933966325 519505412 250693997 732259227 906503684 65080479 206468315 726207676 79781364 488507561 485481854 247581597 434627192 642041872 363528606 282426133 552176526 400773245 941248665 895276468 854610265 84352515 128730219 277953315 973800266 541384838 249439601 69295067 659735617 394838375 479630635 340976493 681178455 280685450 423949684 114733401 561990356 155190733 434971627 913615897 602873462 129668626 790810346 86947875 949653357 580444088 770768585 215545822 778474915 765577188 95560182 704812767 280603888 295216082 287013279 890968397 214892147 658929724 647641582 350971359 185958552 557462374 526092292 854400646 111074463 803403343 249815560 396107363 315534146 754224070 963114849 493857645 401781419 74412941 697088560 462756833 556854701 462264889 194569437 778475027 404603454 100338120 542697306 919621715 498507434 572503854 649981357 469596654 934410066 44060683 908064768 375524175 683962231 188305170 13653843 137285594 108828022 533904466 996400456 368182123 724814791 789935608 792260266 214134321 580369541 163892435 954703946 896126536 131216994 680981921 142731126 76225514 835564674 124310302 362684455 198948509 11318267 880761136 365495275 399492793 654481504 372255054 705226797 760232653 748792383 607789721 418261044 344121545 494867401 208883933 691779198 39781497 50550709 953593724 575323913 142929748 644233840 448914476 954984431 635892243 739298882 562611037 711949419 194120346 688568501 280509546 655744224 562993400 359972035 211763622 931775126 537482518 873180878 497864433 178494300 777121019 111518942 692416548 133543790 498871581 394838851 638740989 490662780 362560914 896575726 714243232 740739600 263538679 2421382 490896877 277626525 927960902 54882880 623053367 961750931 492034526 16664322 337045940 786549201 897312428 732023712 623507780 331483600 946165996 708489240 85747861 830133277 651934990 557733214 211883016 5141928 581753073 539448475 848307717 950663989 801095780 387262883 198800791 770563114 788406388 38859534 831726383 133087438 621276467 222749447 104748495 234275438 112970267 42121004 937552357 992936511 491036398 388131393 149551122 14832141 736497846 436246125 974963779 327195318 557476419 174889993 139332428 875711575 304173931 874056220 409264582 452283593 417529650 721639519 962328639 410287429 192526416 922221297 598424936 33854230 712421620 161711809 506350119 24004800 4332256 222596027 816629777 902898953 346576079 359234287 792064413 356219561 316101879 999220963 531826656 343402260 55678598 100341497 414774361 307179123 208209225 71594798 772983389 250710220 293244637 722766665 521156522 67130415 784912322 516267478 889744997 292917600 78932047 353562009 170511845 871934799 159110831 780916269 366416868 104866185 559867876 723927185 996880359 77144864 416016888 450464672 766487296 114562373 316636551 368034494 550109821 326325717 889074285 51846571 971011479 51439150 477770126 677816210 904362206 998809259 506220185 346858190 64774543 535060395 610608121 382823785 282579273 67582425 504587971 900355660 315844322 2840346 514846263 636931296 494456650 408842300 696640392 758778602 578336922 450293838 231678130 269728328 932469330 975582700 106806400 147760783 216231328 572447377 994247103 185334272 925305846 846976141 370793843 317162606 383044968 64756612 892083494 740456071 401501048 607237229 661976737 741200709 742360128 363656710 510706583 698349456 15859100 447162782 252703057 911709979 415902055 809673249 250469307 334335187 403153182 716118147 27716895 302638879 386064478 973398242 986612412 746020511 72516632 838201014 36836554 671291728 644249958 555658905 910917947 147785462 407061680 941525835 610365001 27027626 911385707 761401925 764178924 280460014 726586006 450516323 417124333 215968186 915089600 210548665 190403421 179307438 914948865 308218428 156149886 594663058 133725205 761041039 463945705 871495595 534636118 491243539 828493131 621063160 758475293 338533677 780387867 595542023 815385101 555340280 254087322 278134989 709128671 451276628 265442416 427784107 85553255 589522276 164711800 202153954 666982229 291360525 980221985 388096291 419068134 7311826 637295979 478854669 361390929 741082730 211363507 661516231 746099755 955258440 374143716 858686971 276292090 496969436 420612349 692327355 618200077 753427457 393871791 79916972 939761403 944427060 565042421 525738347 923122027 808152426 22499042 863617706 413645953 140817918 991069387 771321215 638671508 275704345 877175733 23983699 404708776 449108735 334326053 214957648 512492415 301567008 164889626 564368710 831549085 305452042 900408039 865446890 286476693 772907042 987277748 638770069 304326172 681035832 845518350 673839691 96783381 191141870 123386121 407488080 273704760 762177879 544206718 601265759 533891435 588590669 300086166 899564235 392888705 880584444 648226065 890110950 524092538 716893151 808173480 109753017 426612585 222091857 196041503 386156507 107640708 114677792 785761787 133390380 801166835 465309914 803603532 891351268 632506975 900148160 340154582 642422700 109159842 900849722 828630291 496774846 571008658 732140746 128829653 246113465 751589119 216416037 943176630 825705829 352451353 53895013 890068105 132586631 432352545 825337116 725075802 332014949 703940471 904558933 423166984 226985430 347354129 882693759 573764173 353407271 917640139 30475456 745859789 4159664 367744020 812026217 964090692 316282111 125432436 252505109 374808260 309380237 523151387 832802752 162146370 821589442 773602442 105168185 633626796 470958829 749369608 220147191 135816949 650972921 973744294 820798928 644577467 848212906 657988736 427285354 432353410 401264593 764485424 170200207 881565841 369900003 272590154 53324559 928387008 18337228 496893601 154656746 918469946 816249015 869964459 325188105 112198581 525933644 390973683 365337415 324094158 696467879 336007992 59704561 327514521 268538002 564770506 436296447 676273236 430513180 9780787 401453577 456609916 94633075 39581365 947698230 650187119 403410939 730159858 848849920 521682864 987818518 592943166 151491826 478403875 882322010 337643612 249632344 707138508 308348096 716796635 942456141 797776103 637303278 992340896 310264825 79472836 839558033 769844260 229366402 417446967 166804197 38763562 747883969 114325740 810778360 439756844 172220193 498752108 663489251 363931445 139125328 410879210 433874214 892462250 888553199 747995628 524022517 494464554 238421714 587111909 320731537 824733505 328879626 315742502 931572372 977223719 658644293 416219264 709462326 396694029 643318158 32521243 636217006 300647082 479350159 222891199 870181462 910277602 340616643 576319655 328005733 612582364 457322524 306280031 926563074 415837345 420209419 253933971 899943568 697466101 232348506 667384293 576166915 265010738 524425791 506441522 51937452 345413153 178650965 294942111 867222525 978710261 482427359 446372287 469387709 189629923 236705932 526626858 476865715 673385102 764963843 562049587 86953383 713212289 919396796 1869207 730109116 305196748 937627803 424669886 851706114 68211951 447685698 471058318 928496850 154040642 560601428 810278640 125484460 397598117 622831021 734587384 329541881 884890252 592180544 979892385 807612461 300321102 666444388 310310859 20406347 361860037 971524136 710186540 806636174 264617457 568704289 145559532 380295453 554110808 130085161 168723073 603478395 500162989 296425948 671859693 490033540 833526468 473935930 806795182 341212519 842227864 85452108 607111826 682906423 766100186 266213946 9144342 851599340 194342244 794168527 765919413 449355716 976400640 759349599 41674344 693517552 581742904 770886852 81730381 244818551 358833667 523994194 167637574 568521715 153638828 130294888 286426195 28890389 371883455 832028965 599029457 358219460 569997915 836904399 839246175 713122991 676891571 296461312 488248067 611759229 927189082 921112240 661923863 697777558 806452836 748776487 877733241 390373207 150793477 97884373 199263749 830489404 479837099 775322479 963134134 877959812 810509073 948978973 878367944 703804094 64975900 83641309 629121388 884378086 728100367 625084160 947144868 682372282 586170053 103010868 660539460 576153939 468011067 461312067 234049776 211618994 768737270 599062318 699620106 984824711 74015713 831017245 655834538 835359432 356686412 160152048 969990665 84758803 962705247 252653405 713190468 263458664 437400937 836847436 447273631 969436875 154763340 942254069 455942611 451795552 738134973 79277141 2478452 702589728 20837933 640848243 93848964 349282268 260868549 594060515 947231972 217330369 804115689 346467889 136465175 24995903 633155863 962350287 964265243 56148959 652605626 220340239 671410073 240418640 726641569 546864367 938609027 146599456 647958929 769124396 830000030 626975231 180317581 38202921 13695753 724646884 665922240 351629892 964163810 623044045 183893917 421087367 991662030 648972641 567183985 218889002 279844781 834559274 648864709 376637321 545660937 232320423 909523773 843580355 359371079 702561743 964326231 312951972 138637383 986339920 37333727 507575265 289088526 223130649 875211028 729855234 398509549 731508069 943678137 306133435 99807865 737213394 392619330 176393576 695373547 618324717 195850180 417141015 870919236 811930000 261652895 670398096 177958375 898414413 649439139 157621153 798602046 521628891 643443095 309079135 381819478 785118614 856937495 177702522 146447727 371304210 240520500 69849228 545849027 509731033 849339227 189696063 264765438 858719317 97719645 682537424 988866135 835662606 751315989 576235714 236567231 849844093 235204021 988109612 984626262 763837140 884947991 846749656 527926419 756236637 161378576 589137949 369165591 780802285 737602309 45114492 304040652 959113154 721582239 941648369 84215853 97627549 203267237 949789372 367760133 580621349 503544643 57652654 134886179 734963308 329352248 143220853 718982320 363792585 602681468 277151246 885838091 464324433 203050570 338397996 431261627 731399285 123638911 130440357 776062076 725171162 260280568 975237882 502450389 108656214 524798665 96813559 872312244 580653187 999827619 696733022 192593838 901389083 802183597 866741102 49698154 102906682 680596491 588561388 348721304 246432285 33462394 852639728 373356822 174559230 692186722 623448268 695633325 661735845 765796250 930684420 570896382 756915405 516192538 592616572 209941686 987057200 275261940 657879066 838914187 319936955 953975816 946589915 926402872 300880001 472707173 259606530 506665871 915573499 990981797 679517997 306606371 864155411 56431653 908026849 24911745 897771953 454174522 346313884 456394066 820637947 647359013 99903010 21807274 437260108 687381851 427301390 412298630 415539754 812658186 925730155 110769784 421500681 323294279 916819279 286963161 349228712 98383775 483771170 527469798 114360872 733833229 491757597 306277439 173947251 170834268 994706792 364615582 649880422 23354943 546364697 496817038 14916252 462761867 725416447 169615084 990442072 255045073 327988717 442324944 210229420 46541165 103315433 778002142 398904539 366083191 69930881 651565970 668414643 662493930 963547857 700100031 680890067 892908542 436990621 598620619 70569643 981243929 867275775 990523792 153612952 532549518 458490874 951964290 645188445 914393546 181663566 691262023 661078080 645174752 98182129 726671287 164409449 111552506 800564883 385952184 732330278 693285226 906390683 356124450 227847832 493005044 924002806 621629801 843223605 326554493 109677192 614098853 534353409 642170597 885927511 792234916 572060936 187575140 201331721 370532992 201733658 961345182 584274580 104856978 988582144 551716570 967606981 491111043 627510657 605855478 758247536 944295800 626202146 392057881 777900586 481205721 671742034 367405442 411638269 456589732 117064552 773473408 723105803 580155401 701705520 613954354 210738210 925267538 458422885 249548618 250213582 339290274 597874240 722015556 789908430 140427076 805148850 860382597 262015426 673034698 597161598 235725452 678340346 56466864 149081593 551695095 981071211 806871797 977698858 448950254 61129831 576248029 988970504 658381932 267383873 542856995 822678896 49172436 59018808 571290815 865719534 235736707 390037465 246153547 483732818 898892195 401483236 204892790 681493536 723131252 645309701 920047592 203062856 767860417 284490959 652219324 933351694 334524604 30197528 122883565 961714126 47801753 574138468 906798664 76573872 431182272 53346830 550289612 999547122 921634991 74606369 829179713 739886672 122329420 216816435 169779203 531211023 984287023 14863397 891993502 362936071 865476693 671029826 636135407 324633401 80867441 590310740 972266762 353244923 668446414 216602024 803134184 314751883 510121956 304899787 561991073 691479951 832773221 623083992 725512486 817242600 93531493 413234447 849447518 689491714 761362996 950250226 932454087 685579465 919386682 554245449 861162907 636792777 164689109 522872779 80258337 52249877 970812609 209052511 542714788 637282091 81030011 971251231 33252092 300209272 591056225 759634611 320512288 629106321 469768830 381461015 295217565 261776440 491576398 712249783 478127224 805627898 968549152 78382567 28462603 408328024 807413793 598192828 595183804 978211492 256248332 295176123 633546056 183513708 27546754 332916865 554386113 628381000 22544398 64986954 372086615 525747214 463971703 369396536 333269414 379444349 53775083 922687956 964708055 317787813 252438475 260081219 830209549 110468557 529640686 509704924 868524594 956167657 132687246 808261210 702054079 219135611 803948406 714245110 296337929 47503126 426455973 431731742 984413394 940959821 469442743 576027673 741641740 839082028 431137525 286647088 138703877 393026454 923497828 742831799 129488783 382248309 117211359 274574848 922955773 571046033 312850798 290936542 339819200 219890998 715698374 84523586 824331135 862160930 595858032 140721587 50752991 451997833 508970197 202676982 461067182 395774854 392232742 189664877 561632833 906484261 789190409 942942464 699998957 704932091 516256089 891097878 691142403 474832114 344247063 288697902 800315827 667217325 786690689 790870844 562356736 3412536 631522031 880486528 505389605 926337674 406141010 396648807 266999148 364564227 260344540 765586910 261670176 52640557 196961684 290321926 997253306 716472696 109417284 141585040 531032011 355075420 690807197 302124422 790776475 327911488 835419467 864762507 524497027 790669479 750499827 196035498 841198329 871420151 644388733 748584177 871895415 837609899 583946264 490818301 424716936 896519907 212194603 468141244 1128653 260401367 263960542 677279681 801863720 235536002 149204657 416665191 955052572 853299993 743513688 290740934 288636045 293342432 629401039 36031518 68069219 776852251 33648622 240568060 914038429 486275984 459548047 356935154 933267371 821820273 262342652 810938838 616256859 96962542 451322676 625111628 661978047 153080198 531903157 539191032 165605650 463915708 59931191 38893099 2284973 862195051 816051369 245449435 549587542 71539929 878530810 380614453 720095198 886148960 479624304 652393865 735456321 583746964 404359129 567291548 729235503 198066431 170997088 557254884 861345820 361611639 230389824 297891319 634093669 934232446 837624902 979015875 651998906 370910922 350332179 807930242 814673778 98998946 155649016 325435883 185765516 175246353 983286589 253747839 122857013 851480586 657792380 883633013 440156408 403292060 509428437 738447870 771968187 726730956 898552868 698820285 119062652 201302360 585516775 341328413 439259294 91948050 87208402 672218922 619167709 728789001 934549885 266526236 330841151 725451574 21332868 97098935 213869749 532314651 439838931 107780314 712366743 118766654 9082704 194696701 172911948 854838722 259557107 524304456 410206149 840592970 65791498 259043623 960944474 412052039 751964223 953523800 902456848 212167996 573491566 580586741 432613816 121538762 639786414 190556184 746733334