57 100 894589757 213490590 527263609 442118770 321446866 984998660 192876487 678369020 389871409 483781796 235654182 929767154 279304540 177947244 305581035 90428988 333493707 603981018 29271307 780592898 198310519 835051290 192453838 838285877 114949280 272616296 214558802 266072494 71953870 594419176 818225891 353457554 643707793 512659055 914660868 376674977 105711664 989501628 256035729 858306134 567129986 907958396 556802089 525714535 46322385 644365153 771065520 737734994 530111218 961050357 32182435 192835455 838086235 200602199 219964408 603680359 504355544 869378941 100467867 586071136 627058277 602536317 508100519 502517536 249599578 100717612 737880223 926955003 71549541 306919071 999929437 123289531 262109856 65515442 348735619 41304030 267837162 283251388 585130663 157301601 578432032 971559511 612533816 832353052 290372317 682638546 449261423 341124976 161022093 322112725 339165545 863938281 674851821 623340728 984857493 114924350 812258866 37076852 554191709 135171434 100 856561559 968971871 852199790 943470112 420145099 358897393 669384019 880130336 996438475 997986365 295706814 525654827 668840899 140155937 855629025 25297287 655735851 850198924 988646117 554567511 386379566 536865111 383529856 230436602 875788834 96125154 638011522 472732985 403110100 411173987 627219859 613915252 630607164 88996342 139606322 502423757 411110550 254347263 873088424 676729932 148702510 814635647 843609871 363271153 300386722 923368672 123938138 808426241 604505761 822797750 872958313 832804906 123128748 632110060 32581645 654295025 741936463 438128103 434857233 411514714 475573620 444375220 795625826 29624920 100376773 362768699 368556995 455169068 738282263 868013167 586031717 791869861 82114094 304456361 292810279 574196175 985297185 716960886 869484712 831052432 17677236 234183788 280353551 580375039 277657797 324883618 263879468 841044886 566797814 655199789 563482687 27566375 911896902 98794327 36997394 991756897 968833958 177569114 495590567 854959255 100 803703465 503202298 657641217 640116738 526060562 365760119 732448421 372542123 340785994 7574067 971840009 417169400 964945160 959540573 578218900 274897579 273741884 479331336 555883646 325442400 307373688 416022674 906728904 16285201 518172619 412066095 348911857 998598017 434362 508837558 432039471 444614455 268336448 180113392 768520029 592544144 88584854 728334275 501111582 950505149 810575742 494755218 213407598 54477928 649810633 74598732 673320670 437985001 602594309 74589769 984517320 246620445 368423486 843536087 760511331 362179146 338639781 215335771 347166505 322582894 621334104 977930872 618311369 800553273 111148109 421091202 303661111 628328204 292464789 505301014 990415045 720305472 117508581 471215708 170457569 932448091 998045690 635411251 83401190 66853787 520285246 390514685 247659913 971047921 588256682 475211476 631330683 714910592 618971529 518838359 808821692 553611308 643799570 882702965 711726450 780700845 847868550 651775887 942878844 947516407 100 90731149 757246726 55762400 682954831 943183634 532944522 928178087 524992898 314564169 724993422 231138239 56706891 511237369 320737484 758296936 766278860 856448316 788898151 606253309 99922034 765497139 337033636 7777585 214488345 233094878 960073747 858410161 491561861 684279577 167047529 272437894 664241449 230638234 340355901 540607857 514545462 666372880 846456091 469482843 458809516 563973308 905690334 256532541 170636575 364700576 773760441 565071644 580550875 852384896 775767663 429888956 199360554 964488600 512338424 953602076 737644606 634759390 788825504 578015250 826004537 324120625 811360748 978661019 353283946 126167164 10339749 613811763 699673923 67293181 928757571 780541590 754517124 928733893 405330352 544783169 538108865 116211149 153667347 938427960 172997061 348293634 633864011 61295751 749660614 904135124 790362262 731058148 436748720 643001152 492259976 369585207 178918676 484660986 587988689 183153480 388707826 558278791 585369631 773403944 366749846 100 603258756 54331214 603724215 829521339 301521499 173592671 810203009 509481000 363105885 655904255 138090130 586443582 609163580 974606459 220457433 512314756 846544959 649719509 148826192 699684661 388034677 240670613 302703393 416389783 778222873 488326283 316561268 273679230 435493394 268052202 453391191 227841746 988003810 913770507 332473124 179612282 798286082 129278390 858582278 541290583 57250402 290305373 916113821 124958562 220812052 739338304 149928134 61624829 230804075 2994296 539800239 275372737 315487066 386533203 702486879 711554200 967595344 967814953 24023557 323025349 995681773 426237812 554742355 161873663 334638172 715172303 71145248 843386024 316039668 358469009 383288568 321618866 234585383 257854028 748846620 830002797 740739301 672630993 164319403 434162950 855575076 800626623 759948334 200373688 814501883 406486982 694893907 274071729 535889358 323060979 807453617 260185577 641014709 654733855 333248923 269461085 632932419 516689810 238855575 123965037 100 28632878 474331008 190395188 205586047 726352861 206239761 793500942 158240824 285347605 753809706 667580776 980931965 11519905 535758990 908148082 500473907 927493651 87108878 307111263 999931074 244055045 155629263 5470551 928070406 55400583 364600053 607339774 963384469 819072789 661410405 157331699 330109945 356037586 641774018 412737369 736538528 965010588 448509070 449978162 421580063 469291660 355998661 362020313 251183526 293776875 867298742 329864410 531278111 313110258 759381195 672290788 934955157 444067337 904930669 358414917 617766760 549253139 143264327 549877864 415680978 702236113 868930805 831408291 614386808 572528452 976837752 681802674 519905340 902171022 735711596 719161793 835702738 727502842 440954405 942088747 913599539 385695370 772279428 376517343 855100202 707194216 990850074 713158738 863572101 825704104 817944025 250976858 397945712 922082797 50390561 463810998 425947420 196149441 170553484 707338320 388879085 228016484 204717838 512011002 938851470 100 431928392 556223335 540981502 411344706 664646819 758901771 489437143 684010631 16581671 971736357 963399371 684513318 763248395 185484528 732301264 904991739 505478726 102021987 595341023 563404614 239055737 28268303 605990134 217247475 12740563 526720452 141338223 724225164 71149362 543740299 103655669 506339156 627556119 454025802 320667986 449036976 705058221 539562488 709177911 555640305 90645766 395258435 81253555 797320947 553531981 47335412 92174637 479475923 437611746 863065503 846560309 825094138 848112323 332647398 961714706 800683840 402151247 768713572 785335717 731571583 613549911 498505338 48073402 572902852 402728691 769705286 909183833 620734194 600450330 896073545 944934095 526835563 675358845 491795885 60478463 81056414 902348509 487839532 416787876 853100015 32757910 217702393 830901577 121474781 200632542 45563087 125576295 209690719 626328065 850054007 483630628 191640456 697733378 555928175 295973223 676470066 396702063 909763581 906286482 648250722 100 795454409 77333630 935537558 520007935 741141258 703336538 630198561 410116836 614336355 128700832 446875580 750902954 377211101 243870609 652311196 299527075 390027770 717358762 476514708 23061246 37716759 413686736 876932596 785405443 592604899 954287233 179615274 766306759 24803967 659950383 614250285 666569085 837987182 599492189 445442254 974814561 334432949 324824876 976371584 185128696 37730470 320842509 20296527 636218868 157852853 587383546 847214321 264103377 807388712 840393399 276288213 155796605 27369101 977272916 162135402 780905313 295237827 471953245 844063908 482988149 867166479 378860079 893019152 383191753 532186878 610164613 776796296 776679300 118099733 253752563 575410513 195697103 802315091 452037882 62144838 666561283 593716795 315505969 624913126 905728702 546415888 685709343 172845696 841002825 537244571 854456263 747965468 827217569 162912032 915624681 54627964 418651170 17649257 908508735 995305150 486596052 277128928 280228479 246225028 897695086 100 620448418 730162330 351193686 878132726 217420138 673739079 418659841 486411308 162018631 283748937 393583736 437928111 186892543 847247970 473120536 338813855 465681938 89645259 571411937 854174082 737239380 702527914 216124386 471542743 361689729 708000159 272858 904607510 692098960 766466646 542406484 977184569 87336431 620094652 741866818 531810188 810003737 19058073 712347561 243539003 209733477 300300190 493986757 373974704 746778103 756951346 269165640 118549835 212243890 809328357 438395428 841904082 591134295 638903604 957478384 58213085 52577051 598426659 617560796 976290930 639274794 653163140 832112263 681600440 135474875 570673561 72394943 64412002 540952694 86090927 980774388 281554101 770864632 122797181 453801256 643076367 888221260 135410387 954397404 754129555 722635470 402547778 926477462 131721859 798143197 532420748 905878831 447707414 834250949 992490564 971502297 214423749 752004798 704661041 10980500 1298517 163649946 340524818 672591028 160107453 100 637706633 940277965 938037051 775299178 10696362 331099322 867977111 536955912 882014537 664742348 575226905 813715127 161140733 928658353 412621326 698348358 994331062 805809537 812324410 347455856 573273745 889322871 247188931 345216533 779745886 971805823 988690269 948266549 777398808 418458120 489074673 492958771 627521049 172777320 657577731 163533656 674648722 14484317 751679840 59913541 312388610 881332498 259431837 486378818 99681733 444219212 13057320 372426997 899610907 654663573 530766123 79000650 999002708 334508124 396432227 859394230 288309919 361695078 485237836 914320275 983031281 746323922 891588295 904158242 781091579 756690717 242483156 42397838 488854395 957552018 551613160 884290660 245198986 270635453 910944846 96877570 138119302 809869843 130621091 103635798 463093278 870925909 647308095 778745992 370146296 458021089 506000203 165636824 375105203 920838840 165370758 345888450 176326913 629467006 765971371 983645868 134775651 268022334 168350897 970391126 100 859048199 621187046 524329789 605471127 163791118 707200815 441407580 382618509 847485363 458326994 893418260 29624162 617818432 615700825 981881623 521615588 554786674 627497318 824395640 461448644 679680510 406187538 988784257 743458856 589885971 106731044 862071041 338373764 961922102 305147340 402180164 164730654 869485683 745213495 425557634 476404359 171877826 922067504 432828227 250022636 683404795 436905945 544330122 232253455 319950398 961134084 454145700 239832814 294947183 593447429 227584109 743666071 402084538 149442569 330156306 838607639 962694800 412950979 749015936 781515859 758133066 199387514 217706530 695122899 215485380 396092607 664152425 298370875 822645923 488459815 959255076 971237890 289549026 578432696 577396325 10677756 413135682 893346929 264044971 184832159 945701415 159254556 702561645 121970561 173940049 162867272 501889054 675208945 975954216 268501496 811998184 169550601 317488529 913033560 224722895 59137055 301294291 987878437 75770763 326166665 100 528067076 183225536 486336003 316044349 571744431 390045494 415590705 845513751 497472132 43153127 866278158 605976504 843585076 219023691 402672553 599093592 93820083 213681743 825786922 384137395 442365264 950249440 479554914 111201180 560240755 276846016 666357424 615235508 25985453 638175334 490848494 506604153 228070380 298273643 825113109 481843571 37742836 486864260 408414956 806761860 830718900 733186240 114538139 849825156 7993493 624681502 902411699 41682268 35808022 624433054 137451735 989503148 746931098 160294893 650285292 34977346 166977936 268330301 627382516 509205305 333083350 701049208 852613616 439001152 972491144 975055147 348637475 810550865 178948561 174973599 80890592 13704592 607185852 167126948 697889045 501694690 730829846 958357637 92930648 979338315 244742186 861240006 37314518 755488495 799571598 444855118 538087003 790046114 625751073 794139354 291735634 965425932 662577439 962884794 630084985 371493526 820191344 108885364 656032941 457741919 100 993349382 963807029 742071842 427798531 423174921 918433369 952207650 775450501 107384952 988071308 367045631 928656432 864054377 766240552 564925730 864110034 790538428 435607802 479452266 397800602 259347030 616615314 634734375 762178964 281843846 34657129 437544299 721966197 546484469 252729017 83967017 56277011 177342913 393262451 53787279 628503089 842503437 218333003 465732605 405053174 459749035 566507497 3167401 155218918 661787404 737120511 761504689 978880984 867790006 957613561 417168218 719549436 555711326 921778046 994910702 221556248 854260056 817580415 954116829 102807034 263659069 975698131 350702293 390351725 917895566 999520337 715570153 18080745 448204371 581451646 78542057 806439540 566384802 445184320 414984882 188218549 604446673 649463552 613315638 242652319 79791812 620419557 532884562 822441885 668075058 199838648 181422932 345431805 869547531 785112922 112945956 375909147 529215044 530697670 285469545 431871080 190711110 810495867 912567591 610706071 100 493253351 316297989 324424075 353736514 699879819 466664082 517568246 362029883 342144413 479446299 644325786 687916505 742473927 26800747 811536451 103167962 702033394 539663768 509682339 463401435 94337998 473274711 102526412 529844916 708895344 431364357 586916828 942538519 321477089 79387851 423042913 281572365 978436424 253187483 699430274 767572968 651748620 667547044 699385851 273043569 373499271 186614662 963600296 236078835 408076893 126116320 943554570 475062569 301523500 802636767 905040680 181861907 597991250 672337141 935079704 225616206 411247219 900674475 314500049 420739110 598520688 252811386 974154077 432984872 104286644 391503595 762115667 673662374 54665067 645668805 7158471 233881797 463749232 74134032 266837325 437518727 80972377 613415499 565322017 379491728 921340334 399795288 698842498 556710258 780319837 873285483 475428650 159891543 38665913 602474451 623321620 661620487 1212878 458530820 764546579 35743119 421638224 712906393 87994157 236794139 100 317438079 806306023 736045297 851398201 95664959 434697506 477929590 172420923 929622798 76128876 81532955 802750814 614325456 931532107 123951590 146290932 270587606 54491210 522547278 675880866 520003590 897716689 713349904 235077594 864941883 315745839 242884470 936342196 704910418 587673705 900435886 864157213 378331812 197866014 465938015 84578500 495489036 557518804 751946248 246235141 713262058 725488249 161442611 373550927 174289537 633943 372910323 648129955 580868947 280643148 306195780 510043421 671911092 671638133 36107645 625284314 93467685 738750282 883072930 257428477 512343305 564361604 60167017 963929774 136997849 89810479 190598476 603057836 160819320 485914709 395284543 706001628 600069445 218149578 731277272 703417531 699670190 189350043 581551312 900392384 651479815 970890233 495096630 294327954 140623301 566426152 220063227 583719527 683412220 9632688 437846490 225825708 299902713 45792175 688029323 298230639 954874865 377060141 918745824 487266805 100 569982402 837507899 199487456 142103291 175341034 265922339 928017173 919640552 575612427 603335181 142954730 676404497 361456814 233227326 26332433 175335888 817527232 1210955 363328660 335305229 549857428 316973555 140326934 116245729 699052479 459353949 765059421 426214453 624635492 357155635 414154713 889516510 582073922 88188755 417060021 784058954 989212256 222270300 305863241 408076897 683018739 357219393 168185037 684908336 968717327 556572896 677081681 24442921 417600685 352976675 517566070 593971597 995156902 112602792 580010997 516096254 183617353 461509120 238544168 732847592 218381097 860466611 390188030 653012722 493405047 625457838 269281296 583894283 490805893 908001545 943210977 663137639 194295574 658908162 658442818 926156584 321128001 918772145 482085888 710040419 216169114 748404036 749597324 538202010 23098658 540594614 586861666 116587515 546399071 836994118 934729157 623894082 994088983 214997509 637345160 410642549 285585081 450678174 475614974 323875742 100 537197368 654130272 136034215 961767388 48929432 754421210 485020124 434025254 676612263 978465486 299094124 248332207 454520655 988799990 69711406 868074580 655692913 88050697 993924234 410444003 309741549 885171517 799005829 295142613 218088439 978466945 767966449 246084285 804766182 742374628 540823346 803571234 845399273 523317979 460459928 115575008 521975019 607569415 407112278 422186071 862339120 182736252 744983234 807042098 353059744 595906063 927012061 700733415 586259283 670598017 76724906 247540615 152355755 132561561 605433553 346704701 820587438 848741359 7951673 121945606 99948799 167413967 488488434 362477512 498346012 772821693 555197980 111122435 99751337 344901683 407345663 465941794 337970480 438282511 799106351 762230675 369638539 364004787 244905222 329751664 348572559 598094369 603211175 592125530 689133151 758370890 177563782 640709529 102913602 844274239 86417287 204266543 726844528 150471398 68619166 899372754 839179683 746487187 46016933 798672110 100 220396346 9076981 322175028 402787420 817926902 635637168 630606680 233155214 393921640 122830868 893988933 1417127 679656165 305087349 409244838 942307338 875725083 84951162 796933420 366543326 820992218 813068444 540763005 120878080 706101906 199771201 722987973 28506386 304859248 505885638 833735866 675172121 95684375 744348795 756133930 986488716 194504882 622672266 128363450 416461265 620474804 465797892 180520992 624227904 421738799 642245341 84588789 649761488 643099386 65323187 343944270 354867520 519648206 647868993 795428858 489903303 448372829 92093412 86977715 843019724 939773275 914419992 986882692 482204806 425759042 235100766 619929496 965925079 132296412 86225441 277943003 94512034 702610573 690312113 804052541 747619573 995413678 572746289 548639279 74755810 833783370 219729739 54689515 271671467 234224284 22079817 279356051 988591991 911308138 252474608 461501137 62716285 219492444 476974221 431011853 279298878 803264695 120289073 426687695 561433832 100 390077048 771225522 986610641 359320789 821886759 209939803 13663840 816668715 177586076 386478214 216020574 204703334 755836169 910996191 722512448 795953776 928436576 542135114 680720225 379129910 98896131 626918808 341399773 896772419 487314928 32344680 298415081 871041670 284778910 102288555 20034513 591100703 795248710 392075078 921455589 829338843 438473430 761282069 727908668 980185223 334223562 743045514 271305704 688561671 524105037 943518112 506864016 248663849 158748214 928623845 726594321 941111983 942740092 622450912 425344929 376008152 47377025 638735736 860159161 186300794 288204525 299480402 399841851 337281290 829141796 134079069 120209125 33089772 694411068 167549554 852041452 350536715 789337393 24638406 904697000 956580085 732389966 707783721 971155940 974324368 933125312 821492045 163598616 714178960 226172477 926728873 240291670 658284801 672800566 587669638 348325191 986195092 721699732 453021544 791036010 316477825 773333974 97167457 754212622 159490640 100 517721143 759187383 187062100 611480199 846938733 323017219 456973527 684185736 896635976 971148470 695605569 659170800 659279154 271677874 677760527 72814959 471110612 4950260 826050501 913824756 288356576 59357776 778437452 543661008 327378925 5564181 99945209 151017421 482474852 450069217 668079935 516721803 786813249 509055836 607121595 739691943 694478277 891632020 554848395 843998402 517213103 18326200 608322649 554235827 335434088 660469134 818653504 225543913 512964426 1179463 506935088 73785500 254946697 374950588 167207054 215569473 643771258 223295371 854945937 394528870 941621502 730045262 623843941 811795282 551292938 549196373 543175221 181829690 381061414 652784907 550958050 878148864 419910153 272331683 317898497 645783601 422364919 693623610 723806438 93567344 790124876 521298435 328346781 224513302 178528655 801314798 867866431 125226842 905656073 74456310 273499729 803395014 247340913 490117909 131831397 685963064 880361035 888985241 487261392 626643738 100 393596965 799808850 299369633 650683995 554825477 782132835 763161364 803121229 134258693 512558879 539363468 882533725 184353736 577182607 489227271 548388431 968770768 486169042 347997939 978864210 416518805 229877726 714214156 643411926 423702827 493319484 44123695 353680848 501810062 123103789 916957816 641438357 108279443 702830001 190265558 361059565 161632165 779073392 799426867 338338873 631001098 204779787 123674001 601829898 636327617 528835201 292796032 310266241 653847502 753301760 469221502 64502644 785544402 832941631 155610578 421211701 772977724 899442363 665904060 247065551 927662372 584671162 854189167 782150052 769730844 878355500 992934928 979682564 26440615 551878197 415728279 391596052 521466354 559575035 51732650 92857433 745625383 408810164 299800405 696210110 726206962 133927904 542266439 729839658 554177966 325529781 705326012 9302759 564157392 939459240 993428948 429929820 826076970 463255224 282511172 223540762 899475721 168612341 749785316 990750454 100 114424143 938630758 443355527 3848790 671144857 140923730 964363170 506026283 23985678 755576493 324139099 748738776 410313194 343153484 475887451 155155322 751358325 413551263 906311768 157136666 851963801 783304877 36033721 461512238 399445004 452608873 783218011 892398093 41776272 776298229 512998899 641452434 706048793 985055473 521116466 170879865 267198947 892484138 125381494 805525150 394201476 300818030 799790203 2774110 368224914 467186178 190450713 618448356 45405845 150685304 930812728 964633219 664690853 276049390 125775342 389288042 658096934 657564527 461783313 891905623 425789523 538913475 291439150 28288141 850349497 298433681 931905784 417313658 586480452 678097396 904895304 690394630 654487747 377963319 199837510 276680261 857813576 985937169 197517139 82154420 250563694 705346757 325217123 961950752 270113052 454406115 971496670 592844853 442276673 493463726 192506011 757705225 687557234 61042142 300766746 623149731 315896741 684307869 868237692 327364159 100 499017621 521810837 193990579 806665126 82986301 720490011 107576552 575358530 507514052 234577874 296727460 642376507 341838786 307572998 899177364 756295325 358812273 903177274 355877980 893157585 3818198 64149880 689865605 789080627 479060949 773016440 386475110 975193350 818542084 4296319 757378894 825185626 347138444 674385661 120535059 336005004 193244445 699605403 138946756 189413503 847252978 799166022 435964613 425696748 753487858 600279677 594024117 833032806 713219032 739978725 128781427 840637056 393906815 617702285 79992641 856706369 274437490 950906114 525261134 612065082 910182162 754129773 882037713 261303374 310685982 230679515 960903398 424850544 988138013 244535632 906836076 354011001 583656228 515313477 20648997 307024458 125364156 807999137 45937784 520946450 906764625 851220787 549865959 973305 468255295 311797893 112262385 568247573 680355757 100456228 595383851 727671269 522947146 913014608 392430213 470851632 847470931 480139350 827366009 485456675 100 295711170 567254806 963306239 666437942 606832606 769544233 539635821 965537455 600324545 793672527 586389188 845299664 11106852 98476877 754061322 586368376 903189738 327737300 224056673 362571350 595162102 295193913 82612646 807318426 844073710 276094216 377936295 338918302 173541204 972070636 795216435 7836295 903575621 342921509 784053447 485279336 639189778 170992309 511148863 676951851 510620422 183794779 118903097 379456604 1456899 996106948 721294821 476387971 371292136 807139057 682404980 297456915 599173578 538096044 88551396 936338692 538666847 258373549 439439334 148858814 998347423 498885333 669932957 22819263 272101076 206272701 758635537 849219854 574178563 259067978 683707382 777253851 896661963 261868704 563027112 106525496 994496640 128388134 845976894 566998365 826129013 34520831 969103517 596214398 603304927 537107515 49378808 877743627 391713185 422037973 490279992 701848442 659856473 665331432 413071876 588125477 16648971 97345670 203534864 111122938 100 394810663 944919255 696492762 424722944 855596356 140515223 83596875 638483144 379275287 276212727 563886114 647659028 899276807 755623491 373251472 137281271 97002830 736860993 232398551 172080773 952028242 16991875 831632652 771904888 70870404 772252110 712291886 454431411 343653483 676063386 605042977 454702270 176069716 601221112 647750916 158984749 319512364 575019708 796990070 786886615 696226568 462952590 523309040 638787357 806741168 629147845 677463170 826545546 941060636 710561392 21450228 980231231 59084619 96554880 690920916 892985563 587570963 936055652 574167659 659737930 258798431 811962153 351848817 79826156 799749764 459051759 577733132 402875582 198117232 660264380 837357427 266434726 745744759 625559256 327295561 433158466 234110649 948418353 852522745 159681454 902551573 118477547 262133608 634907379 353889300 246959510 518761743 442113064 971171472 289032005 267444247 408042002 573190123 945339865 427168554 28711989 249147035 854913350 635233899 288483145 100 354164812 651456636 644422494 775200859 985912897 78040550 309676704 555383993 831724816 931146882 427276213 490684215 313544891 778338413 856357216 443087405 525938404 965729722 735070951 426543415 280937538 339134167 870413569 149017436 186014870 196687748 834920717 486655582 431815607 235501277 780363630 692945694 513574637 556560098 107805034 893726776 327826020 506516013 551191567 591530387 443097430 299074013 386857024 430231909 177197875 32053474 97913044 261026246 432758196 302031691 741831985 251434734 624697267 817582672 769241911 173830982 683740654 430378490 69072332 475455623 172069658 911491048 435551029 323018643 409234695 728624569 265508206 765370383 153031244 186066499 725195113 271526522 95734120 824656171 941896010 538905053 435044806 474598295 540912415 423271282 398167108 439674345 653512012 54965049 341691541 437874769 636965295 505171012 129949745 230070303 150331421 871016174 295594587 556816789 380741561 603408850 243321590 732643814 691865561 152235524 100 765182727 173824310 400623872 79947541 60524476 589555096 601125252 727793742 605055498 913072023 759227496 70370558 626508110 374651507 43739563 238668949 618770596 147408807 333047131 103813487 626060037 105534975 798266287 648299787 972936314 850018 939984412 539549993 165870196 211252757 865604169 287458308 201981421 301255765 27425123 475096474 112175142 218906620 310279246 641453604 599789266 401642348 581361808 198921584 703203574 689442571 498802921 952776747 848691970 888561644 52881448 227040279 876205650 336471245 154256999 512771275 400852479 973237991 549376687 696515753 212909085 816576456 779566039 867279170 240884080 176797389 365459940 954630261 815043512 727535579 953259809 971077015 62253428 473198307 140582060 933850882 5147326 652745896 816154302 607847909 483110490 379902343 24182256 923155418 93102404 113268262 765310855 186934313 207320565 663749153 524158820 844886897 940480847 441664464 907676790 852742182 566665584 920283396 798565136 196177607 100 371396134 535652903 188644270 995743336 720984256 449971906 230106979 342155285 740060234 693919319 92580427 35525493 368884085 779487057 731995252 459816847 188706419 423534751 294057443 794303157 327900845 338654511 668780554 668714007 141074384 601344310 188585441 31168378 960433148 735361847 775841912 744280202 550880295 508928262 957865865 578858163 386425046 690305686 14810724 825216005 937468418 504941648 871775511 737401735 982047777 748909666 323207852 194943510 10854837 435638444 856134196 104311607 322879346 940120954 918563782 674721129 638636279 989605299 55428001 550668415 717480868 888762142 921090436 458639262 558984980 368172376 198687336 47259428 730390960 639015870 818765363 565102028 355898367 566950062 534896817 661790566 369991497 122648889 903991 174599233 728013707 91752425 261108598 831123661 600626693 193148044 754128315 298324342 854031140 515915154 433183238 186642421 109016468 771992742 840101835 121904101 416096837 555871841 117633841 752157061 100 837168654 518563682 978825385 220831181 432709975 642755968 329768645 805814908 50086765 92176387 677967944 550005437 852892221 647494231 669661004 302835804 40497542 27528977 914903926 213136974 29741124 717299401 398861629 468326866 238226454 34885414 861358427 408295620 2943397 923800713 267202292 265709175 359914283 646607045 849299675 165029231 146477842 486922978 260887635 334361845 131005603 719089252 221903272 620676015 211389463 354734505 971966224 258965654 447738993 890511820 180428434 178557055 753736958 13879148 952451676 46295231 610482826 420602326 832413897 995018910 931879192 536312727 361524924 398918867 477153001 236056556 107258212 485545483 322238792 736473482 227444131 397029858 873442695 307383044 253959656 91634531 301680491 845104037 111778550 603650659 246475543 910211530 524012966 481384226 121729674 403029146 564273577 977613326 389524044 36001481 720482303 6747039 909337490 828388072 761541027 430585875 77509377 903772807 916254537 584292539 100 845674817 569763359 18086287 808100434 944111117 700458672 106795365 974412805 501987787 399694162 387288905 929476304 491554380 467674666 44107124 207351401 282974844 553390800 730303417 916493828 439057306 463105730 86750224 66107995 616112309 69946147 756840296 605119343 478554702 847992612 925124689 967482121 67185483 431136900 817783562 513921395 347931819 931249375 520995496 281677013 659613891 28550089 488306952 328690142 959553505 606880504 803162995 850620970 254668813 918089406 779241324 687725807 281158456 710299766 258789925 289926908 765494179 165440030 181629431 736501719 831356998 277447889 806177161 793810895 16519848 275868806 56539752 454897641 272917464 879269612 619002879 261774819 551214759 140503974 57316011 550405485 811684855 795202886 502629302 56992178 971795416 555870403 799958276 421050177 632944823 86214081 748359237 774463289 535580395 447323719 781414441 580585006 848514965 26492138 533968328 425881595 432804872 578602386 379146622 285579499 100 860005638 437092502 166297117 354656449 306067316 430333116 393567694 423624447 714771017 626269202 124213764 444426219 65001453 275490110 375005633 94794851 470730813 608744847 837575501 719090527 854534245 769430347 602716452 118444410 265774805 860540369 283186216 265002200 402903824 505773140 226776436 994870421 275370170 645355133 635696245 230480035 573627996 984677230 403135826 935613410 539684818 831067152 601098572 962062882 216797557 80258065 437117658 617194675 898170345 396750779 775570435 254719468 466297320 844732633 759548920 129624293 740071460 550175972 575859288 123870914 710059196 675705178 623484768 727453287 458091197 343519481 133865934 370932664 297976086 875253228 492000559 742534512 924077970 356347076 483455333 893305101 954180868 265294837 554238499 452533553 488226358 713689324 826278586 258343420 374773295 905585382 658378496 578692532 490751891 159662185 544015970 123717511 694101436 841307139 590831355 899568219 146498113 723097755 700599159 591794657 100 86964312 276209339 546082984 683085915 945074752 12447330 938619840 357604318 521193562 798087006 10758265 999384518 557751942 626863154 901396212 154789709 67698122 459642866 234108924 56248798 279732138 215369110 188368482 349490685 934927448 129544284 195129834 71996938 892712618 947704488 8173425 734060689 545119161 312776741 287181742 496469033 796065975 988607686 693718563 321571716 188325015 456285003 757682582 794438714 1376157 925904954 6413842 191643264 344630249 538867825 599458807 677049165 185164808 568820439 110262645 165857177 773216020 176055507 846129501 44181313 303335518 14896710 567846419 635134766 194215007 127755697 940605870 608386940 889673181 541830846 306259233 261361237 517581281 384626111 931346597 669930149 273471212 820811739 419345368 889735693 854765960 947386045 53274089 72107535 620839939 321647266 385244332 333819137 392664232 10130051 571861722 128488755 820461171 197235394 9757066 298536368 261602287 33972600 390333235 576006116 100 687326505 110197261 708781104 735923664 631495050 382379274 178436857 360756544 763985716 208675707 695628247 226718050 625418601 4299006 798773467 930457945 550940770 139945855 767733259 62866275 281328432 412742059 226352096 702847559 721990500 564215419 353639280 981656368 42244805 980602932 208749113 610161031 888897941 219266174 778840288 136830283 700031288 738206413 417153795 511500286 96072241 225406501 306603858 179688610 310335647 960267906 178389873 617244515 476856181 330166469 273187527 315777546 587522591 115130977 651477819 405020564 803944473 11759383 801911878 954873937 416571018 270972154 971670165 131356402 189223855 866192922 781736894 411104026 218395926 44737471 571687024 973723973 886308768 358938552 413389653 180134444 620220950 631726670 164542929 639500557 819894610 896846851 143445850 528097845 657248780 560438100 500488976 459927695 570058982 483856566 679297044 725008788 734348530 47420198 310446143 94602440 446966126 420533465 866395679 274485820 100 504569424 113259842 659370984 164532405 384144921 607887780 358400495 202928270 696583877 881777409 883030873 285604357 93972798 302064418 523063469 94096578 771663173 521928537 177385708 722421957 563839695 928326643 858455472 211990985 734035136 637528871 901647754 412984219 569597460 915466901 835596693 163606097 518322469 908579976 373999410 216437996 126327150 411911622 489877946 657087782 292762754 791907864 796419781 999215386 997119957 188236892 453924132 477813661 331615735 621869370 596035288 994503159 271806694 754311050 260551371 514662670 510494562 174394310 879908914 99469449 828698752 629651721 823310086 774874961 831268066 84082835 285167786 926608766 640537859 425623236 484766439 489061061 573356446 771931311 767273548 354246211 329510778 312520889 651362214 434326663 704875078 243585928 464441257 295311207 384091685 628236671 194718018 874383381 799669680 292656216 542130772 909356331 14910926 886633206 427830221 580682017 86399791 711517031 265314677 828330005 100 691212864 364395529 89366026 794405433 838276829 899169657 424022070 407255854 936013152 455723900 889152562 957793742 7790272 837685187 895449610 338626355 573610950 7192858 896724221 678373056 298970774 162064381 710682577 259097695 654280041 361607277 899683206 350390533 922724520 634919808 110780281 618529763 266477331 421176136 524863252 49453668 459897358 143709445 415351208 576798959 273691069 626882852 449617621 863623234 893097291 915600054 249131368 452325806 265279777 338762412 7588681 889704770 789555936 170154739 117057720 67953239 608024509 41191772 285685376 726775443 358353872 166193268 555073527 771207361 938966860 21961405 247268312 690782042 975539453 541893639 222042346 910019762 958515963 591513981 522012726 620320058 671829842 892277570 330132415 14364163 472510094 356508738 551490216 95607546 91529953 634523398 413817252 363898193 132572638 238464915 724935251 432084176 646696080 696449139 296131814 805297926 451230270 917424327 5170171 552713574 100 720965201 121446055 483342018 382733310 533602998 322602172 738838465 669034624 445621261 50183595 662663476 51561595 869740604 174333604 680179 135568797 373064864 680368548 210241487 130523540 103858118 683404218 463420435 468216634 543020460 116140979 815144607 137969529 22801001 381072744 484052620 249944814 977756586 563261406 711298581 60585735 98871308 202965776 863491485 642207010 176534907 717405072 760658634 632810458 617845759 699066324 763128614 415865474 245589869 708846061 150814324 308543415 154518745 97354465 722545810 781734768 913804041 305076010 624833723 786121592 782735468 313087657 710669614 829524724 955109845 750638781 952969496 943293813 644470531 639219873 493690072 511930057 305170601 281791349 13797662 774800980 509003782 34786734 581859048 512541923 874451647 115725970 38278922 696271654 571993608 289714796 282824086 299033582 76754017 71445620 255707704 653966633 918664450 266523267 500307788 239927326 368717122 7017598 999720929 631393933 100 419062653 100889558 450036635 532142717 718038101 855060441 104388933 712843233 851825304 935066432 241270852 340983754 95186182 350999672 628061156 329954019 8561494 745987179 473412102 285336228 501350914 149096493 874913803 574529281 899115343 987250095 977755334 88119126 477960050 569457294 420508472 743869022 848996505 677576390 100062882 927301234 657424968 338223725 933384068 722320911 549638405 432284379 886741245 682429057 698755666 596565314 428341530 554784482 130433831 872429534 494722403 753528337 86757782 994607598 311766425 39667479 425528225 268201169 747947717 509043677 9672880 91660464 602539970 944219964 729472681 351721259 383903312 395491435 875026159 228229909 571172816 439368948 337081529 276371166 632943584 96551821 530817805 154601272 610213014 757795152 865332918 196829307 606687960 316219209 127929817 307245072 592910343 910663777 222212449 713286669 416604412 927064142 274962045 525030877 655964969 949593743 151652227 834174180 60005934 160131149 100 207388341 652661394 622256340 376257344 390279619 669189874 875204147 646759539 870943767 421778079 62852312 108129448 92337579 359757725 489516159 552921999 326635703 339400712 660998626 50584323 864934662 292976019 96501286 927193320 630770424 358707051 242584674 305750840 211486751 492445572 290857462 429115290 111920083 983991409 989850151 458724784 630605968 796412340 661152829 459917333 287508359 281641023 239545378 488157980 140216692 214032563 780984177 410617445 620136620 797560798 689265735 396234301 909173684 845889459 336094158 198525693 21589645 44276710 247787442 27144939 480882037 717512903 616505413 160632706 480972303 963190 438795641 945451863 386318232 757589320 57390183 119388943 714380907 724893092 108412513 98436314 345421503 114092200 422833917 838848923 806907411 544575098 122366071 979654521 547815920 848894419 844257799 927562925 246267865 33834177 300505292 726568820 39870735 310607871 463369889 236523077 329348582 918398108 213987487 802861497 100 74705464 655893664 712334408 165289788 171371192 799899394 203489095 170676276 799650636 266612774 598313186 632375696 48768216 159917689 672945543 396246098 750618066 343633598 127694562 380780757 386387832 845957221 629399441 163487125 721761341 566312451 519124523 599295810 319138054 303041874 149194930 218370050 452084694 171680248 649259818 525851014 742198551 113812670 182345533 346487957 213633756 333257133 598974157 720647860 598241188 633681678 300540078 181261009 503644954 655680829 912756329 657167239 871876944 124958893 217103356 87629671 159491979 413955944 487180825 309335779 321302043 998978552 45951341 494666253 781278226 908544901 816525723 430109573 412457314 998848580 91547243 20720191 223128335 684280792 265293228 954814989 20491290 935978659 223692 713168314 86631140 208072009 102829307 210893989 913449391 569557707 993458312 808927707 282743898 304178363 295675810 679383432 90759901 128491959 302868429 375805888 856453692 381593962 374494251 342920657 100 339602566 438799618 73499683 216231150 802161226 27336150 434111710 883794132 42415978 562284897 317928546 631371179 695793222 379100770 27107291 640574368 535192531 607617460 343743249 162689859 298382242 236804214 229853515 787207480 344287580 66910250 197223410 345773705 169906674 398101970 325033898 464473787 367745684 223209459 75590843 943180385 76434838 26894848 26046475 216460827 135190672 364149023 962286875 686728488 917238996 779709982 369780020 828044348 947382112 96219258 239677680 853168959 951838110 763121761 760811991 671292485 651714834 549517969 889286453 453702953 167366431 866760119 66702193 440569114 83631423 924608802 622493817 420641849 128069167 622933603 24486416 190563444 323124211 271962613 768317180 592721116 330165566 760551646 39957765 793923326 107542842 705330090 972269391 681146015 859785781 726770850 310403919 943537604 50963129 497139868 806432780 568784642 643327081 246487939 399010 983691354 749991928 79365291 269585146 663433188 100 378835001 52165593 730969165 184131852 291775012 239807236 240065224 824217825 203135415 125225297 615019483 986087278 388709601 541780355 366356618 941977062 597264789 443262908 324215109 936118904 850080799 547918224 55386938 517476408 233764505 414458855 4013148 5411131 406939189 954873425 60241211 695222482 71180632 865801360 486373211 664307993 527310985 408945401 75259924 462568775 133261919 37039516 885317243 156337994 722421997 566390599 941657900 604463138 944886486 225536179 511500258 130843608 297428113 306351958 210033949 902081708 770583339 503868692 206473889 476560907 10825517 21572417 908505899 876671751 129652264 697861299 87290423 522638228 700504465 159750618 491495769 569742727 696068773 752644007 996156162 528670399 459241061 808051653 662870816 299499325 728363683 339670465 801446034 815244612 814865139 663721283 601426690 888820880 798248720 288510419 406054409 824051069 925260836 617943893 210799034 933310529 284458076 393367423 361840285 329901055 100 521486760 953365054 297059771 342792852 610681718 106150007 377318801 17016251 526355589 450209351 159542738 704503020 316085155 2892138 602685155 322163337 132794018 87768085 666151574 326289537 386720184 747626390 784294275 485279279 169222220 123179345 556129529 507742694 277309289 686156478 600034499 626919216 813585082 95143566 430726633 481825890 84859618 662645945 731174378 405782318 145564131 590500846 178559992 551097254 722596250 436920455 88205864 639447674 277559501 500388458 223899790 505763539 905264767 919706509 155628576 109765981 342522091 86900572 548657917 117370256 305856305 934403706 572205372 54527218 29461731 642893732 969997319 385752973 356738039 924967009 967563592 471308363 859534307 558609079 355894487 611162069 326082167 812211606 207962036 203766805 706409988 396621038 815326771 530131868 821795946 375122752 690456784 429117604 532144987 143907739 188838351 636451781 852139299 432639778 25318110 829321735 898574145 211423328 124227447 657295650 100 861836460 279484164 815916792 113604177 196653261 92644770 288730305 687355231 475469988 205446627 67324906 64364870 385670909 676172469 401204397 585153007 207360718 8711087 738757881 346159925 172142272 399340745 205072634 16201037 150259263 644423348 201435224 620984637 853910006 288323273 613838142 145083065 391803254 524219712 276255075 842695430 227832252 535674324 566502775 170261325 459827393 156864064 88343213 225067632 664706103 580744633 510501283 898522846 827474143 467268378 789449642 823555282 727876562 494927833 391905648 969714986 375072891 624517732 74153703 253607609 415567060 713123118 83167933 704399580 886940223 985514389 863018978 338768038 905484863 138101142 995972730 736637819 196533846 337681798 280311873 856482241 195818766 311471702 700397847 122516425 109135022 772759131 73730221 912283903 460873204 896801859 192250308 276023043 90690161 951444392 967572166 399663910 373054696 406438520 177992684 424436835 150071706 967445292 508694526 891401039 100 498684056 297405020 629271293 687219741 871766497 745997636 991961536 247876276 762076673 209011522 645595499 745916625 810834003 246257496 264220119 210387481 308590050 629097117 876256206 869714465 823029427 96371431 33974632 736475844 204474032 200753546 725537397 737113989 910338135 621788717 736026334 317287625 583739722 164228187 608912721 730844749 148392350 970594369 433921771 884193615 662104864 180578663 468367576 705931293 160750078 555315593 794991427 527758936 827313963 133595628 455623769 126965374 200356941 969017996 197588654 73994787 128737985 937667916 355138227 136405325 855142702 752631122 6404596 315282433 425457667 52121124 876744429 610121034 745084246 826796179 160372326 88904210 979562992 929890320 919081145 156437799 549795157 692707959 103886864 256991484 650884800 614747375 977269539 958682000 32570402 36345237 824132189 843047905 142420226 146092916 17675116 864078941 889228909 536672895 505450975 537040058 185088287 322393899 456668550 2223163 100 46234489 766375676 134734628 426815196 254180047 299621266 149197463 491865531 875970002 205188617 149179537 969034639 493240889 736846971 832296365 666246854 869582484 822503754 575895734 694333010 645165787 242668207 955861743 381846929 601106546 367520409 987406596 752546414 256656408 730153769 155826220 126054282 440610944 380241353 942431416 340915137 10120373 996091380 270822501 166802379 278931765 40570492 926253561 640544018 87320034 321737556 95647144 407885558 429821184 237943057 37676717 762867575 252446808 287599140 765405929 423452899 561401689 840961291 303551774 30981879 40257006 326686490 514493452 256748991 365909662 31591459 65889044 1580365 195209988 629128338 449986843 607500669 258637974 22474738 786699159 516593872 677781911 712896632 723020493 212506618 199844067 530994277 674067271 160779361 428976690 466189755 65371685 862044514 128347914 513783346 334095058 544875787 328482897 606500659 825935994 81215714 174315115 477969952 838136374 938965686 100 62843223 127946616 956604859 513065082 341273149 729401151 547520881 275367479 161101750 704769791 696759517 859777912 543945299 928977200 169901039 52428344 475289212 414742971 577651008 301254691 797233266 648241250 622721495 957322037 706567891 397558519 165903690 227623526 399347845 134586361 857515141 706307371 509034248 857467785 810660703 89566337 221441921 377646490 307334694 22080111 345994122 841811459 267728022 267815693 644545420 953494440 725948716 607340488 873497440 286002303 129744143 739170414 357837351 114546163 321201570 366306960 922639843 116557582 170739261 692032079 733499692 206517511 108662427 352672621 804266870 748267190 492409534 765630210 164186192 726211770 457032701 276180260 318111355 218327160 94437109 440914866 169853703 693089918 444663209 297652384 399369321 776069353 481341225 605406785 978003757 701669938 121876758 633122536 547358459 16210979 536104404 52006573 600907684 976007620 972765205 664946248 504448755 741796356 258556780 862388747 100 82581166 114500803 580610745 832227641 249917123 441624103 478676607 299856267 123249657 461608149 151212783 79600478 695969665 630974132 918290597 550197950 568332592 80414880 935629906 193271305 791274890 991363546 852475623 254708901 323747326 814500535 575568798 287514688 686772048 632079335 862162209 766577136 788461923 469170766 515708055 642917431 660005594 481478601 490486177 473862998 868325900 711150151 746477437 665120860 545971568 629003766 812973963 535012005 548143458 217002907 646121958 614907233 665595345 427253610 454691902 811722038 538922170 411089029 33379620 477711149 247930073 57265755 93886207 380790376 556396285 597929914 412479522 732226075 316481648 715919401 507619412 335161551 107088121 23039810 71517979 961520355 146172006 211494 174217756 614222525 145086339 488110090 311258525 156165293 1365004 256025358 874424298 214679548 71993129 638145578 468045001 459887590 805444082 857299364 428772228 970698930 473077056 930021175 42242331 899956324 100 843160125 938583319 711997321 869264817 502367052 732777941 734597484 659728819 62556221 771444707 518762390 344581575 15134505 33358866 809861338 716829833 380757711 98506278 286528653 99755727 831361955 404472225 883085801 808040774 228773616 145056903 98899695 508829540 185034872 949566236 471423192 438323585 671405475 455005683 881908809 884177493 972423269 916614932 689783048 753034686 710200403 414388431 981700147 426317475 727144201 796632399 635888050 501953715 795891423 989389785 246005314 927621996 851894839 537523073 486331160 559900832 777758170 601257159 554659868 169246196 22927132 9080976 112446670 227187195 967913604 329293638 517803541 124098477 368021262 33163341 943472713 72022933 369026636 526496789 370969055 609826719 955207670 156181644 349268166 190682046 272033419 623335666 56536606 211980267 579719141 25481126 53440903 427900637 448450328 287522915 232704790 207311338 12678311 255112237 908051603 786560163 898073952 555340633 79124976 418355821 100 256504801 326515724 790516870 162507109 739866085 252288154 239895016 329573466 104176038 875223492 726131005 693120617 650188275 841448837 810518988 68653604 746591872 949526686 682651336 570671434 608367357 372324014 997010676 96146803 291029895 805457382 684634763 963591858 241468388 346124851 792147090 35092381 198895318 495941882 983591770 266181117 307337020 804697018 120903255 978799944 706200030 210740011 580628978 807027346 242949562 401265083 91126173 396376781 564605630 397880322 845332206 967261256 528505103 395466756 111856349 591946445 498164323 793404126 964751353 957797156 296501444 736133009 299891452 871075116 185240061 482282516 551897267 405621314 820233672 373896901 257401664 38975351 501805908 754422201 487741217 449846583 599054150 925279731 434717524 98253607 46122492 75433517 972597663 899089384 570810886 330433989 53798658 359230548 532613517 194832125 319900766 228500569 333138169 675974363 344208569 890884508 94853313 668865898 649649751 97967359 100 370257392 75460939 786909209 185817246 272437736 315705705 319991283 694428642 528206753 760001615 680786798 697800617 456817402 54738202 954545831 469494995 561810626 735699845 943906490 688127815 111200489 734332958 902944349 931262496 766383506 209597947 220329226 698816783 698582792 236199466 507505125 296045217 536618398 749854374 904075764 269513867 333122566 332657781 631011938 249826251 956681595 92831776 371418685 345691391 827229841 74489142 708912525 495930935 799659329 471048256 831249362 254480119 837302340 35298513 817017469 990610299 118416295 699482048 705681150 492450056 940614363 240896836 460324659 847611563 901489644 580064468 347478158 982543873 972822616 469261453 712722066 932391664 21080414 519009278 694495940 946241071 677627709 76588067 324514710 142823874 708348163 474478759 550280019 577472964 88309678 868603650 561224510 145769908 809215020 529422111 678157484 84812968 954369137 319897053 385413496 483733636 63620375 765231665 183340338 424695122 100 487078005 564691145 600600380 133197705 747949408 493556205 513902691 683555471 237099670 569711971 618656714 22015047 683808164 182268589 423031399 60180960 116426170 250378293 342077510 380345784 97806052 278549588 306326279 809448717 363200880 416173941 286571314 290014078 128824004 81905387 317406045 961548776 708332393 541729264 390818553 52826704 286152734 921666711 416044966 54019000 508259110 445270939 950319747 998179116 408667910 596286394 210065687 956981854 895414828 668501897 984981127 943004593 574071689 649233788 409322082 167185191 147821226 327299892 681049635 345182055 465439097 420637458 25780122 876074102 695822547 21392724 662198643 881178413 73911824 909253265 474708888 150453810 772654445 467505658 857316706 970466843 541920908 988662124 756843265 624648820 840135903 291771682 778645742 639602053 690433066 704715963 88835838 122604730 896533098 700021807 836916240 978149345 131141733 255042098 490778831 460379654 472291504 494521636 174192826 503359680 100 119827081 770001411 762664996 518863673 117981827 199363466 888438423 171338831 744853994 799221813 454551337 61532246 303225491 998005416 669016247 792864453 864012651 576619838 868614347 970475672 828640549 111286753 492647844 928400781 808316484 707407349 658605626 630190504 84795676 977708789 60328227 248450512 768581320 635622163 686495098 967113884 338979332 276238604 764963877 261242182 352495787 71410748 887076010 439840382 702716176 885516784 61266370 12000406 476497839 895434598 841677680 330741515 837001091 352653826 404158203 677166934 967291736 414775493 536044668 336701793 86006443 863320590 387598284 48659578 356166445 472806428 559625822 882815160 765237017 694970725 916653987 932060711 59248324 235636863 231401649 108987437 43231176 109573347 400218827 794015472 922897288 504585211 812375076 977568513 486917711 179771941 358686279 724142082 676747527 923844203 610294679 804360327 329461307 884195557 635651182 996339460 952808718 343755651 844135007 10880645 100 500045272 512033781 19036082 88660244 609731101 785124988 67492360 908291400 479665627 589894365 186894857 600392409 632556334 949393268 444109330 660312612 822439469 925389600 825901957 498031871 708255909 661490324 543999220 580637252 535469990 576194952 937409406 328304850 741965941 645291846 976919629 918510151 87699971 579098052 156865391 300016841 166579704 826271364 786693857 528089941 369664317 36627021 318509112 405123289 389165313 347880098 470958735 3778108 495642081 951908432 537002991 769220559 339101202 780201249 826067120 449445789 263498301 602588582 975756873 296765717 797557522 56134152 366451071 117896197 632088698 143488861 780090987 976405601 836251694 994944264 231530445 877780508 357177200 687170152 583271573 950569298 343411376 187640166 427363485 651573843 913498981 29954720 900498880 104334019 367626552 265705702 553692032 332714847 375695207 197195098 276350668 126921179 158432498 601364952 596547286 650226217 963687141 75485671 118952711 962054104 100 758747912 806661992 466372480 229076277 844874503 161211178 249363004 804823397 228588727 71616044 394090299 274903470 124230487 493862196 320589785 300570583 69954691 333955871 681884793 399989224 18410610 811390891 547322608 850451424 23226496 944982288 950110293 842499141 621101730 357897121 495171389 307005376 27409184 214371703 334253895 541002281 148613572 606883884 916715274 185861295 103900821 489484372 867704203 74629036 510976989 599143195 889710235 221398197 580092228 251502145 733502899 583471268 930851863 470379069 925769588 405394161 742987052 640382687 217770727 312065881 60708029 131922956 72838250 484143684 855597061 846349841 982090929 904415300 550901001 359994095 121366808 734091262 857312863 873332945 532481104 129851459 873444259 581076856 16439795 958904532 795601203 518694059 233230627 414692941 524357928 708911883 214538450 875088598 589156585 92968938 650682225 313158226 257778214 499910018 931749094 107574558 257006177 685006873 581890197 76689402 100 810106348 919498069 278239185 6334802 455662027 468799000 474241022 523009377 957761967 735580011 915227121 979560627 439098872 111422651 843556091 989821403 588336687 708520112 635160829 908233657 205614067 672542329 951396262 846628777 780703450 835791131 144264865 576364498 181385682 41632934 308127484 157084114 758103271 277993796 35592832 829969764 376437097 354117537 298927104 371855467 485304638 304807815 386063306 65769124 790107961 481374308 544901488 508070056 836087802 739095062 570225843 371116103 897042486 203654280 206619532 570939090 8966351 526646412 620991734 970359373 366636334 986506702 777820169 794072342 707473028 544983829 78552356 35136492 724059765 684288825 958892597 433875763 375833010 630172045 53601494 768297093 206335924 549290979 224551728 19364678 926802869 333900187 91773614 350277016 204914024 563014880 862728714 319057847 30301230 788178370 303999894 846085826 708368921 956872848 506374965 398860547 535145935 448721431 480318280 398771702 100 546087137 892222733 373229324 927200591 472157669 961377977 252232640 887109139 95349329 748271192 750497726 810081360 508948005 195982500 344674281 15383599 596456604 967718630 946573142 774224290 986702412 197041376 505622771 948308153 865969743 353797479 928231382 524231334 347324747 254554325 291337610 159541133 467763594 72722655 148268064 533674649 20261645 307168946 372055190 275868226 904207648 842680668 799590575 542909187 258644708 560639674 891795157 96081492 319783086 222556017 350173094 246643240 468465165 2425756 62285831 529093158 216710429 843276448 571036977 321212506 618812470 634876158 612612045 472090593 848020593 191329918 14619203 101083372 490066038 859245596 297481943 308290102 750725820 228650912 8288405 247903180 437806055 686399404 108982420 45094555 496985923 40007180 795433377 426699807 615379379 729883766 631491677 485768939 872684391 409820835 175347409 800871771 873538617 901887816 395732028 77100221 169157000 136202263 115037608 649116687 100 637694474 571748308 450976498 322885221 892326045 348579074 1267885 745820645 441484101 306962086 561286296 612391559 20086841 489046375 343276266 72215289 395792819 186935370 622724755 911370052 660081146 24686610 128723207 120334033 927859547 419219889 179620958 526421143 351339864 466862832 117053610 790569086 412003255 345363081 581523348 462554544 406835061 399340379 378700085 308326815 946008960 448183822 87004658 990193260 733880099 281246602 132852303 585350645 312663246 512048632 19265376 875692979 596875607 745029618 236808542 521282838 741685470 54973922 754120282 837491647 119757801 285188996 675015798 544199103 284206582 495906259 677068870 1258538 984505296 296449046 351894554 431133652 498033186 868137820 611678844 52664866 495895967 780278656 147646102 871881512 815834650 99714856 779171301 425878060 377715650 398104958 63932089 675343034 997653098 249270984 859535461 828309426 924257211 164147844 321601701 834120042 568117907 123648703 444540600 756950673