10000 4459
786949837 40024481 454591026 897837851 973505796 238186278 612623099 761204242 14605259 63442564 164633617 677118747 827362631 385776995 867232601 601056138 852259477 422661207 571982555 286191857 358657409 177665283 633546999 447809330 646540277 738325940 886062358 544428312 966332424 839726798 80042931 906022013 965673304 878262275 631680690 341889612 698430356 709416727 147799171 463896844 91901607 211331663 245256122 454059939 760943221 984549368 314063475 241308393 136402429 766124888 656209722 949788817 924099044 396158353 123463370 896967135 618429795 637374090 876001509 923666418 924475643 714617158 436431568 262029043 215841261 388859506 295337008 288112556 855086586 920017367 913326618 454797734 382514515 358430977 586944289 89522875 180762232 151936322 411969156 597282752 336361021 282434090 198003463 630415435 6255296 47583943 765293708 593282252 273901831 330619985 174763766 80925332 575090254 661617533 807573126 944832268 604653067 983073829 783159938 404329502 541758165 850436739 668410125 829903077 784838314 654681565 525092027 238739939 788611901 770415864 825096197 267976085 346982703 989595340 721459329 658364982 136628841 860013960 787479473 205808198 656187946 465668479 124274509 113060853 5895823 481149160 130365937 699632722 267374427 513030934 416628370 83137788 672512688 36180212 291890747 106148651 296696064 486654503 965938649 754974258 41654926 103893746 98332732 280246603 317662786 272654082 309867441 569289372 352174101 870606939 967500911 165952140 487203572 420685621 194514405 794951749 46188051 698330378 809784756 723304059 175575728 587280067 308429373 520273719 37845294 451156845 495936291 361090586 652125547 678457769 415882560 347175271 524545128 233649400 659095431 625174071 310574124 712552684 857210636 101816161 961318991 75355721 565787193 620519164 969027009 261471327 939261461 827372922 708035016 904183541 829176273 982608740 458557546 816108076 805310280 114717618 95947068 268293472 558102636 258582949 57805838 84005309 270348426 519099551 99183441 694159611 93615689 572517880 387023279 740907201 334119711 473634832 362765719 6597156 145629610 59807977 836381788 417322296 140238616 79829558 920647903 833349769 118043673 649016930 375591623 733176751 863357593 31081980 283293923 66562807 214852874 121294876 105786903 953809310 92786400 598479613 239057979 603110600 241042850 191274934 706331677 121115026 700775035 208584940 659447703 612363804 524734734 768454011 332785959 99719896 500326601 562733983 209980923 671754803 720543000 164667228 576376679 213764531 481988682 347502218 809979416 265954076 896026350 446547648 373368039 742538165 666524023 132251058 336066578 259360392 973486988 356530828 16701277 805040469 487049034 247818604 63526953 333639241 272399317 93352106 955611161 412316528 862132955 504744416 17002567 52772519 546087944 452467285 601976338 391525236 358461402 857363250 519709973 579159695 128292282 97774743 735840529 94577069 149848510 230580087 167469718 998384942 636606986 220334 578596849 277363139 941746540 977203136 802191053 639210575 721757291 964136408 918904526 3504246 173627986 375178122 5416820 467410493 217940192 233022209 138570372 524041815 970954875 687395360 930369329 298073182 367932428 511964159 468478354 645229471 513966441 900068284 595797602 277911558 459132752 676916318 989791613 972334442 360367469 110823253 263585675 97472636 792991956 326594861 831844213 163521982 154279158 840427589 128879610 137978836 592896561 662616639 941640429 464018887 548189879 248058361 603770701 136555300 22951217 89504558 225993318 588293226 976764027 62886342 197415116 941480876 900474644 700945796 858848039 351938219 593791100 739099330 331789219 338664116 520599241 867029741 914780616 159357221 314057566 282085810 83276755 587354893 915245571 214546113 284496236 117659676 982006677 677873633 763182002 247528132 800818376 348432568 408837469 560333781 823544549 293443071 207524313 746028778 330513300 954783820 881470704 557036717 83764092 226795341 40177283 517758174 201446628 975188491 378645388 932420446 602992215 260769424 385543094 286750789 877358468 414117458 307837661 126274057 998693009 685952497 153217942 820175692 948985138 881820127 800828453 802073635 950300205 736963646 596926905 479028354 159316685 769384105 12648382 571154418 860455228 281978369 124975132 480305255 937913807 825987584 55097596 661707186 390474037 525331517 515628143 720148495 289541843 854847631 747439144 832820289 715321858 971287698 378376171 441718447 38704647 625497173 676665436 678359518 419791252 490006192 460767804 119377659 456341472 745237028 779507617 384732595 485471579 39891301 587793905 366360091 114457473 871179847 558062303 752566915 78014050 679542111 24647105 596004620 618616224 151669293 360904695 904579004 24733109 979594102 737256708 565722942 226459748 181644003 133243994 884413929 213173347 874904045 991726277 997120503 952743262 529199926 312198863 635668519 567495096 423499185 691264482 720748093 99212754 311148111 651352460 696581161 72022184 794901536 479573155 346394664 981354682 987250780 980999965 159503508 961662671 229875213 232679482 610796966 772343812 423695379 143148978 978378940 612144352 989962681 159461736 17229167 852731476 343300046 953524198 464320393 431389665 246309607 856869645 671972598 752276141 70717888 823714770 873170530 106680536 674297271 417390704 184020964 418701645 332953568 431809994 603769350 8177011 283506760 131639413 365665378 759296844 927179098 453488679 773850380 337340075 533548101 446458797 18153995 132330250 217440232 866238979 267118457 157449929 137418927 829405785 205294620 376124511 795402927 271765631 815186773 796233974 838420896 785593669 295488797 548172466 130093195 844134321 178981687 213329874 241507515 333995446 532717765 912403275 741475628 459159167 520249642 500283186 815565510 975103909 111298752 148832873 600081863 590932105 399247761 921434839 161403465 47208209 955448998 994980906 626639025 19496307 188511627 641233329 82554932 347802489 903097476 381736341 761962666 424856580 210046519 458563117 474793825 693286914 866735139 496127319 182161051 462453628 73044750 255699180 408958671 758258007 255127969 940306816 933440675 277762585 134880939 195452449 51227981 618982669 807287403 504498709 570544547 428715940 874355591 524091128 254949340 291118209 761421985 904012411 206838504 422015716 393145318 413918995 907549253 59687384 128606703 561321872 391442768 45629483 406228587 473808934 62639829 862904254 34834587 957173313 804961596 269560614 225442410 171652738 364468705 53131524 323661204 231343886 145476584 861815505 313030833 333995611 304635438 466657094 78798199 359378692 154479401 704461113 173854459 609283813 901184855 182288796 612719586 311027732 165120526 308193445 736441250 177778737 153610688 346650377 916441939 933323436 769328709 105726340 153697076 640303040 61299403 67638989 37850347 477794471 297552987 950109846 767559884 982598918 972134891 563294166 608620133 531688780 643045173 850454324 389135317 280227616 470005068 647947774 468711183 555729805 542334840 748112889 940077670 742489114 184406628 951127587 789331561 563104893 93855030 101509132 936861801 335164612 678868891 391872638 182987604 348328219 506387082 830018923 869715815 306662941 792437067 22961155 788600144 873473017 84901514 966628652 708722639 659035180 652363903 492325875 368045121 478948154 538227719 706064120 189273499 95303406 358169706 968599819 56214746 424301597 115993374 519362173 697168272 34428606 55109168 807591062 714291061 801400049 346323321 103070422 394119074 987462357 840770629 321150888 109557787 764077836 313043444 532535264 883832554 407988824 549243700 204607843 742476204 566774516 629156317 522542635 282893124 93763593 989403657 45127186 85770943 13698350 580009551 820309947 317250764 281860515 705643908 32550663 692018618 542484785 12284090 954697470 289606555 483666464 962942396 924511970 273817423 881721530 394017980 386194373 832953562 290816468 687212724 784740259 987487518 940534348 736587944 864855343 865187960 142242090 11825025 519410182 141936541 170417119 154069619 851584631 727386456 363988510 823419462 291921815 901525108 475828355 622143776 850954534 964721701 971291187 683049579 744030098 381942068 249982422 543978668 101304144 653294853 585032913 138139490 586898740 343449385 230284607 622785970 566428941 621172267 569384593 761880060 962936977 477034501 779201065 595889695 747366201 153703241 11144602 336515104 94608496 209067597 744836495 159433051 576863752 384207733 194346063 678698733 608921646 915577299 292007412 986868681 796867836 602850214 671221874 711652683 761170760 758833874 150175896 332549461 325044632 797543533 779514536 432682016 135498236 709745344 78710629 885928005 515385235 758311976 78708976 899882008 640398760 233631993 796758990 397965547 452391309 694355311 457861107 320390182 722454292 362761823 752862834 649735340 479058798 66206184 924999949 834616722 425092113 691671085 313790667 253427604 447820576 873391754 192260954 655014483 702765494 109794926 890182650 426908820 59503977 944130441 676431657 761576046 333140950 139489162 390363953 639499406 687544029 210771026 850484208 14047592 224286283 967955544 287722698 131243910 23345943 978580743 612662398 222652964 458257526 725418842 775665971 153550124 761718446 197500099 719539332 903527409 883538653 391047916 516321321 96282865 861128024 718036241 917314301 12270961 509825099 882324350 587555791 588596399 294446355 634458892 500026559 487281210 31651082 272191956 865951747 654613456 906690713 873294048 983561399 450542044 875742939 442187274 959737617 893047226 106731749 704402219 363962662 773939796 224463413 267913134 543666373 239293682 907651004 844534407 780524112 210706425 543186966 559041779 132392938 410505052 51979221 225870239 793313228 237209683 524499483 269509052 147223898 482236053 674606697 223917861 458430144 966690660 673284873 990313739 760925624 118974016 132584826 597095686 511032171 743484000 964571646 41349471 91186359 578856340 706125424 573000614 894187271 469154662 724093054 940560567 738503769 907515070 444773787 387416625 498613684 669902660 799552858 923584032 547265739 909729980 218001921 618121186 58413344 750806893 516494979 3577197 541844539 905020516 183497334 587323196 907289213 890912966 27202201 804546175 597669926 12976903 855241451 270735145 850291943 32276330 328816151 696184255 79422559 285584312 672736864 416030082 76747553 539301585 145248631 817996509 809393056 333119156 348375257 864846625 643307904 47859194 822852786 803448029 170777716 452803119 174673842 318274328 799552389 391190022 449771788 473382456 641061346 724474939 507859519 925153627 170006692 602657374 714727989 389829966 418195847 544083032 355977458 962140881 621338233 86018126 756575052 249252660 606409896 421992921 545427100 362927118 638249355 53900088 423265488 418009914 79689460 855309127 920569747 766180267 45796504 398718943 623385578 591583597 729178210 586068498 26441346 15528550 612700910 29756213 397238452 772610498 628312558 362614005 181708050 940031172 887840523 162658044 769582947 472845316 180283912 882066975 640361079 710670008 335786098 233787367 920203376 222723774 50965404 385801412 471617482 930419223 963756903 88437700 867611047 441547818 125257213 223479333 40117608 330771634 288386971 681893894 870626798 634808952 305180581 563524327 694655520 96530816 434156579 77324077 860816006 265989258 390456267 49435418 87921945 580583206 627459257 648583307 37270711 433720430 217607745 387737477 312144219 419150259 437666948 963095729 590217034 321137641 992864326 815095181 649213637 369107066 134216955 877954388 863358490 555773189 970000656 468904447 154110935 936904560 835885881 7219876 641816124 301408350 99130411 703567702 312297934 280958007 316406674 602044086 423040505 930885700 186440778 616471346 261890142 886748788 914467975 878167036 814141227 357407228 75404597 564625277 335063641 619014934 549881058 179740371 76427581 755677100 686445144 563118381 478266649 806069005 170844469 531745719 630808157 74437694 192398121 467359454 259458963 306341070 150485745 331077724 488445450 14023448 417003156 387491951 668597445 184303580 329530976 430077234 681179566 509275975 312821794 735196053 187149047 227317244 209395904 898056299 541859582 42455975 468316487 754106519 352696729 806707479 625309150 300768525 970961534 520352666 929453284 327081780 23880801 949482678 43377084 880984376 9152097 131685174 500393503 868801192 793592238 374964269 209435826 215401756 389298378 735677856 96239637 17921240 320494124 752020823 901678474 225046720 368133383 560444294 876213767 577008254 993133724 573962662 562197115 783658035 555845922 799664117 136487372 886317500 515181661 314079180 933762127 425369122 184701640 506980926 330016010 928576590 951952482 333996614 476590767 202000530 308363631 51248267 345392152 865854168 742895529 572559710 680320499 916236811 781297982 648522382 540884195 892293013 561395212 778319363 994773224 504647109 700254555 708522490 255828400 493528537 580620992 617550733 409700351 288481879 518557246 295268309 531068161 144269932 891235496 441929163 700864704 180738418 857691079 777537960 389956509 869857279 225642290 115021216 516865661 527162000 678093604 528067307 952999357 915776243 659755706 340205361 344860498 960526597 256363052 127722530 496529968 497799795 776212649 962240829 77733807 56906687 726850827 448692376 906915806 339995710 383101703 206818179 221634266 825087764 46114712 108188046 87507971 674034310 666955604 687960869 203564564 53184032 554153935 134911495 722873235 248907405 413586609 497206329 55120585 666421454 643942251 807013336 512700700 329577365 755234462 155653827 772178849 177232669 881165576 679393700 404245788 478824220 835763758 189605318 737531265 590022737 792050473 602489391 50476312 108213432 562411888 340919889 811508857 757638478 675940436 413529764 720904420 171155618 584300647 92381118 921867525 556193149 426138399 236964987 238252902 911447142 430977036 427131972 794280554 156234826 334004340 225735250 148879523 615416126 623000721 206889200 321592710 408072290 411452258 803176860 890759348 883946125 193667857 991544114 604603855 266496022 72170475 221403046 252306251 891644114 828624337 869664183 558944190 344356699 201746348 870692108 142243273 894718621 510470256 853412171 87144373 473708747 687017906 721965551 502934314 445909960 858527885 647402571 759397731 757410445 302245281 818044119 429644194 927746268 934687229 165611811 905996733 117643771 986590857 136766747 723495472 305983302 833935970 159517753 485555897 566605207 380709160 975765347 272186967 623154587 310302006 75742844 560639645 493415377 134067673 549371028 548808461 694596723 706641809 285754559 8305444 568424747 707979960 594427726 346377057 999551726 680945553 948812702 684455801 56994198 451622764 860875508 620054013 928578227 569609991 582469696 749159653 352970967 650017003 611009395 84024206 689523052 14050229 208846019 407160696 332694001 99318070 143469119 877711280 325413625 776268785 217899500 236661429 324603516 486542163 384411771 466527278 230470919 627055302 718886125 330733454 840632353 968974706 422218238 348352152 612532487 511097362 91305157 915250890 476417431 961391465 373471841 491794895 149750147 237598130 723921999 118640523 235381324 175360212 222786435 966972709 368321545 39584511 910003894 841641033 405837391 913212736 408488566 89144475 737132265 731959179 609137083 122316210 545017 581141062 435718564 310601653 255237685 655099354 208727750 840808191 344915434 127629062 446202793 921353899 421369955 300356929 19565571 778245692 719810207 181162155 497025420 946627757 488974807 698561806 389463335 926124074 834436188 953809684 976764851 339715299 65463979 68336135 349876385 810504957 906570847 607545521 665338763 627711220 575605992 305772150 197848883 903822824 65774704 462208789 834360265 371343585 484013129 537186597 572213929 22558221 351510910 591263237 591214650 981628647 216520362 349649035 485163941 839471557 599934789 670691375 10163169 732137347 227554473 393112498 194654576 779208735 283907412 829421080 322332111 297190815 332796465 774260651 658603278 281301001 317199257 517952477 209218070 201014025 856251793 522689359 309436515 464593394 138749529 196099772 432285600 155054903 520041039 932996025 232417878 460157884 319520559 655912200 801822475 540257979 180643671 377122312 403776591 506448258 885338282 655034362 797002852 955813846 630131246 540174978 804389382 720539675 633164196 153755377 301469772 995666609 30688348 594789176 467454975 4075228 671381781 899350468 234076719 345572667 732486860 342542437 666233322 511531284 565991730 837084270 33228715 513935993 208911956 372258758 462432106 888093320 354958714 154420460 256386281 274701910 713809632 834694633 553486849 33687395 35278881 186990736 812658202 732764031 127849107 386748586 174043851 408417326 97961198 472651474 520716561 63082763 173111497 873080538 277260395 37490250 659260420 464055725 340866755 744754714 71583224 500111066 800623769 208018919 52115911 771881972 271267279 65546261 155027147 784219405 332000680 301534903 166848514 234349347 827877042 920881210 579401324 881799547 796439111 240206635 665364614 339494319 447549013 295158706 4331329 466022657 320652255 795685917 805234386 383438401 372942230 510611327 886588769 66887465 398185939 180894484 722706587 828982460 535306565 704818176 315177345 555742587 764908892 473957767 753620171 319657213 504726538 158219342 250519463 435858205 648671144 819711143 379459868 4751611 964257598 716794397 690834345 536185281 965675604 447637515 530461601 882282197 664460155 771428789 15391364 944155713 586077485 915814255 160717592 164206182 209746489 759241543 40444477 487535861 199413677 526246037 908798227 495872193 665299021 473630864 804258451 962872298 397152611 302902774 272926278 483166904 338900443 631854339 304796017 809871803 72805370 231586869 406295668 300167617 540265319 298967185 572045077 497724808 929627573 454095492 33823601 699016053 9613519 191516633 502867073 580014496 646547537 270734631 112572988 900168584 465219489 754337032 305939741 797460758 547604069 349673010 556113562 111952604 777368193 203768527 769837346 109821891 722047195 985714752 767560994 686893138 194882413 652230318 57818179 115638303 682164798 85300864 994829897 144123156 477759113 660024486 321545954 609919969 175479303 767067098 977117896 651938374 261340183 915839887 855541569 317355924 321419593 555397406 565259627 691350643 766536928 14557842 687499470 123985066 971931851 558376059 175443321 931966971 176573617 362069224 490483870 61919862 686307491 960600553 599932680 323914159 377580785 870563948 190091812 838270509 721777065 778179844 13056786 970970636 903081766 946056018 393694066 479533225 920294227 311443664 61005497 845074758 637610895 121430526 513631533 724735492 17516495 506693919 777559124 24707689 220184976 135028537 811841829 915529757 603951990 155317749 62334118 325134175 600355773 779774228 200048673 9798772 767729187 459933410 590012849 26489395 123771691 466443432 308652142 321600621 209457150 440100415 612020335 489707616 850498714 82382899 380324652 705213689 636970527 637054042 595130572 252408406 899737862 808029674 157555533 309637898 215032795 76132756 922989719 979307555 794026986 470379435 930947608 976139215 437751895 174034794 792139195 751495362 812984214 467697288 96645760 859063669 346375798 88837347 561326737 311032007 675233797 760314079 341008574 213807462 989323953 204664488 92130416 581456347 127089045 886577395 9549365 167923862 560887061 283114083 890039782 11463220 919466316 846964445 821236793 703767562 670058540 998056355 250122190 609070485 708857852 853969020 375002588 896164355 589326357 549080283 428623835 440491970 687766616 201465628 731593999 221954577 351245224 657102242 265431518 836312037 411184622 249196964 647917468 690770351 583014426 781930539 866801241 614760969 894086699 854695317 327411224 346806454 358700025 399111567 726800872 974129684 707897627 607132369 102547312 21574901 777760328 696284191 206061817 713952653 939938144 71703859 643771154 704496596 474047848 528608189 303612069 755617090 581911813 12545648 760192115 336156811 485183312 505494088 939530353 893363607 292314911 826390371 811465244 744173323 311262915 141133200 45744289 214090650 783575810 935837138 572953597 85639864 732893918 623112190 846437309 428388975 30353914 79939109 982645911 270771977 299784045 567703782 910574746 757046409 649357595 701598379 939922011 672646854 212005895 968414158 293766496 598074773 686585878 572970561 180040924 863037613 880383660 234302369 416670704 129796836 564313570 803332325 947211426 301855776 243616439 388523554 965906150 553613925 207725554 952723011 751084887 544806421 315474856 143644276 14162106 987048627 548148867 198676411 996220055 445422893 355777649 51131374 16705106 205314749 240738373 478436964 847115112 509173441 869679251 50022074 464531974 571556834 792252029 781022327 31979897 6156592 434372120 130318870 60141844 642093040 927375671 642831455 856333121 770171906 328114349 768106419 33481819 401080294 889657029 188463082 770384492 845354507 491304372 547862125 966877086 976742192 864511657 332076311 338744759 891823921 923117294 381159300 971521316 692368562 928077564 319230676 913019468 837851778 552339711 43464620 68716339 73843959 227659122 206405551 755617769 106842782 286172904 356979353 333063214 814244192 332778775 508679076 508321360 471341905 636679963 195348863 951096931 140155565 632930443 289101735 352211822 853898520 696441458 116573469 386844046 335020781 536376936 685213384 951176373 560814839 760618103 672506647 485924470 195452838 171735718 641405630 471027447 343136098 7646108 873238768 238146327 418085973 990269661 638680951 660040164 8745893 710392615 783474647 728039282 909231875 12647295 174438038 252367216 610944730 853351817 620119382 659280470 517768468 156282160 751488944 660276176 28605025 617712463 749852086 805965838 471543527 60735810 273662951 892905834 115815897 88099414 329134579 100251471 677764322 623974009 2162124 595268719 261059449 855165626 618310999 271518697 572292081 950290523 926362608 83357923 715888120 669396224 497723627 224343842 275563677 889642406 942887270 235059870 88879649 485340044 966614368 358016642 245862342 438851589 494509056 462997489 456424829 830626819 81800037 452211335 797664976 428869892 216302751 638307973 113560893 318070684 436531919 349893308 717461867 161546601 932452970 157773092 553160155 447487350 837362907 305108539 198749571 95071590 384952702 56108049 568884014 819520818 298836942 273266091 556280366 409351492 40362165 194725151 749784135 242815933 743777303 366944427 907076289 723281970 818545579 634431887 36495521 655203975 215511804 681315829 287818068 14922346 648858512 564520750 735047882 305297259 482601194 346717190 994530431 127304571 987433930 493172288 747378724 184184899 23461663 208702567 837752068 129010241 421633067 985769388 538762558 412070979 605950769 718398933 391798301 263428892 867450909 364331700 853626440 196079117 615790359 663584358 131252194 590979789 739732719 991454788 809379255 71309444 304552890 88331683 505542630 705419406 801444525 601571874 397185779 350341595 421488733 572894857 684769871 462613907 216986151 322803743 460622030 957357941 417261962 34214775 54243077 163113721 927755514 267827585 232024939 302633518 946396469 108831904 606709824 155485677 148621809 406037081 560262820 565309708 527172535 117387293 670234891 700227560 61119752 371208236 922368611 105570924 544035482 153340956 655833352 829216343 933852843 101345879 817290334 22885201 637859278 64276642 879510297 33024470 819349621 886204298 160655759 344840789 417637988 193519457 32611071 318051088 415021682 139857318 342915935 381730373 201366779 156364949 950367633 312272778 103144954 671996604 104855276 44767513 690560495 9904437 580119242 130355627 204930074 275071549 300559207 704422694 990511520 193083742 59235558 314988145 18798752 516898884 907719056 735608097 60735915 505952128 55456967 909616970 751750949 472286850 132065727 699668368 919486173 752417814 487112731 740593097 422239173 853565412 504295884 604828442 143709392 444055836 125926608 624352811 298670134 313165206 517539461 887001526 948327001 726778985 157911648 565726758 247852141 913164305 659939169 107190575 237834966 930378535 790825287 29268736 410507600 634502479 690591368 661837606 529935667 601395565 802986543 857192153 908897877 390198341 393939413 34314691 541457803 311164581 853006918 10970419 124694282 211061368 859876780 411285681 443760985 300515687 911137265 992375737 926545963 279543825 774637492 310632519 78044738 418535023 528963571 205894986 914821015 618443855 405268528 766236294 159938660 991126458 605539783 77268641 40532877 352461086 41373734 592742958 554193711 2366457 897624799 689485551 352898478 162051365 495435054 870234826 881093507 715255397 160826241 318134405 152713710 419368097 905506171 432333682 679087665 879807562 689206189 994359778 123573041 3047970 564693331 766319928 666936117 176408696 654098968 928763200 481843616 988621669 667697949 794692233 756383405 113323815 959240539 333073457 916902346 691501494 247000517 951971409 351336819 871884021 329772388 346460087 687987527 554005882 917552687 461790282 12027827 785653834 372209883 783657426 975025031 227300340 564774724 457205864 954908093 707040468 56070985 714830601 58742406 587188675 481863066 384944303 839353355 662931528 570214641 982338982 91869266 96268176 794366444 814109284 472026822 431654671 139677712 619026687 552819538 967607885 551578744 277077142 212235319 78737926 956140488 143182149 598604057 959449952 451524758 113345998 253360380 237931550 411247514 730815613 747524199 886568531 973252759 50130968 814517525 642881372 732263431 394611237 561898648 617935095 584561741 13924200 493644055 741907475 296128719 960687327 4702240 990116491 148643758 89938798 512525394 378574970 37360616 785202270 54038721 479773547 949925549 355816915 132575315 309537373 54750249 225788310 774452881 707897497 461600825 745672033 944294149 286997161 138805289 513481577 939006525 606788044 183997643 350141846 885401421 380527496 281930712 915795423 295980408 848332489 782383738 990721006 524433682 601506006 785789731 911354193 579486018 479727163 406101238 789622849 98053937 796867968 964383286 364640597 214050593 642848315 896455704 446448118 149144199 492472065 229638012 706504678 102195780 875550611 11810880 824151837 928772549 593142460 28086840 53192522 673792457 557765035 464378161 166503937 225134731 614443706 861110974 434044581 860444610 976076861 736821358 936885450 343581854 787366354 763372209 643787566 788950018 228945800 714136489 360312829 808314387 747927282 960557225 956055114 701297543 999620320 180367212 670641137 760822844 853689996 245840208 772381971 217997388 143854496 503042768 554024677 341563537 599575358 216494187 63158109 4138664 238462274 161522039 244007560 611561998 239874885 97649114 784819926 736627553 29005120 649352375 510034967 615962639 940632221 182059230 161725870 580553803 733323534 629180499 261574827 883929180 440293954 353797636 68549112 585408326 704656039 488225587 426679008 283714216 697576183 785908297 815196436 876983981 388937695 113287999 476700605 96639153 542088249 798038352 282344332 813857822 242473882 624348504 175818335 906680400 194492529 3004976 402313265 103286543 931531862 486853806 897974053 871351407 13917951 544972201 500425399 246964474 456829276 32120132 642263175 303418656 469528762 797239581 269785680 382807645 682829255 333656279 531722625 952856977 599942556 523194339 65556477 397347114 756188919 371077202 626532916 723182521 916365364 958699514 134089276 161559893 104331271 839808659 986481376 223131954 986507486 414519245 624661069 7728338 376878571 190024409 757111623 507122282 751204675 571706551 97257125 150926222 187181771 545360782 160055338 651176968 526197381 566281629 802067414 368237194 986475735 696153132 157197403 663123256 730037864 455303958 838874187 349988334 159619168 859134024 750717759 57796167 542630025 620103034 558954857 390299 221679868 954324876 646031775 745984386 916646726 212280210 541670676 878807193 863644803 354270076 108711779 421422996 76246527 356231874 146831309 864542465 130270441 894542661 706978603 439578685 686920656 98402052 588979460 113585145 201057722 967792368 580786972 522945307 220279209 606734871 124184962 267016258 578276434 567591117 817414728 384112465 821307117 916824058 153249278 552379276 330832111 246119242 363186723 684892787 963690697 258450227 685701903 11728678 440700535 482783279 862181444 58613814 901783137 14544904 31043990 60792849 563288879 354241306 782047900 453171886 12767769 94160220 284304450 662933146 427090581 794302838 163851581 474935727 5287421 82316802 313476793 647089210 500178879 129457299 410543588 933166226 919975803 209892769 44428579 754452074 827777367 58070777 755720220 185621250 758563976 377210931 956995842 688845132 622968952 253012459 33261856 10810856 62565006 541553902 165769361 759123608 17244662 375172691 423925946 491683026 291700126 929965416 269148999 508491526 688242600 376878345 972276727 387453967 119786070 754728380 709838143 457226174 855655805 769322811 197001780 716358237 479844643 273384867 781021434 764749514 550832868 214019763 698343406 658331339 255050789 932730844 255579776 453655425 665077930 255283775 88170514 554277008 452063020 301773073 226236017 864042594 704391331 452278882 101376095 545921782 531955237 109818711 498312373 728641986 918412029 468249106 903028896 416243441 993050189 69488334 947977101 331657393 291348026 966318130 782280612 908009290 290456012 97502831 457501449 986106678 579308874 627370481 487867366 687450910 966362812 989613479 35429774 212270455 218615816 328846832 367694120 57323097 144768273 650698596 141774169 415891904 847859971 761644756 340204385 751510683 388377266 505998696 268146101 291762303 55775610 731259862 244080409 106440791 900322289 798607480 895375916 127908930 768744217 217130620 657515649 907921064 105084906 395914035 243677803 358141096 32267306 700953631 481458995 5151909 765120176 498748847 94834901 375213692 249783332 524171120 965152538 20712682 74750692 722407729 520967749 468747989 120012593 661646027 539316895 893618214 295689235 299276681 542474623 8057455 504607035 896910837 387044934 312697729 659519258 793933958 812303725 716923311 219244456 667536098 200831360 664750390 740683555 563995930 957035509 878926831 243434723 118831111 560537830 464114588 374105872 590214645 653172261 234327356 946508047 914881960 125181149 238444082 899539163 136560662 488553915 7838048 998470923 973436624 76148836 241208199 660694540 333554277 471837948 997625664 19867086 95523855 658218495 89927032 357447803 296151764 551271744 737436716 73180239 676735111 124836755 682137318 72279080 464557908 70981992 91295946 294145104 540443881 836280335 753996976 505970991 262629428 746705918 395240376 411889751 621485618 97730415 517570630 373074059 446915950 176100005 327370921 270623355 821536280 776200656 17826542 792651551 500053094 75784126 513426585 105599628 153687556 882351211 712480731 518063571 942984605 286562983 46674594 589986848 405214868 512411997 11733875 261656171 787219005 758108791 46150797 682625704 693723854 203054356 291073842 376232771 745994818 505124627 651606026 34063049 797769077 692056271 572339653 710185875 110951409 6251195 439506776 528302781 713528245 85871901 476227368 997191457 53587211 784323874 245471598 808968176 245601440 474929018 639807434 760336359 625460905 878176656 644518516 435516449 349961814 560374278 453945831 612664730 780905758 648745961 726737359 237006272 491491222 477723602 905966050 932172464 281420225 795973881 222839769 642408585 365158599 767350772 819592274 637726645 417605809 573787535 244357071 548806273 825177444 92516413 278532155 828755896 604605315 769117419 199920173 600893409 610308857 643229362 946693426 47146843 574375470 920503124 959449073 318737066 1162976 813011106 331132741 179676528 293129549 274911051 722180061 946509461 44237312 304259260 429633245 545420138 37426886 53199972 461736811 738177113 481414579 543807382 337086406 632465916 303739933 527697506 312592859 451029741 901472758 186733853 650630779 738535850 516514500 933116288 211475370 158891502 823399609 655575082 813581906 110746548 37438941 100728195 179052259 798584664 832560485 980844498 307907167 609545514 841254545 982326117 802499944 302322791 590133707 710936602 16694529 765167232 138420534 12862011 637914794 577562809 376398458 254451610 7751248 313686845 814883786 905271926 648364641 380479254 737522834 519995240 504465845 512187671 325911827 18740391 76812570 523740639 96750580 581292691 580457171 476704 293265915 996077936 211507570 663111119 448950833 26278284 683585994 573998726 13513320 895157400 29135995 145764965 433946765 847374169 986266927 450299165 704487575 957395836 945995108 777675402 80745034 141550983 780226388 191354828 846275178 241103605 781788928 906819487 783286563 318007713 195822553 348135080 723354078 11556345 157087757 279928491 441416561 927297520 135779091 599660426 351665714 259826805 182430455 585637440 691418069 754133898 112054498 519242503 503662375 770592403 562411 853890323 849366379 987167452 640582167 858253127 49782565 183061982 836452273 631634591 374011893 65729772 488103689 804704631 625784258 972020088 253952750 340782777 751722025 578429694 472490951 35112390 488663130 862568138 183974279 972418978 403368506 99171115 604430225 853618994 291091206 715872426 221289557 70917870 130716194 481303898 824653224 751403890 239531433 507457877 470794722 817198165 220222328 629680167 931364103 45741121 490760214 798961776 875351223 436794295 962423581 713094522 428941130 251768085 335671911 457814852 518546703 762527422 787109318 962854771 75374753 651796710 506412993 259647706 820254057 885795960 334413313 277071181 601601006 373606939 554827884 641204619 72341807 594658210 620064081 776466514 889571318 469457470 699456246 786336780 209763266 613558269 668516352 251825356 233964583 309259385 78602050 267056729 520535550 689125219 713122815 319598104 512981626 57222553 181158974 27426114 216228540 918179941 21503018 12157965 425575036 143843490 126798851 338392171 992550702 935186070 150023084 273627782 701784775 548270456 788485362 511407788 16915028 137188869 670304799 221094140 228263495 335195350 164930023 200182428 853006432 525992108 784057181 61125554 8481195 946953780 677678889 715985002 198345664 355532670 631411549 278909935 839667305 732672534 504094381 650962374 965184525 17326327 562256750 568180436 727898052 277903535 250858579 489273873 534032490 693150671 535064077 710836497 294471468 377980483 747013559 227183316 16446830 876604255 820118750 866630632 185716614 186571737 500009683 100332772 271464418 541979265 950211247 91842847 426421085 608181990 881772956 124549687 781145888 113231301 683295924 825822589 876957539 424020785 926025934 23392812 154870862 35320444 663002472 392004300 638345568 561870652 488153869 201536749 490595736 564353139 97485198 993299309 652634893 430605271 416051301 975392177 571760827 535354164 438333542 950497702 536781863 763338752 325325981 904968542 126427358 340492872 78777651 118154177 281985565 345188007 730854000 931625532 567552381 531307110 982085206 164550822 188326131 329786870 704933845 426490166 791864308 550273238 481278226 883284719 36980732 448195973 924962425 747625225 245922908 626941481 359023037 116720382 389176686 993271994 822943792 939462570 507905854 11227617 29341282 756122361 482087317 232500949 523375997 198704704 887812720 595794813 313451941 713357371 89908418 581008845 14542004 184334437 795661116 327331881 359869570 906330311 806703874 282091574 606520737 157995813 113904368 684764186 411657453 526145329 736049334 96430836 172725460 896519258 283408114 194356512 826872617 825138040 973480724 232482941 571221991 425329176 333229277 339787524 412497528 379750083 252370761 282746906 257065294 781903694 757128486 637741468 145474925 886068992 623138064 314284103 368105962 889130920 506994534 783275147 797337527 292645309 193826465 545040038 594288409 198297381 106359533 68663914 456827215 268499567 22930699 274080360 831702754 799506804 337894885 933429743 181117677 806643317 906850299 966937958 567164317 412008950 797635018 684237647 684040941 982277984 768358903 819230745 151097888 56280888 898688836 325077351 408476681 709154199 500958509 410134408 308878298 812030517 881541395 61303413 411212961 850266743 422179693 581234311 933607570 410419211 518124917 458581515 489486747 908689670 240790152 197412112 99116895 202995960 28626954 932069474 963701131 897446296 227077539 462853816 483575266 396077880 167189406 782114961 431528798 444451259 178307379 197180424 330903108 886907817 408232661 492367437 830689448 574765816 613552214 533776364 300128387 137106016 383528609 732492271 906009177 482638752 910528577 902751169 724311143 240827251 795538956 592206515 837628705 544443238 409588085 581888740 897789262 991862814 496915116 224940704 181584643 998190595 34311507 916521062 192174880 441058423 643425678 863898853 519700439 510519997 651213741 258551377 693048908 665494493 986681797 958624618 637696622 94211611 847743765 611799392 949649208 84499029 884564438 677697810 377853320 884980166 401472512 647709750 313314854 467268678 73743378 516364679 596271160 381741845 32226561 192983032 437981691 271153405 154224005 55805253 516897983 427345863 569047908 857705551 754922474 611599569 89089772 455966789 13354430 327771377 822171086 183294948 638556485 453340588 202565917 935523702 765263822 753401985 496609872 59855822 630831631 491843927 892582919 579862902 256349577 272911909 85297822 382190218 180952402 962894284 572236115 82429088 159796785 96225244 362253201 468534047 529861864 935211589 308941450 153570223 795003363 329294160 652005280 235676753 480906765 855363986 593087896 742753000 748562074 449390054 718526027 776637317 37901053 240736029 876870910 306768280 326890841 953255746 922782610 695637974 404999275 629377225 849376558 711930291 593169422 260342041 152695758 209375648 767339299 443227922 643839204 353565182 546172786 247101878 831982830 877615135 903797982 58258425 839162162 116984167 111921405 373426175 934965572 405159673 885546432 795680953 383668491 78996881 88822105 441740948 34112993 243409974 331458831 638517439 650122903 748230765 889278964 899283234 555520995 134410207 599333427 638863588 942212087 251572120 249021573 329137784 429978502 760257347 614405080 878157596 530260253 53955369 255226656 659735834 592175736 849888462 102812976 770981752 91793350 307228585 345812299 351753350 419679493 815130042 805963778 20123503 564266271 105889557 112055594 814174416 347031608 573729766 427006848 307033225 408499487 643614964 155633279 269768690 294809540 117171059 859817887 328978986 854989848 365287141 108286325 905817988 893173369 103470883 978365727 729583072 203098332 18692164 73473134 50605995 598408345 362993713 975903625 999398631 7666328 511273153 731626150 147825016 686145958 94773185 759389823 493281034 580034740 446498655 439060171 471007617 914359471 289721980 256692456 353443345 754062098 442790527 586848337 216929395 496137867 694295134 57167355 998657781 983286405 508205963 440281671 931508104 929124452 296884255 18238803 622349005 268323037 793331248 356502909 139495435 63110007 578768800 450997148 720383135 503429686 313552947 958962010 205095507 166316378 604631478 930171856 455289593 905697514 121063665 587086000 344939408 135755665 412228009 301958857 60993891 230801082 612621392 792141046 647007883 901674286 431886331 903191219 995937538 656327656 961599175 846149698 886580687 686021194 415041688 487926212 244277055 516043475 537709542 652483910 404971616 143741680 324422023 377906724 519562214 124215518 501588885 823145711 900753761 409371584 461696978 435135665 815815399 261369304 387586966 81031809 168122352 760106300 573975042 331977007 119325754 124173857 96033936 906092468 678592560 625480287 510737110 398751902 478623609 309067538 293705973 273072759 603983704 467947780 851148018 2468898 627510111 641265916 157409216 405301419 908261362 749747983 859676368 578058446 293991553 828089022 959675125 960476086 476457183 478557346 121470338 984543589 372993125 893281593 100972815 918802422 497017862 587660842 375093561 377770193 351763095 846052216 483574129 363721387 49441669 800893156 893331290 350585041 438690337 691684439 527442765 714852344 456062481 25241087 997290836 451247111 488533455 184208869 585332517 882823443 615476921 948822416 434853337 482832443 750010788 230188210 204263718 81058945 507956797 717715034 795261213 676257711 739595903 814507677 519964204 103048827 886033252 471105899 865952864 73903037 864062055 897209135 151166902 431997622 806502587 930623469 645303437 222091840 733492272 819662330 77675302 850474320 60313836 246417209 868516377 593724644 627049792 826053233 56463981 446277279 464791425 883839873 930850562 122513129 179037096 854123214 994286339 327044929 988646267 482149249 679672819 124543229 679246512 925970745 159330078 522462671 786107821 534033090 838675289 333015025 810962128 313194183 615006596 977883235 800099226 129526279 536904120 617278918 167787214 974418032 540456684 866116220 289709224 767091685 112319873 662385139 589748507 193019226 382431550 220596818 108962195 726987029 99949116 172173250 536343563 816898176 39961052 782353701 265395970 55054636 524787921 200094629 2054146 42014028 618930178 662646330 592628136 461815728 498003760 110464949 992020983 865119097 284946439 472507359 675222093 574208365 33946043 283264373 705862454 228245344 671365418 298114809 498197831 115872492 427700627 542545807 562017159 214434752 431119160 135994744 786245754 759593056 493175906 98332847 372124313 148511829 901903402 515375167 869286428 498197875 861103736 150703637 737241974 29991711 11927389 501890923 360933409 441310383 637624565 986942311 882778294 755875871 543533779 94890323 743053765 928504452 315423741 269288882 471703140 845327045 309200083 64976930 432916038 426754966 424141272 404801118 447038574 510929768 37835943 652776533 683711785 78740555 335593924 802259893 754749171 46809556 506241180 99262504 24918688 809906379 342874474 871195205 449573682 328309271 239250094 768599252 432552174 378452614 812318378 485445820 844795472 159627587 146914858 101189789 358362419 150269500 977776830 209392501 902658806 872530484 122311635 23434618 683327542 185267920 306776082 323351095 483722261 411619173 145968022 397073423 39635923 824700349 377696628 340254638 318064541 379119215 880996899 40443844 903271833 842595404 200997431 573187505 980151999 797084873 446949705 267495578 753203018 184287780 914676257 26958154 943237389 637808782 163165791 502218773 216381813 321213983 786761664 64125641 960108697 756257252 249651053 382167644 471181050 399401198 709148292 149192280 107204282 883238346 308889943 221421725 758672063 81747798 946624118 897246865 602723794 385016640 347627075 428378161 397842960 747124258 412239781 225891176 854418871 697256702 828798999 18892317 685522510 56626644 28651981 308555378 216169634 874815093 42707235 412181277 626173049 660690229 241191789 378381789 309952902 313889903 850505511 905793737 194806495 916462396 24348413 167643260 944120273 559694256 74358744 897502590 907984448 204058109 356830779 386692744 375394570 709194929 278028399 521179676 236778266 718478334 113345135 81836032 398944828 773907176 186671973 565758465 668119865 698212055 302135374 884112066 451868061 116073505 146890126 181787418 569230942 956216146 428781744 281328501 879187641 214715739 182253682 511372652 75242361 114074641 79215682 968174867 683198411 471888982 716581532 818233267 30316150 907370427 120786064 363375390 192260928 78646571 105858675 126376649 70822107 578274886 853314683 697329887 931457433 279974909 423096094 319171470 300591173 43344034 814545883 846219894 229569196 650807445 444443639 752241201 943650752 447407885 796926743 972652508 625944944 531105537 115580822 354632468 388292756 594289511 747356603 490296668 850806648 309143011 589440352 314406571 107933846 996075201 686858307 732666248 309948335 910091204 38098180 7378362 99647454 801460944 136642566 701676391 595925535 166767601 529082993 796421959 748840775 759076718 229681134 747527813 118139885 545420474 626828801 196702040 806548774 510113168 882631929 533322506 149649095 527721087 296489283 789361113 921941787 850687243 757715369 388203446 293616253 974500636 340013675 44602503 721461398 549950114 710912870 490147851 309298631 527634322 874179878 174424388 624983901 649139236 179390728 412813603 722641753 716804090 379468709 866371388 637316416 344736113 612375502 73400054 551686757 431115056 733982881 501386145 6086848 332475857 366303860 688677337 771591101 470543751 502700830 174992880 448327741 299623846 724272260 583418083 554369318 128218068 335922878 510679445 706031620 62659229 370252914 692942654 523283681 702985730 902430332 51281249 921543382 509951639 553217599 798997829 609514884 739159787 564274880 670869938 539962172 396014745 253237042 313543096 196579100 951059954 713056862 347958430 770608112 96056241 757291899 791859751 390153027 909050757 338810407 365238510 704137990 15877256 62197354 746621940 763524146 657114973 692371507 176526174 538482178 328251335 35411498 482964063 716112201 383008238 405995925 443781675 996919188 915927643 484817132 732391427 496848443 411922863 344536054 566251619 599616631 964001036 122939853 983336136 937803129 562579373 839086141 505773559 112257558 879332016 749071431 226572490 169013649 586053734 198690499 597193398 500845397 912410212 489948714 699244041 183143863 382964670 42359800 606564173 967334936 466348352 150871605 467853789 671224911 733645451 939279792 532764480 3840009 836853478 321608829 443616508 460908828 609988099 768925561 298226305 635346543 673641627 582683799 220292150 782713703 637721145 787906338 108743079 72135775 895715993 909492828 961061147 361685777 574346771 697484547 631523914 146984268 780969269 873500424 186634271 632155563 667610861 897427911 773628829 622835469 267049846 324902528 277123343 453255016 181475094 891832632 7736190 109871094 997800215 380709428 827224920 718025724 44030213 304356177 847181225 585377969 53924567 913080190 835579581 23604162 182054679 647357025 590530010 825627939 249388744 223942694 688762534 421187714 14205747 696223241 292926622 966182498 700603675 106129577 261810709 907961043 699914668 438592993 151573097 62032411 187596688 277806404 602008506 904321688 277528596 115099003 736521090 440401898 92681483 586331339 695082550 808921224 175064785 402783331 53444588 807977500 455422695 35205396 914809808 135883707 338883673 957493471 654652939 633898315 742016266 303491491 732209859 771008600 487712327 719107713 932577056 360894713 486174295 642709770 979699335 105586075 153466229 709621178 823214287 22490291 566311877 383854393 658301336 476609210 175461748 862870272 394631991 664130450 409656089 827413201 399613247 42465118 706695611 277843500 80904381 3440082 631898662 519321393 528043858 613514080 210606915 248737942 172133874 523580623 112493761 483086612 237384936 22962129 212456896 138920168 274990596 545453958 37304094 231517308 647566505 343166601 998401400 398067908 496964958 110129924 426944949 23109456 286972985 377796437 419338318 87857594 453160556 682049571 167306511 755724578 900442076 176135878 310279394 698824394 39188354 829685086 83198737 616993977 508651103 816433719 459694715 502103574 680891520 953102042 384824855 402100718 689091336 837938003 905650913 451215545 532652909 884213700 7177664 714920634 131383767 989816461 229764337 703379782 134945671 653006573 926143614 972673828 398245527 51100774 874550549 372390727 664397376 241071625 96485073 424254110 569548124 488501303 986638401 326332343 627667992 116323233 912604300 780953283 851444247 128916448 924124225 498936186 865847779 889791038 430875734 872181877 945914289 903104160 542214448 694024372 221740593 297162802 654692509 21348145 62995368 264416110 60670700 742585250 356219929 218161371 695140414 507980305 166582143 656565254 702942636 769152427 786632110 868144771 124437037 7864201 682268003 199826153 587750252 838583795 311818989 122953039 585254401 163053186 207269355 995985526 912354684 527711533 976815855 25076663 844642410 476455266 285506486 767526986 892763865 793154093 86936804 392262196 230006912 172654921 554319183 511730680 525358264 130650880 94748783 863033924 686902336 56964283 98861454 334603214 63046851 378978338 950068144 348418722 945628224 43053816 860882031 939796454 364666284 834924911 330541665 467724320 76374461 559249136 315127365 50760211 136101800 302003497 792664354 187760328 953590508 350130896 264225 57853836 634024354 736832668 396447034 320888627 127001146 610631111 538331714 431810023 965513295 229283933 905779163 629266283 903940676 780094972 809277441 792806626 250476281 116480423 51731166 346473437 720596450 205681479 226358792 944100181 257982138 225228352 337623763 703679331 705956605 190474743 483825802 615375212 699795499 888154188 162738700 189995127 467120880 74520023 666146074 519021860 283423417 647096201 883735209 439819237 635314937 228227812 79398644 588903684 845681516 332021741 476992250 753515221 424932275 200136940 999838145 966281602 251883363 736641937 398177 679351837 907967060 115054567 918921217 557969914 716478360 214943932 489597923 257410559 559218528 503955408 566993495 273662756 443711083 459960391 89133545 422607657 199936665 574304291 241748147 795896505 517389949 986204961 886737575 613352043 496140436 599724508 318533015 372786177 545452210 307189113 379384779 264760651 66084020 136187138 521182738 399361262 795046327 756294473 425852724 81152701 757375733 108565030 510138233 921623592 401429251 512474721 475034288 521639897 23731129 152122442 967038301 445617765 540604178 104470379 436301381 266952073 304788883 271894648 907820099 629809183 580972509 124170829 192705069 245941201 294178712 129485922 406895406 823867680 15904394 593425127 449560035 390838791 454293775 683355035 737251299 787185889 733188551 39265658 320390782 480807580 838508183 463536501 68478047 758757217 981038937 857688035 496584178 45387734 520920174 309079723 561876070 756884804 616614528 173205557 720677917 832445902 931171930 832711839 677495786 774799761 855884496 12452151 830998655 897744516 407621055 296007850 47217843 707907239 458045604 236974182 55786168 663233880 174197546 405692749 290153213 926103515 696810346 987795251 789820448 478200693 490708352 225635663 938417350 554865439 461659088 41861215 286893232 127779859 274461661 362574923 89172182 811866708 73199855 28410125 933829869 270526598 48755071 505465926 798799736 253144727 489190139 133433127 149233358 245785448 566080501 654547788 780188708 103077760 183150637 14961239 869710097 322345744 659783667 349308045 729740575 446183938 158088837 822432370 327496592 19897594 761769933 533563761 988542715 867438269 362223404 95281652 134579069 818122500 919812910 367037586 321844967 488651589 860528538 902736508 357077291 62203546 41489055 542336749 894033682 224982770 594158445 635404804 627857955 443830459 584541279 877453584 829320843 837281860 257702383 439287748 964329676 648562364 77021475 279668699 182311151 804960465 825696610 13129901 617112321 262337538 782019179 750239952 992453268 66511744 807544963 90172259 147192662 164006944 952082408 272627662 51365964 46688293 257604296 518555661 851272871 303915744 904522026 328321993 822949211 852090376 166707402 147839679 176838756 291291436 445314904 756921235 17466043 710289604 811105298 135026029 181540401 258627501 236073614 929526847 675703008 50001498 748338026 363698433 901188910 255834813 156074011 377660301 872875929 743978712 521782437 951504071 296691045 146663991 14136538 566636167 836735219 389466367 410138138 284050719 902668673 5025914 480437780 651605198 866644097 5569344 536680242 88769572 170017765 825466949 931942767 198511088 48950833 436037697 565379601 294386846 853641689 275407531 524306614 662284609 511615473 306432325 840277327 297782505 546338691 569528363 11040601 150652853 879070725 702636575 716964787 143809199 930294406 574326551 358698013 214915939 918508403 611415084 863175659 959426822 818935583 186804890 551143136 545518749 175637730 163860146 3818697 800227403 994121423 228271870 116891820 141069874 88043784 932882677 406410503 19643277 247926120 269928508 652406006 486230310 603931743 487393224 618940886 844411325 556974859 917035627 114559357 37159504 864945663 457430840 336285008 888253787 394122334 454715725 127524185 37011807 315638657 580786669 750236897 688378017 667951016 225622979 59018986 237767839 814895483 687253652 246557929 107347173 598353775 217618916 87039808 365857203 717111111 670021313 272332091 707403786 644279121 194327279 350674785 547207473 920618427 148256013 45636839 366630190 754482527 190424318 26097143 819972101 741154723 925664359 867813330 262664313 702123470 201822307 238105238 502433468 63108840 580258304 930872083 29163220 810535109 758131309 386038476 326627875 559779543 757337426 829628270 890537845 395890613 814987777 826051443 48562088 931329895 971070676 440693408 684654866 963960196 936619211 192712134 40510003 77702698 593628725 676176266 610565862 720349820 492750729 551136085 433846979 691643260 183154901 599887071 852847936 598296552 894748883 984040313 8770577 108301914 417720951 70008399 874795413 337442746 568957876 491210447 728752757 49081542 551470988 742314108 208155763 575914765 176191099 200881195 391702374 483489276 78890276 881636199 460523565 198653739 602175660 893123953 286686128 35927479 411776467 653914650 409199351 31406295 217211467 748011031 561829508 737614581 153622783 296805094 689620276 717109454 46113770 457433498 368777564 841752068 472067254 929057289 484415919 228051436 736500388 209553081 872205447 901037510 363725028 737044411 699020726 995298701 105444283 208085809 897829169 708074684 168313565 911633685 509155607 388274867 516096581 554771462 386764406 574934748 693249954 991905498 794611160 959874399 546282024 135958817 418549426 119038671 593404519 856682278 285022203 485001686 17916682 889988081 136328410 259130934 489941102 533820279 398601436 39762661 285627550 94056192 760833580 695039895 316268249 549688132 362376975 96610879 812972564 817585111 68502824 665551640 411601831 776879252 665835264 549193500 83729961 742667823 198907087 79927907 607009611 808456194 609483130 295601229 141207194 917531647 350385529 254389766 94205627 740962970 83127706 940093433 102295842 152883244 547287637 488210360 49123453 486115101 61744821 276230552 419224233 474267900 801820580 561478984 167081274 651774992 443553482 742092510 684671334 607027218 795506279 115090787 488579268 481697294 406702445 887278097 210991301 775621203 24593256 390525376 378144765 433586831 126450468 750065554 178159380 433880806 352625573 564223910 748919884 581795876 907089994 777398044 822947007 9166135 121158245 58089096 851030359 515652041 739780431 782939270 396144981 802801542 161045898 969469848 358959022 660536890 961017475 902503511 735633868 38117883 775384461 853253749 707424569 591474191 593514453 812134442 111410880 931823175 497362175 467279805 370078452 115015096 689295333 634422223 132949168 451205818 90123569 973500774 150363306 216517925 311055110 156723668 519727610 605141948 236023100 361961575 796847682 276752974 950712335 346049570 794431556 785590091 97353390 124348027 590175125 133910744 371864088 848215243 673017749 34867717 703791600 435553534 243296848 321910405 395109576 947513549 784453128 17146705 501922243 243635241 886939762 90550708 248298457 219956533 997929127 97258846 874872605 489509398 159417073 321051901 131158851 391199325 429413159 964292385 203019466 546648479 266811835 817581119 376414120 497185516 639786157 443265388 104981164 107392214 137248732 623771312 249477925 746361704 250294615 62894158 862039949 507549292 468557600 260077072 972828225 930953769 22695679 751412346 367479388 538014371 627079755 276160597 572857664 363032267 165855442 702957413 210153843 201964790 988435005 663304902 962720704 294672386 482882086 136099768 385819929 355894681 682664876 217046740 261120410 852251808 246502925 456220204 843780183 673626988 102931536 657050968 804812765 194978742 158979802 928493073 520055339 629491593 655796952 639036062 843186316 213965988 645361858 590655340 905976255 734390465 902150272 176802743 297604290 815824997 919300473 631449722 144990625 783004836 695010789 840774157 899656367 397853573 809484489 950785280 139688611 864226624 951888672 99111664 382128759 631307595 227865688 458447310 932753169 589015838 176708483 32519919 919889814 975485923 361971277 521251343 186867310 480312454 806873416 255543695 108005304 458011168 183782392 252774685 344657038 884415586 967292573 371511453 44997149 769440914 791363527 551363525 97653028 602645023 753508955 218255794 175041127 949526709 637676291 984413806 748300748 292546456 957743609 116546136 868489576 336443403 172118530 120340682 25251723 936307246 826985908 384313051 793285152 451182694 870989774 82994620 740132804 772306456 151197798 527826299 415372366 351464339 794518782 680409035 101218513 474296660 302086527 737332906 934469861 219653639 557790288 916934229 891931786 999477682 786439143 190479004 381892228 838252774 966932321 924479295 766920848 911083346 703755004 467279829 539721673 443822222 945365420 367675108 777707911 687281383 131504741 561698749 612601698 428065302 721718619 154848399 142404587 765637560 38699229 804026469 723470956 982112627 582843916 686448898 419696243 569636797 341361272 56097894 2469145 293013701 759090456 260486139 663739473 786427447 640167373 650317510 347602344 57522586 44616526 62099870 578273973 767842585 729674511 84774211 85825409 760539565 816627963 836866981 402532215 120050042 744102425 53323160 271565086 727847695 402901129 313939454 894663247 362597908 568245331 294785969 509982585 437078337 338530610 780537054 447455766 588938224 720967661 367568576 298909890 870123873 515515822 8449324 633412716 399617721 792706284 436258380 113848141 782635526 399333236 807148498 463442365 318573925 161252203 631781315 470176306 184297708 303956049 199103069 220808771 223638313 239182834 924873371 864474735 949402574 928640407 342948657 88999488 361237370 20514907 110156623 589549894 203211784 764566690 528144526 744821084 45252691 248833273 21415240 228495546 802596180 460871818 658585361 240939385 98998943 933368874 60345401 450964144 713950845 59202574 726431295 723406321 687212714 483048870 332958856 173688356 786602584 444037278 511375608 617961593 925633690 460849032 54400998 589677324 409084924 683624430 715517567 55636883 798932853 92625457 142962849 538718988 287798462 979884021 354741317 74782673 604101277 73308249 140128847 133153074 489402751 980847782 79962953 75539274 520688138 252930867 778205910 24753627 936004966 369022199 907508628 325963678 92564248 475934456 48095193 188038475 577727491 967799700 148987668 124158385 622767962 925505494 935210127 354612316 345427721 342518459 363361611 445349336 945607533 172784069 495477676 634484978 510430436 95662350 870607835 459472062 542729277 181772147 82580559 576426531 512952113 658101452 249063006 217217506 994841538 877645154 352655815 80350497 960392852 610286862 179681820 746370260 610075668 398783059 148943028 635458624 245248056 896836986 358916584 86968008 299616387 419933170 978572827 476972554 215331542 663504846 90754340 657498069 593933099 47347171 959447253 101485040 638062812 819092763 360148397 152276677 994200870 719872451 261021669 919851209 321801172 226770172 493808279 380862330 651334935 661799460 182882360 371914437 299124693 895252271 700333389 229228585 996437091 834677757 633441764 322413078 443409801 185216844 216890228 185703930 888435194 316859890 154143866 609383001 697818375 828280739 529006695 393220488 756935704 181186655 822485914 999576547 27553817 691578249 3311245 801666973 461200860 862441674 314467131 653022533 352832190 864906094 72329999 48550956 753951236 822292137 720585807 735492826 636853312 747822282 187612530 794067065 781962643 224038422 619091636 320871391 388309244 115637690 292896031 607343546 947758263 583645074 277880878 357785964 527841851 212388894 631812257 441821883 233729412 856432171 254141238 255924372 626533939 253839240 302560035 469654206 502258027 873739509 708512510 957552833 743970539 957912459 104235614 619460855 30954780 870209183 218305951 116127351 453501118 262300745 574135132 638922850 907270796 245082078 226691391 88575601 90269354 436673326 407578070 960184477 985756250 88157514 386436889 28865261 695672552 729672322 760367680 834453755 420401592 621234219 968610771 366391321 634229296 677988283 518763768 220178570 147662705 553053970 71460197 959631205 390127782 928116672 366512856 759444333 632778068 44888531 445202759 644501584 133528294 823397208 606993579 724062576 504164483 797437230 415706696 564750137 568515070 803437872 81056605 738672089 825860167 299154179 447107953 115341944 706937186 976033780 912046447 21498155 962308744 742170217 709536176 560446085 796664956 285367101 751494084 232045858 663127849 857627820 93137357 238214484 117983717 538051400 520675737 690273656 977366648 912344264 339930512 947665447 250667843 218738981 23839734 146890935 153957568 72900376 351170425 912659541 909127410 773296563 65498389 562289899 364665249 500516110 659930201 144761526 86427853 336177356 877163948 804649398 654438397 517953432 603737420 200291191 155327130 528829203 583119383 298959855 245459190 191106728 141467809 710077352 80093363 299990420 579677305 760449047 625806011 996267156 857329768 390822289 618570929 558170882 190521581 319393178 122541823 735485808 241415831 853130092 893304739 288746501 351878681 382344618 676476868 653152002 241700912 719276026 853503048 911793874 780183657 80776403 563379612 10889442 725585893 538956702 448508505 405736110 647205262 288045921 114465789 802243628 445789109 796139969 837157891 940117857 160033572 495579323 618507272 157046952 585682756 509144799 987229097 375565862 630743314 202931508 844937769 706166878 647185597 32953283 7948422 450388236 797983961 502407963 688757114 811933523 175850512 741835606 383283855 740703175 23029637 904895003 962300598 554896019 427102373 164569272 101178029 581826618 750471328 438223991 707954227 216490080 209275338 616911982 159948967 648729738 374046810 555383140 195591842 34057673 777164086 190894041 338252121 502785592 766209572 440984657 38237530 39723391 366121234 828009368 360307709 540870161 274483076 7643770 961198053 777401455 222739650 927796342 425123575 637778713 414628049 135208847 948714477 657628786 731949895 843744269 77854666 235510743 690318816 443757709 217939551 845698624 410601656 80813333 735527181 604050110 269704816 769974489 714769313 272916243 901926562 387737795 393613133 412986575 400850991 608731593 995462340 830758736 240176949 330642478 983754072 820795761 402051873 561810099 299775101 228684518 132779108 549369852 743907893 630591526 483581947 943645107 518719072 240301234 103255566 591593254 24482941 516855761 89534349 208826365 167806139 735593528 36600079 865350683 620620964 241160254 392683762 868052525 975038640 923973634 791105480 53001950 459637977 201240895 392751151 915519616 985469326 369335295 346012761 99115670 477985686 861471341 388217620 850732992 550420828 632488733 209574579 426606453 350850298 503289467 234162898 553355675 421020590 91693857 380689043 596684551 200322968 111643450 853117631 139947212 886105327 652040516 340384771 415613014 920433280 535473241 387925768 174253794 619022705 560838248 491477447 965419874 885589484 823729273 401212874 152266020 840516808 286829254 754532467 118257662 799156910 835845994 331799705 223476860 134108053 137116282 31783288 403349133 98289990 611810930 408354300 77134897 314746029 707852878 927679943 93985016 206576621 21006731 732364507 900964947 636601320 852115463 777505021 976390058 390808071 210287351 475475055 953817385 990159693 200923465 776036925 698502900 765572474 579272465 213812202 904472765 344923435 326444295 6491441 85943580 598793503 792446154 512984904 631091931 647796579 708610636 143888924 269560851 835763995 427029442 911546671 452819068 154848220 538020727 43464669 615437852 653694485 307519974 158246367 82163863 406240063 130215463 679103481 939035752 347610080 30159850 473986431 604091764 261937248 804697537 262392659 101505314 914714904 505661382 828617178 331740917 6659348 52290228 213735462 526633377 489575893 386858888 709792844 787095928 6887922 366208811 259770328 687145625 481330663 953059148 405833153 297857659 543221484 399598506 489480360 330965336 119022750 276209685 383970977 576576458 265934899 748011817 109067804 29630233 688093215 535589426 302599067 195718822 716453516 363221344 104970400 425630865 291434679 727003128 584364092 920813415 431599239 265974613 200663235 287100171 69400500 195319230 723582107 685074371 73356674 692711972 98989051 101721132 757640121 780395316 530049640 803858954 427622925 997948010 825083092 375074737 127057521 135841122 795950248 808421455 750527544 388090620 170405148 464865836 667767266 408333712 884275631 697345254 33808393 637167048 848257807 497794871 742049200 458544693 521809395 941397440 147120944 110716807 604875526 577906381 696661009 632918519 889049652 71451914 54679499 320273434 937451848 561994422 884284728 241625002 138040699 909834612 895290569 363541500 76084951 320215885 702191884 734275549 257577097 892916184 555630973 894132024 911450507 45016844 809288978 520033883 580814658 681927791 923882352 20711385 328882538 703175003 732749566 828713234 666889234 226926728 43041437 49164358 945864487 56249057 222232099 950643940 518723240 501602604 63093999 790131460 696485203 535380998 87466817 511264741 421202980 223935523 206143907 909959895 196890443 786517532 596372388 558213944 654192893 400953341 641972417 60564274 436650744 538853617 510103285 153433747 223011913 750149835 134380961 923559767 117459468 360393426 955862772 984867527 319670182 909215007 578911866 989404545 711319050 284414651 463330311 840828905 111993944 627163170 703007571 91710890 121198789 253149135 928903632 174643077 359568862 967168017 588618333 153961204 252763175 629256337 609555906 207360405 375170650 387862026 955743544 260136541 31080334 678924379 897745561 824579105 49830063 294674187 536255537 645560394 196306773 56286472 531134902 498747423 847719144 683511513 172958780 663120768 508741569 803528254 225692289 797381431 291459757 633620038 975915276 660955790 916796597 941628429 166722147 341756942 467017267 614618717 572882828 830034958 45665257 916927307 192192892 594952662 413966446 400245256 513997579 709971181 56740327 154813551 70149807 727668782 207316192 462653535 949395649 848672831 6599138 64113579 594104347 759843848 837663174 725862778 929573779 101599855 237472788 257146056 601893675 216620612 940089707 129030107 12448635 275666262 417613496 608765170 330522431 556517238 978623526 948746836 492377509 384939865 74001742 283927058 427094295 526330324 656252815 652343231 450283915 429634128 679388554 585855004 326149804 487872766 930121955 536790272 580298618 344595395 605803805 896220003 999485941 634163098 287888717 441349265 475049477 765660645 840227251 748678785 75392174 879307073 213146665 211381478 391170475 958273719 355733891 981628001 13106518 539684524 943306171 178708617 605166679 534699530 626392702 588463918 607821147 705157099 183390511 724014915 494742118 144352943 755499833 264370604 457117905 830725167 362846993 603164927 116238236 657650661 273912366 140368574 740753995 389913945 21443083 626163735 222776844 417976282 269701142 222542457 422612135 983111746 861764543 914562518 988029201 744291125 371339973 60404348 523535503 530332777 141567936 574977977 953451010 688073436 387793545 500695315 840046342 425566610 134969031 822668261 565924450 154219612 681746318 752234194 670738715 82480152 466888356 632542568 687816103 819847575 432210599 390066441 361380525 167009975 313116994 446666246 351378852 747964169 808969943 835378171 166618210 279246999 412944234 293840405 878944065 11224690 818528109 138700439 943053671 36711531 426596033 767603515 935368301 414020750 179833602 954414864 918999416 623471303 665550110 975431890 34219789 411262447 253104203 933505424 660312261 693674957 46061527 446531661 455602418 365468411 70370701 706953486 266068612 323141502 841898004 797816374 656906925 31763252 991071845 897516047 37264532 741835597 327794731 848378823 501267082 134651776 440326601 633110508 256901047 229744736 284092343 179911693 552423209 483164871 199877873 224202207 390367592 984679013 922667186 426314644 476528395 521679041 621973099 133069008 283039033 731179659 906890995 580954669 959476592 875258450 264020858 101797774 507516567 502418780 45529290 546840112 292304170 777672483 180837074 919168690 459843871 579750045 497336153 759407220 339964832 797915541 163435919 931011748 500876793 186234215 88788738 983324328 594389806 561010268 705915632 293882774 357009674 773203266 622100225 626021515 902449802 82836110 867748595 172131367 858398273 875771365 615754485 86841638 549373384 821689514 874293555 412297172 97506717 974707074 569717418 991142726 923279259 533489210 170612336 838146969 220329637 836153037 998968689 68220379 102469556 405501120 268588491 661687557 370792025 919301695 849770305 870343060 256071602 518084960 279553507 872479244 388706742 735181803 453734290 472554585 331198335 435883127 303450157 459979579 745991648 19528517 839816578 187470689 688691710 796895594 2907930 147498852 86995257 764446560 882181408 315881858 568653406 780180717 847651934 326395167 867521273 745381126 380379555 489041918 673684320 750863345 637569156 350680308 60756799 716733887 598314453 938257091 678978208 64755758 729764114 170092553 340831742 473858204 954657059 854637472 601923215 635540380 204497804 46824297 822369779 365487011 548358090 881404567 95890063 880625467 597643910 187525251 925501881 761399370 241118442 98817942 739384569 367682373 358617500 759994819 45479452 518252643 299861136 904067994 218026458 268066715 842435231 53014121 80171339 638060205 472784938 502382572 733220023 632585944 218398772 711091117 982891479 693808419 773956679 595381490 751202704 965700892 437122104 750062514 805073518 736468717 488245572 307163376 893595273 651405236 557320311 411359668 272776410 645448274 148123040 419025948 260462254 701859196 5709207 337796532 84481034 720235367 231846875 539308533 401242295 225963459 134900142 980534290 628930461 237576519 912976140 246406401 566549677 784794431 860704562 779702674 811154876 838031497 585870060 728720868 233892904 573786043 487792358 74275998 556645272 121067623 619905045 704884547 877325984 325785684 917502911 801587214 457414739 343108679 105363125 83207209 132275850 733873842 556475038 777102259 415385680 149492064 385859023 656828183 198456782 726990436 873082884 29395267 465203333 284070356 524131299 526939870 235912333 89553625 254532499 287076423 945689197 115249828 833162986 548124803 823489739 861641179 607947937 54685466 309916428 169855261 958522369 373662145 660848284 668974831 171216022 93473351 794198737 634757924 124131715 6505966 636062709 778976179 933565773 554840374 481264306 829846731 850071704 115085959 391972193 612862899 66527132 899735680 486174711 669366234 388730204 229320631 362769967 151240969 882496444 938827618 535101210 188375410 822142364 413988699 623968822 260644 497153703 626010574 194094043 344270234 317302006 601210122 562855624 968985377 397956831 524643645 64470805 18606319 881170085 506183315 859425457 730131810 495583935 679786307 593674503 408090771 512222583 411713683 879844111 260551669 722837626 507421249 556016456 851766355 208593931 886572822 987664424 273516030 591277593 168322914 673089082 216369349 680614202 967090986 972230168 175819135 941997533 412219118 806681518 398420420 66982047 778491069 312811200 57193151 138393136 722816740 369196686 172060472 104382405 75693200 372663272 802719631 900006990 292671694 508414766 923300557 160067220 575202985 463002659 985790207 63494258 169302865 106317473 917187028 197005724 882682220 739375556 727989271 246712315 913320817 767192049 974904375 899785944 861733099 291323867 535347604 444941344 800516410 80388235 315814253 464090870 742446881 876617023 312857820 995107633 346473616 754900740 853696534 237776693 466561826 89988826 182023068 139542401 685051994 94873827 334652709 31363284 423901905 957299439 133157468 504082876 915062140 195322573 606478116 196104472 219979779 727313258 783881619 54803358 221574796 352686871 4848788 120710705 260246950 477008284 26004849 958337659 418641020 117463393 113339570 722541203 70923835 790995106 192568068 720961553 631261963 870326929 695359114 337765254 792164085 615377630 12724690 448440177 965116889 597254175 301866865 425913084 236014 959940755 557743491 58730669 810991680 784270632 838361707 896536378 629837267 457988637 577737953 467317140 212599326 572370561 660250934 622052783 190735957 266751026 461422703 364470633 755323250 47644617 208217961 600090549 282594463 259439559 613745474 300967197 759173882 56002272 188290193 132765067 110710678 106645642 227994374 798086567 586408154 126294571 689170419 720015339 146311755 975568682 27705625 810386672 977719524 761038559 593521534 430977552 425956565 32160973 895460177 256949394 663096081 622724689 655473891 168493214 612741126 488025423 690064993 244630312 402700769 549058889 893881609 437530329 84562992 397787858 236019813 135134244 823651064 409371174 818660958 74099499 788895287 252301860 697630483 445872820 644645814 764043213 881066242 566471935 688763441 171688830 969519645 174989015 277304912 333005026 925167373 823447607 835144981 655940756 645164651 968157505 818104158 343093457 669157993 882764418 759313603 728492416 163539160 419793014 760812208 363302862 488297000 440368438 595922766 501101740 246681958 433562579 235702498 300634224 652482053 973799435 234932255 371162894 314320805 6863998 426777278 480443082 424236194 390247421 691493257 119893061 520204736 201052827 461897441 498107758 805961808 412027048 245112120 394993814 158884716 486215863 378341221 113061201 735150822 541000042 326073570 868134239 89698770 617468465 947891760 816478193 737019743 217293334 895374866 197176711 865442890 670229979 878002834 842178808 912987313 563487624 634369554 611371875 788922857 908758132 526625483 28015243 27714980 510148926 243485796 591099810 694513436 542981907 778681107 196366103 701537249 676258882 128216408 707093841 692801423 174189016 552823268 81485166 994587219 832632890 543427315 207288381 39689637 137835025 188902012 140088421 40001432 548493374 268114393 745785381 556888436 567189306 668891141 144245324 606144388 67857835 568628312 853637808 517923224 282590765 373766410 786388605 899428953 647080763 85633945 308344057 706999376 478694615 360423157 822001019 453497974 930855854 64595306 253592598 60991005 804794886 766240215 281822950 849164050 231837963 93771643 525739869 118344129 264822963 637610319 869247332 985475062 19862863 482990879 197159239 797401959 591551940 611173723 575680839 133733074 229792097 915981605 775336297 339813171 113660266 502364768 539789139 242855234 603352957 630976262 341331711 160408580 694829291 769920061 109926967 43731398 964113898 569117280 169130985 99803176 285855721 736404048 892896143 164968819 911557382 949555393 747607539 14763132 194189925 182399137 365134513 44594645 651464795 145916740 718457984 7369543 661150995 764874686 508138157 401998825 599895138 883112196 847176047 839429730 641073926 423439417 22236694 259366930 138210370 629840980 510409314 120067014 474650711 508688692 932441156 45694459 860383317 29780545 443117735 170344746 888879146 145771695 973310024 300130952 878070446 339300762 173988804 393805481 717641542 748872840 160490926 113456045 595800845 274554958 853894437 61769348 400263344 492251989 692621421 699107227 711520758 201908269 627526669 76946083 12376339 913605465 736231147 373354024 150835410 197242009 310004170 328337467 437001536 451742845 477654658 871433874 602824927 552114828 655823408 791803125 4196781 365197617 94871843 483467706 849620677 108230409 56909023 684059695 348765846 410751847 869381020 977967561 751240817 160091212 49982866 162236858 604834221 558797440 811115818 20181838 423126020 453321114 400962045 86061613 57853521 698072226 904565446 171096789 341762732 207943594 712945883 645832152 345937529 390001220 750173083 965234602 764747630 192371811 675475212 909802357 611267164 718048278 464118554 125793510 175422993 6023194 689540149 182974226 570676500 675917502 657375286 946240633 75215327 6309756 701680020 291801231 198417204 779810184 604248860 337964110 581611747 825658845 158518747 240929759 693432566 391550192 778835385 986095574 774046652 379811458 277212852 975090877 220905038 357669217 730573793 307729656 795855763 191065992 10696995 10136912 89411737 627418650 644202325 652765429 300904329 45758377 306858253 690403164 633865736 286699725 143208630 193973331 926165105 350005476 908391506 333184804 344567418 80430213 210905938 863149593 697144670 572836310 945107023 338486642 852844100 838001573 225988972 557356031 895308752 521102468 347807419 232437937 282907014 376360948 983396168 152042302 459825553 917216760 572762860 803252223 602199978 897266323 572509834 640856312 5881799 845961727 956983671 769455758 807396781 783448295 336964291 708892686 115384351 343977849 168483628 266855315 985852173 251651617 770921793 398564136 65104963 870382330 167518306 582551848 267353647 756300861 446821698 558715561 348751392 711011007 461225613 496240744 868176964 837910396 77245178 327181299 66164976 740207073 229861598 770988439 734229510 655691331 930710960 681533536 586767429 781244018 542310076 316750372 901557960 369968117 96557109 813645852 910582471 768784671 767905607 473176805 386703454 831682193 751386898 78907296 830249064 988147981 406007789 823392110 750129738 776634552 909764860 570681109 188333493 324102216 145258075 200129665 264717761 969079063 133162688 556905576 177839287 497307032 385064654 22615034 209315524 905847424 988875375 326752941 660764208 608892455 944952044 447122617 676923518 407489637 153131411 718763990 966711159 672773227 959158111 935968297 630338518 489529764 347038065 106849048 468966854 783394545 935346207 279904007 133971738 636812424 951167741 923129067 588127512 690080641 215589869 592011177 389972517 325745058 861351476 177192307 366585782 716211501 66591515 390072592 54895649 426944629 85086232 454915382 191508603 737357084 818703850 527446109 177323696 881174937 642967149 244691304 545738948 932137833 377640968 993414932 331462382 813983686 572427318 335422201 404455262 763904924 134213373 194878730 373811367 455769284 832145386 152961953 591938669 193933347 119102172 105933448 60825462 405505285 322919793 437875171 470608654 495340845 482756630 676212659 7256055 867892445 554990615 257038061 987465968 263375868 131237930 277033219 703598816 528649196 134655627 356743611 458093726 989738849 609347418 779855956 583836346 125337163 86303073 500336507 538071035 331897536 252582265 615867538 204914134 634899102 799443769 761212491 357183453 676062256 212909420 843424812 509380480 949448934 446343306 746412420 284374562 493659550 295477758 111895687 978932719 770585008 491916529 708850414 42854290 375171714 799356855 390608134 738912732 549433581 435400424 646320703 535647204 133772743 879498204 364724111 92733743 97927066 551419354 465330495 286324124 980128332 792846458 750137806 623354584 535926297 670631721 145638638 172636422 592122227 845130709 595817488 689704410 330239234 692355632 789728115 11793635 126136089 893191769 376621156 819670641 639054047 31450123 586847126 853323622 667288213 819638958 400832386 678372913 960351213 706754475 112203252 304186685 922654436 202115226 533773109 123440281 741193317 988176610 934803771 488470910 361507279 553822288 60584110 931676023 271183072 200825165 875678851 98683705 699173847 577398547 565771684 751512382 520433297 243495259 718360977 646541860 534423217 268001860 771287847 222328734 931522830 69732547 509585419 561727546 430740665 519562763 222186784 192955605 900352422 250701685 486369765 608563666 763477003 353561767 732570375 866973475 683433585 157419722 964565400 30855750 268498149 698902529 758716066 957032297 112780245 347378350 196729346 917797006 615764661 435635933 495803223 627760701 42079623 969269530 341083598 136679777 255681498 59365579 148511671 716564338 62740936 200717801 705934705 511102303 337298863 905542347 227680269 677491199 582690375 839239990 838356716 645198477 819294089 329841780 233979934 116619960 30421746 230158505 674922521 799522026 382933129 377781782 938660204 170630524 366161010 131256838 623885874 909111981 702553601 572136274 649043703 87736251 171929544 758350869 916979295 212996964 793485776 729295077 726447507 812832809 699800542 645475819 773536693 822279429 378923086 773536278 782573287 401763776 685836590 303449181 116693555 620416525 726779304 244007507 816153057 10664894 636414999 283624636 355865291 92206387 517382046 856123702 661861127 680318706 320068858 332522728 672089126 588486129 752146927 632706822 307772676 359507362 927200193 236903430 872086433 999865594 348314065 950538122 412502537 375509674 763462820 247061650 537096947 320255744 567956022 47280045 145111283 274863289 483629354 291446070 742430378 152922753 557225646 58366645 594207679 660431028 153375766 201110956 735335265 981481388 280653389 609313064 568028073 411057415 686646721 553531025 178905748 328361234 429590756 810657348 201122125 3591040 187281260 577786837 425056037 856450220 96396379 927660795 371234296 662060753 361222866 692642436 894680588 729652030 290234901 146917775 155163497 572667399 531256178 836511730 561300707 716430744 824232423 83305593 903976064 568906147 146697091 51539890 45041368 202775156 127782900 871360398 700554342 759355580 624714512 63181345 989440685 536248145 438851704 765448561 740588033 894459916 308731495 53344841 632589002 496974985 984282351 724984996 500330420 937376711 164958662 965788839 603256226 776033717 90255854 824408004 806702166 751667315 500963592 696004475 244100756 516661589 990478966 358081706 216246426 648803237 991182125 78049884 960978363 845589725 164920174 452693678 647848174 788146362 447318400 43131245 922691638 1019594 750772587 690270998 283148553 901799567 150722731 565507686 52913345 44423266 842454381 934444424 452593128 188925453 557576356 999968221 72530367 359396416 930912991 795067695 385627201 497463259 47114675 270369879 280089102 566670169 114746892 947407434 479857169 460346806 816344015 390256859 246281793 635015350 251208741 724260597 960258289 128733718 661066972 92439192 482035044 361216032 569656646 360990981 371923995 271672830 968853663 374384381 969742888 619215194 375743612 546553050 659717455 942573659 192198713 71637853 319301261 174373457 518761841 305773867 985203242 482114122 131980601 315444135 167318141 908433340 279170798 674074253 192802486 720089632 701984072 670216211 313684237 491561518 319967529 208077417 659753643 926138846 531247096 259810927 765403895 223212956 246232523 154707319 526374170 44496034 857823075 604716376 25692500 272056943 341584200 872492749 957076002 55823226 938080906 937558245 21682375 475197324 809465753 924643150 626993606 423976260 469400100 876075105 77476612 679031845 71488532 473206295 647389362 447373795 904780394 394169658 314167815 182888690 836779066 765284564 891486583 877395879 25376867 479276971 459593501 430267926 171217955 754978649 950090688 91506565 485084836 351871068 310291269 860509853 781277787 770866682 331467785 970610482 28553901 113352798 583794551 958164492 367308311 590766945 740265384 116627384 488382324 40202742 101370060 233480575 339197494 880299601 964760415 108385935 240376806 196011354 818410019 294666713 190485439 814527592 996111868 907060282 86229711 436318680 509522722 80661602 512558512 922758992 551843246 245681250 361127194 70668756 639887956 649299162 471643052 406782584 801160884 268886366 483684906 37218932 879003214 37780515 410828577 430201939 37800586 396064429 572375695 173531239 87721111 994238093 865291692 387209917 30818724 110495133 997886010 559376360 719203288 554230024 560577920 302193995 512328891 924589757 6162397 890849003 88429367 498699047 89720115 766361950 705798279 194458133 350513102 423320435 993277100 619969777 315633000 692151687 499225804 503499746 842717440 114054385 815549636 1129035 8982814 255833210 62384248 818061583 680275387 122275439 534341381 649360204 215805557 779408262 672178806 272231180 204018415 792774478 838615707 942232376 868393126 364769570 692640702 435968872 660236067 349938079 206783281 833401283 494443184 764925448 712328572 145459507 730232039 176694887 679017471 474331333 800545335 334191586 737016700 354803833 693162954 197551664 50754746 445965641 38787560 824040390 282072872 469430408 296129348 339719357 563404774 46510604 774554676 238609916 44457624 738229232 88668632 64620956 394808373 381741418 858836203 844345047 61752757 599846354 197875693 271564176 292524429 348266891 971296236 904584705 58284766 431801936 378304113 809411434 380385716 397552467 778522780 809129773 945947256 30604242 379073804 811214454 5572502 446790375 598987778 539925057 176238232 263420332 447064607 404496370 360166291 127602253 296485747 761073194 175159418 315765829 606050818 771585445 774936658 507416897 989115157 347823884 758353454 401787619 822561289 724791947 605098992 437673425 643047456 496737510 536504893 335906566 714188119 563099483 753437614 390150232 172385892 628372024 721620443 162470825 241896668 505679333 246812113 553732727 151524740 983449226 542978141 839670488 886376994 593054479 623268853 8347484 606672320 492422358 134868605 2078455 910738804 421733667 137318715 324636039 93047967 66604123 330441779 558760638 811105499 728416968 84387802 58074666 691296681 2334798 541120698 861083592 172411384 521756021 482892781 749699198 23292433 418107248 109618670 306464000 892113264 932988234 323425171 55109604 159528602 885104196 824761477 607699923 533233399 775462749 836759391 591578689 236321756 998556924 357208068 382255533 955971020 607326942 179711437 86238488 128520153 416401993 58356568 477864950 647235192 627825443 465125592 208261644 12414759 333168574 292094964 945211124 344062580 543479156 502181500 937328123 911175240 501949223 638724734 278588448 513999947 518587989 31988241 754415979 398730324 389165024 366560143 668149706 413082975 886464349 792778600 924312992 483629121 63183994 359912801 510666401 771220628 990742092 770728272 491922226 49927013 19781683 119989897 694997140 825526632 880909675 477141904 185681100 483983861 741533558 371969037 93254593 717024156 580196404 831330909 812615849 135356213 622589495 459618602 435034261 35318227 672418680 635761790 532559958 6341959 909922167 244212125 392118682 194921997 836943276 936379087 259234203 142062526 607376371 119638082 177446910 112952105 643001866 585629418 420811193 696773962 173142137 10371480 677647047 655083154 101225620 747780144 997944476 437398279 636621081 51300342 622407786 507024474 338084079 136808725 77037424 656540849 229854955 851406915 855339949 126986686 494176780 434241962 842114117 725900244 285470709 382651184 149025506 646955990 2010150 196616026 982496105 880719384 931950115 302706993 610436044 415004719 298340152 398818898 311006950 9426907 799041825 685451406 641166669 857944097 487602341 377945271 885255918 894338311 329605461 806713448 115662596 20507250 192897253 464813369 490492082 484306745 586702373 444102983 709058222 164562492 908491043 875253189 383329946 42288731 723286293 384704928 478502627 982333646 959935204 363555951 195130377 546682229 818574663 779598132 166819691 43840023 532534083 141570550 971276504 327777129 375640645 812062834 787436767 367646079 336026236 78917815 730160931 11536624 793176929 845157648 978469548 624841400 724286270 263238386 685434860 612907799 859759613 549871960 360560423 852865686 714805230 226445902 707893603 869034045 548522608 854357171 633059218 208967913 727974642 748745552 883002752 994415187 937976641 961829188 538924063 682172560 679573914 648918424 520285143 890895847 688882442 223454098 331566031 478088816 269595080 716938077 343488581 907945633 228278860 503173410 353754932 366119161 321014773 843777612 846637673 472263151 642461405 652009461 56688378 57810459 618460935 23814689 838148545 578879261 25870299 559494829 472860382 513165648 450061423 470516088 989948243 988775222 826087126 497265757 282353861 185622675 23849162 494627543 358078326 480873418 64951887 350986604 593890558 600116383 886831088 752058914 230487798 243438475 169592036 315230913 333955265 807343357 59689747 462582348 787202498 201455893 991576402 474999495 588613978 190318458 60143732 321849062 684993648 191878866 774515336 384710711 262503246 990222053 347717622 704799893 133801885 657065980 674167280 516264972 7133831 469741833 222419449 141648892 748336479 362589360 822077831 496785573 996181638 953037016 860494228 32857032 142861071 894413653 920710997 45195402 558482366 10693864 167574517 412090206 75134747 535518926 197638656 258245365 437083053 706090679 859917661 790089500 518816832 223213559 306391636 558301362 815335389 264042654 672110015 103944614 994593764 820985858 657753941 503344479 871350030 558833653 479699243 177342558 722584981 505503052 753326445 101076649 118923026 10660321 163915187 321335052 528801946 239777527 870490168 856168017 598843046 911837847 882447411 5583272 729068809 803015695 465223309 202433063 427464079 66046574 43317626 394158342 433727957 412260598 978065650 713053123 248027230 319650884 289481942 855353458 810475852 345186660 685629981 942388050 889126189 522444281 495077370 91932284 488328255 984790729 474180877 47402033 899425159 940874568 882435692 515995929 205265534 27922523 890062607 643520831 587202086 959076252 753921195 286826587 698961287 168627963 705556402 586340719 886217262 915574354 203698516 468299735 602360069 893280022 101325831 549668227 675991072 484493814 629907147 717158253 317684097 440652741 197110485 555790136 432844375 600725407 302500345 729971377 550018420 998318489 741498759 100019666 273914165 122095771 310327367 46169319 391326325 94177568 210964340 658246838 66218913 198764841 583112029 883587179 859897121 418708283 315832647 186833355 135185500 662751807 41523895 103275766 992969817 285321755 890675982 491546846 470955998 621877985 775920756 74679027 222530795 623869671 801951500 658295333 245839022 995718627 487470628 361545524 157544826 672068754 263040948 166823371 388325882 584438761 48704000 977036657 160479528 686370251 542948609 302134202 638487129 674287993 688838392 479078627 664735298 672833927 745276371 231483673 143999667 140055 445179498 722737494 539541281 817000646 977061276 628246662 280705821 145467363 778099111 233884832 490867584 853787219 799208594 860834636 361970613 778775036 907081911 973594529 82451084 239985184 221387310 166779698 155289573 101340703 37740756 182823953 405134442 706104021 765992515 272403821 186579641 221366328 469746108 26938847 864923121 574895236 376216052 411384902 323475038 539370298 6503674 664967539 577977663 369180676 399744116 784431158 407533358 49049271 944234916 481355402 245049034 433391045 505173659 425806110 766640149 454773884 591125262 165318585 548266275 79911704 625656547 466708944 202640247 58947339 694207088 838710804 819848083 584739006 213117858 907538230 498270575 863272388 363172133 814050305 384075303 851474189 154865776 691463818 680960840 606382625 192871836 75558066 546990265 808271502 241878263 136419776 136004906 401210611 270934943 735573130 414346699 840269601 160673236 666480077 984361740 779897545 991849576 917094672 414729714 177320222 424760383 591161723 621057853 247808263 824133372 537082649 868079077 645574246 763130705 266230381 879513906 431542880 454349882 370060466 831418382 935446509 633154931 570775342 186150669 752183161 117503968 103919389 975158100 632394324 907089994 80745082 182039978 808301299 497983959 765559841 585723971 457707385 97260781 63563986 866812667 519441282 152854420 184801860 593314544 134106042 507860841 491308518 21627939 358419353 132844020 835603890 752136824 894949454 143355491 817054087 808218579 962625498 167723880 118759051 785534921 660687595 675272267 186837343 177378427 526449967 595698294 584958769 139995388 492540375 427261164 46111816 87753559 464993655 838923604 476382539 647464653 740112239 935374392 769896114 588375722 109012129 587797958 745579552 513163049 92746632 391439835 728415388 752702 804183826 746947032 866113669 746856418 525317699 777625766 667115463 580611723 959575538 818456426 126359852 827792294 417674902 946090849 693257839 127925251 231776802 551981924 935225249 219021810 477064453 402444353 678557058 902734998 904930264 719144656 889970041 196004326 279265071 897595922 251856948 730356500 311565903 609173382 959799158 85351435 75620854 742773938 575502545 333508974 116810745 176438302 503000511 706667218 238552505 568923038 81823322 721054846 600051131 155317849 821640989 480413211 149687611 21291978 779480548 498416688 262483542 421243007 578262185 564125811 586010690 309699428 470168052 814553220 939011139 37826916 434964329 243100890 266634365 891403218 785524827 590688163 634300060 103792466 639743965 409245295 691185969 114469355 888137197 333891259 171307507 114039719 336049819 401401469 652128051 314198997 658934014 498973289 733450768 479347358 761794592 585196340 617323576 2862128 107371529 523498191 443223284 662058960 781445973 229557432 202466288 396302735 154195154 48331716 80291306 757236440 140248680 539739885 683035186 618183455 732098394 699201013 109173210 20567932 470933869 32828328 675929971 863229323 931046312 18148172 5129279 192653814 472960407 868712578 60169276 159812780 481224339 29671834 730465251 213031421 423342438 941659683 822016569 858747171 622905061 479816348 829523842 293097438 525336840 597712115 676861148 696899235 3358211 256620723 301960634 735173503 911972244 288963855 723093918 644854693 835613379 420679219 988702836 757967643 795576130 946547941 842641292 329816783 756963865 427178639 511322466 478609640 427383401 748712955 447603226 976575829 365471990 871416113 248701736 931861980 654652638 153116921 180046895 605559093 452119502 507405832 966462409 72265267 400155561 283473302 318730652 387248136 668948355 291068380 883738627 381016073 422527063 260607019 591727183 698611413 577011456 495617769 617383761 262783118 728170923 461539184 67154278 931078293 427713163 333541271 229319655 421955339 5764942 297248246 981351402 73186470 413051876 303994006 454074248 411149385 867957570 933750028 617634460 848117833 959066455 495399827 680134483 463931236 441983191 395353482 165876996 97571811 31662228 563425141 232988982 81986849 12610279 585298637 503879368 463034006 628802802 378756451 733815946 868604386 258682323 181280927 829365687 802389541 8311888 989766038 907582959 699636656 592990761 568049449 413894570 836957376 827237829 333395783 713469687 609212387 232914311 854605678 787468211 311775754 433015767 680165749 831871728 888862124 361414192 377977648 381190397 768102426 635723220 144431164 218659118 891677050 267586975 889013578 331776311 898654131 494146492 821759135 964958216 267574430 329184704 648649676 250519488 473543908 39009312 924100735 195314103 497429916 303710639 830433582 795926719 993453137 117768147 813662534 194911445 524974359 664502354 668232941 502105468 616136811 743504510 645366333 133707757 277276055 557951966 747293563 334486648 138068741 860296022 895153050 556624418 524092824 25523507 882627354 208399876 549511281 36142841 873669673 936346979 667396818 785818691 900124089 678713704 732053985 917807034 314534925 158989814 90296451 666786923 790045395 692078810 79409134 787909231 450744318 574600357 160233811 682912086 233298455 553666922 100400567 994823128 977685484 695583593 385814630 531476778 372528438 623870014 885297860 618460157 518609335 329235319 795180245 687364077 892724038 643318527 568571278 93814692 989170324 729140633 87412391 181686114 474487090 82500983 604222016 296267359 490663167 879223855 823323191 345167999 343254565 932177692 778677449 512295856 545672640 267529025 254782713 313809964 386034124 74598310 192370035 189039352 434609029 996789083 947132104 172479334 262294980 141159179 594500202 783695829 650809799 959369040 554773680 156952110 405783088 552940513 542432803 41499142 74200684 889835162 227444178 131470915 638086007 351999227 235235789 90555687 780400274 549648295 160181629 33524970 859989568 36110448 420890394 730102197 896456557 810230576 197223319 52813880 515277464 539810804 432811640 119722322 927480649 107618233 273085369 866270980 477809962 517890637 931667292 21094948 477616675 512575239 832240123 805830570 259987871 658939147 961244551 195258313 378490623 840663754 582139906 448592427 899777666 822898700 753884496 196681494 391350682 13703423 352745327 568465157 412978099 125132857 920337436 495112617 583917436 158219475 31982099 297788130 803890630 882192646 538372874 514159589 781777910 185184757 711360987 213804299 28800069 4114509 348092535 771875701 476654145 485565334 831936421 65407222 550843792 251882151 3476292 724594893 746327604 82353072 806425791 793026550 290582902 794217010 514351860 453626209 131039067 738156413 804357502 700675476 450314977 910694860 871463939 369075051 598965907 516564551 794502056 146653061 209147253 233413175 450171530 87008671 920597187 79051691 467742543 680048588 445435842 994889799 587481952 373057824 550066458 418959672 752732652 128294046 157869148 275735359 848499101 724869871 676276325 594079404 829509562 496069409 283287794 412635773 863683674 317584484 41217411 408520002 920214113 59273168 969240767 657496226 268674790 836553594 266369123 379086178 172665898 792903313 368490158 440266597 921607165 621305752 994865 974970298 657766721 281623455 112517517 332695955 718028293 519157658 353275446 694620143 526003116 110138634 540968578 364655266 58485652 304190313 391609652 548574610 807681650 799867263 903430711 626519095 940166720 836232493 809566563 727194096 510244485 103492289 702631486 967605149 125455513 306467794 670101111 867289115 921885620 700382699 381576108 538824493 417479622 939205416 532819406 841239542 747863770 483891803 486780547 109828668 816405154 653609670 498557324 271305163 253376305 936116460 346800029 739124310 811387507 189364886 740947711 718244293 804840202 884826443 309610110 448616024 356355837 987760399 265301079 300798156 727478200 399795062 499393620 777356443 765611199 372631843 163109430 390721451 224448106 744825886 652974182 907140131 867309253 86088189 265971345 883697500 35471275 967984104 176369657 140748578 852391089 207353222 664623834 757100846 85315606 356652248 514785764 48502760 565707190 828577448 634938188 81961138 587778768 745070801 957049705 756816448 273752710 415553120 728572222 659679459 686316630 846777206 29599293 455513158 757502574 792978751 448609070 295778436