7948 491091192 957052636 642822258 891970230 369313515 860210482 170848946 344804799 165495265 538319583 433049224 934245894 475805802 547314542 873788077 944139711 94953168 121142432 674884369 796978891 605019518 802917755 38908846 229541503 906191343 992854853 682220840 740268905 220443565 360714043 777858248 908988159 640576826 817845532 701308012 721378330 213698752 315599664 597747032 986605500 883897554 916557794 852241325 985079988 695384980 900182483 870547931 881621548 300059212 859969383 373485821 770731542 113733777 213161448 109532353 544368088 14093937 400278809 176182614 994945614 63955084 491861240 948688272 982783924 415829719 693061545 11747546 582574319 266862379 901743538 593558058 789520926 548367877 552959635 598999235 723243208 436788888 899374350 361204478 977167817 194989033 401320409 524127355 704456592 342598416 435838609 865854042 934153826 290738626 363912203 457247752 559419371 310364937 342974891 102072830 889527398 588227216 897817388 371222738 614056571 608057561 930356070 416115490 638358500 439378862 677198057 991850572 996210551 98039968 823584016 966923963 998774104 568692943 643422615 699814489 825256063 278580852 757536125 780060523 926916441 801571532 831457203 175412336 214754397 976057562 989955684 451712537 769338034 44234400 884192573 863915158 921074858 372275636 992567921 698638018 851133798 481482283 544292024 495543364 908720337 133151198 159072100 683735296 693883889 77746287 871862375 799427700 845404081 825214401 944174556 32574574 374897348 408825639 795175440 844457840 891688415 583555262 738264730 138407859 624763532 766249200 897185630 759537996 929431680 884053278 924647848 355727554 585194354 228705635 562033597 983474446 998370872 230532387 463838148 754084267 950663291 66692522 505594945 278076597 840937973 19343407 167787549 393601269 636733018 917895993 944946532 886640255 958479688 470559896 694431992 551439091 601251888 858608272 903679528 757988276 857563408 234630949 816828838 719425758 953507075 277569166 714461506 507244478 923355907 686702810 691103137 149776898 260737429 302748163 462494234 361280992 659453170 36510716 820960858 446485203 898667342 151686378 901474527 127566778 282254173 616216993 705695233 355284674 901203651 726442033 811725125 165223039 444701305 789786736 824111203 149403509 529168307 325547622 669275527 644601807 726994805 255237751 961734919 515951019 641357339 63541854 940985360 18975576 143205204 892228630 939982605 718754036 865866530 248099545 753504738 538434766 642726792 653045138 809718040 389675389 486871770 1 691930165 460806433 754247509 17187139 618852053 240652344 399651238 397210248 672167661 583673545 971238757 276647572 718701562 649457069 657626857 178149948 368973238 613873885 742521411 636627428 973888762 600732160 858526069 903054626 984444291 711570901 952518248 7679327 762863803 882102183 932911077 364284038 954521711 504477019 916949252 173796283 307908419 7924075 848660459 697175934 698817757 880731668 933652762 360977398 525532678 115401170 903374461 795909782 946178740 464755861 471260681 516850254 739061831 293056671 558445992 829820406 988179663 681037153 819087599 402005570 597206918 941242059 994874967 183147278 529333678 504798252 555154806 589342996 639192591 719781655 734607290 538382333 557694428 822566934 823018987 237923290 593481478 585697007 844792068 923141385 973512139 482346555 712941551 285035666 396940758 70529367 76888377 165300007 831245737 447808088 937803155 82628354 834972833 196986599 448162441 965334835 970294431 250689690 935761566 585204170 724018132 772396407 806371827 591446262 793648894 933656149 993572772 250217798 936046364 262074037 826289994 858392237 934779703 5139842 119551077 246501574 984919783 433253238 825303126 958869602 974332700 440218938 967853686 298281914 797755382 209386071 922125672 683415738 888485813 105334082 920904222 740228667 975994718 286890336 442305598 40651621 164546249 927174193 930977077 971914900 984110348 491956327 740687484 598962077 893751635 102707418 407395195 444900014 929557644 414392718 824726309 797565191 821016766 505726167 967151756 199151422 213847582 832608593 969922892 730743174 980699871 94248819 556382122 628516700 773634294 418410669 540897959 190782741 374508960 896341804 963026458 353649467 793666363 880504301 904122643 105196300 266127488 37067049 837104038 354627308 563391537 72940601 119295441 216723864 801756549 720890470 881676654 699852041 700411509 547482803 832242227 889100108 924482438 412205473 921412997 30928452 396332670 471345544 695808884 52733324 589630875 600916510 891066822 657388148 868624804 203540128 817283760 266654053 926092550 498138751 648224604 578533785 718675430 477595245 833043286 636433162 776627870 818981111 876939197 219960279 392007408 442950003 786523595 10613707 973997694 797969349 802151385 610552349 984295765 660098466 820391173 882365346 993718869 507867902 681739597 695849985 711591988 130027894 807777371 816144236 892647593 757697904 824731186 233748234 237233887 783677766 818429166 612049615 934508967 506961861 576046745 196197923 209899060 706497386 817701767 632792042 965031519 134287018 987937286 815831726 914977902 772408889 946433046 728967451 735755732 660977832 998337557 388829109 605132547 708955660 854375834 206572566 728753564 844848481 909865629 93777679 510461864 826586074 826859612 480468712 797181337 723351175 862899368 357493479 588045627 633881402 818369877 206655122 804079995 519085819 995831391 516759310 788762002 77818308 481576752 340413584 674175204 135092292 676459589 1 731917430 340810829 894788751 721573961 902291100 810881921 912553961 382347431 478449171 729426946 766828232 22372112 110121025 436468657 771484101 567559663 641824182 242046602 763288892 518450876 731493993 219747974 663645451 579506885 642089919 596660260 852668428 733001475 910819939 233440913 384689777 815332399 989199478 210017975 437433776 786035293 895833155 453098964 902365728 678997309 914656525 571973216 981072711 932762657 971074353 519358124 977184851 247232503 898539265 951193363 956891366 482715740 818851199 726004254 871391466 993229877 995409050 153940340 847221594 135248565 519746242 941004154 959040259 973181023 984171406 1 654990453 668732988 900573671 809991757 888329194 990697026 991834089 752884265 872745855 786239533 827215395 967602271 996481048 939506658 956224876 246799542 784243654 905826669 965015207 295209093 987379419 884502852 950739464 869224686 912566204 799972489 847199330 399185057 905697168 927815326 956675946 164011974 896660645 638413293 834808891 691478275 855278126 181391026 837143313 74280671 583573203 971107442 972248987 225026145 947292611 636697346 882349298 263987802 932473995 665137504 986087678 879946624 928377111 631086188 836096275 694964004 859522368 923806957 927420704 316309784 428715341 233560696 893338650 98195739 164637443 232335963 877460102 411168007 570316283 491417418 664425533 168418158 967338390 356377789 629855053 671551894 854807355 375096416 452252666 82420992 591646759 570939235 795306053 463966248 629739249 168527831 772134665 475731638 641465072 809208493 957057225 846909982 997696848 167599415 981032968 149420708 855561454 591491923 945397895 123174748 408977699 897283553 927630457 478547922 898650840 837592896 964084758 746690062 828962230 666912481 757579314 885921124 944560055 539828798 748046468 101175179 256433999 390580570 700794044 280075953 900352883 705874530 823411332 982560927 988465076 887375820 914363052 490191604 950391388 962507638 970595430 534529247 874136301 510471438 665067505 682604430 700923322 32666742 508411744 219324764 248524648 143947268 862027348 342879270 353735946 6817661 19227053 632702205 703255275 446593613 841722382 609143104 874033495 445404470 817508686 517008556 972488795 630539286 718180921 284494743 290382721 91146068 761399701 915225081 950114187 649334222 715973922 695520863 742919600 995420305 996865364 26412311 472131595 323228306 468561840 913988672 946805049 66079522 753510874 681188141 976747305 109931804 336005318 532085173 671384512 555352135 578499932 78887031 977351841 141029600 627487515 828352030 869459323 673765391 858910217 907436822 944198321 401403559 709331043 700908212 757861618 396516374 889927019 559118827 582535165 845922888 857023937 700110729 939241619 574630542 791427659 319640418 409271788 576363215 955983349 93342785 309430392 215619630 356798727 170871500 652952186 950853264 969316253 168305650 954988675 259127813 693136126 905048776 914798725 42125397 83142233 726540138 728054340 737352962 842345509 99431354 202205707 459222558 560775287 13144703 552551969 704758755 953819636 209297422 560073679 689076277 854121393 610318873 685602704 162236939 214077835 380735714 743053053 5321287 713543512 850102369 999585781 748886827 965450531 266827332 675015427 559707108 632086608 18573957 291904250 106251782 506285540 7040745 11268194 460112899 623897615 96294538 615842108 723555147 898467078 172936344 832022549 494567484 523487269 137279366 871859428 543486431 629777132 242668756 848758723 1 175809819 356470371 548273868 823768558 832788935 576182851 935729472 815715620 838711401 914899664 920563039 557713354 631069923 308184581 383537961 918289317 927907700 25046923 925880458 466115413 744202823 492612549 927395298 318684961 802571107 965500029 970954914 408710935 872900238 738612371 890039122 547869877 653575224 539708966 800770788 183122176 607411866 463814656 848749113 869856663 895382030 867969746 921547470 744397733 910607833 687975449 978067298 849731788 879454069 652914584 917507665 424165752 637797662 229723966 518256323 368914902 506738961 527994449 852663903 42312984 851946474 15153565 173433641 575898130 998081997 56385724 753833858 808999 800668556 780491714 809795957 767279844 823216340 199606169 420908633 200444996 963386785 348501401 459010183 400469861 536433151 648320483 941388334 421457181 941067334 559622710 890360783 558199836 829979066 473143788 727627964 263724085 453264170 474267987 980083279 594203502 985609737 41266036 738955527 687746064 862985827 284237283 375857404 435285345 584069779 979662304 984401998 949982391 985050377 225601813 386458013 550166677 803457279 890210373 931041952 702196437 771878167 9532255 266248867 54804482 803905524 561295854 959079708 306142033 968792862 728186582 978009498 428181009 564791663 634619967 756162722 84622224 764394483 356285345 812382038 744500385 954480568 517222183 592039349 106187088 506399450 860595382 899966039 880534516 927478054 500206620 631452080 171107551 321062059 866960582 904784136 308995465 758504320 926122288 998905049 291560612 419492124 615217628 701665313 452775992 878553216 394351464 452608008 306363551 596424574 117978194 914951650 946008037 955776754 534077141 769191087 393137038 707812093 224714537 562621773 251238315 476426301 325943104 670079174 249255207 512373423 270244592 615521331 155246248 751661563 571559766 610186667 968240405 980391130 660696880 983934490 736556626 937250232 858641615 898390531 75139923 833092628 519587410 817192883 245548187 945803967 120714863 280231294 960207958 977955481 348674846 988972688 928148165 984676320 159710167 621645095 783313545 941207742 795625470 853794893 512745287 929615343 706811851 945622347 28351903 39304456 86033643 618933558 393001676 529155217 96118970 493099511 217643849 865338233 97246813 396406071 956437263 995750326 508395769 709694500 474200255 775385706 412867068 931603131 83447154 702244585 284893218 530175954 271312202 768949531 253978614 735318700 655930455 800511023 924254279 994394119 183358568 260719641 748333110 862985157 617130228 728370556 342312481 983461119 555005396 685576554 471261053 627549231 847047831 997989816 233647422 327141630 489461495 608752673 151676929 297297608 758308730 817043347 509871133 941311209 498586675 730088667 741582812 856556592 801800329 930255834 257058724 282698368 353392087 758433348 263424350 953156482 243874842 415407039 907897873 982926389 584555941 888211256 240030451 554707332 355541396 920400759 562475790 840874730 388468849 927062872 868708133 977134948 1 542379535 557618378 620297532 974986699 980272843 748762380 972970058 861025739 896769621 759897372 918528564 313897318 328568454 403689076 730553978 7329892 659114066 582963459 701353364 23251669 78694093 510569838 915605863 899013555 909226822 756717069 890286937 382505623 834051233 865677988 982651712 459880559 662169549 642434593 910752746 351938038 716758688 307235437 571561853 706156359 783510405 966459158 970470034 510331957 603691219 993913056 994557266 459147226 639622460 893092134 928068062 390431966 933918442 702798533 739386685 577718346 768917575 676685751 998027626 896756793 949170147 638606124 941926439 601141976 956021773 88399324 692709890 363592493 539084367 444616065 705651822 8583059 978007356 584416448 820611634 434132884 881284933 37397563 852622810 508020982 837100937 980642214 992193807 665414339 800981206 907710603 916982105 661199811 873930923 562210024 703905034 248939824 907745218 414569784 669674548 865752794 866762089 267980481 935631195 1378467 698900668 863668360 944974367 712114909 712552433 153951024 635560887 332153661 659949363 70660209 504645647 37872287 934359731 746271808 820129644 474237651 764392124 726060404 974758287 599015382 766420390 146055952 375528284 952690358 969013259 455967334 728497574 560737834 873159774 592071124 874973018 421969128 478060916 541746955 783513297 597262354 922958658 433544549 896256225 726166900 749399803 578092037 852914055 873127860 896804336 705508353 888343918 246472552 974703037 972553825 985415506 47134773 560191445 494540126 957259857 909875627 968902800 864441437 944530975 266168983 598820184 27791587 297191954 925159794 951872534 533438256 939502990 182136084 760259532 997102547 999250303 999683155 999807978 204276814 961524113 705118536 820493240 881820847 960733968 332314500 572703920 528810072 539832045 464641569 755831874 722524497 956086009 432684846 589372607 540717940 688561111 691817739 884333402 624773857 941908687 916347475 984762948 857153097 978812262 424220644 981177740 130514062 186159217 241129830 478690298 666749000 863514522 745530354 756752075 597650055 992284457 347197337 635164342 435893938 801254453 647255689 879196626 704334925 869219787 805339574 835035159 379205778 887582948 777496943 905475780 929274267 956421040 339701435 715262894 359268946 783087513 495673977 736394853 157727474 386370505 564337422 614051016 811046880 930142556 739248317 763323238 648028134 777159794 431975398 625058617 959627416 972524061 133628914 727025544 283508113 427838242 174754387 845132101 448125761 557962632 563234460 661652173 622169438 924364332 202281241 843381132 385953844 940549907 479521018 849923345 408166392 649748945 533041631 571649095 27002754 547264271 14460091 600529430 29527594 728071838 283919506 632221330 392823597 814422290 77752985 506402984 12485076 454969610 420423013 549399597 1 92715891 687769245 833156544 636432733 720407006 602628595 746075612 706285293 761251759 986244215 992780911 940155001 960137174 898959443 905343685 579251051 661172352 729983667 935271241 828814667 850405603 560827649 765339203 927608018 971225585 531183287 745578592 562195118 822955288 539098956 585461609 561818188 818223941 345895099 749744340 217753900 694314930 525326849 596118491 179304375 240445753 317046223 892451357 767130882 809778999 933569046 995025665 678680657 874183819 134550125 699241751 334069823 857703652 608667041 814424910 417374746 647126804 210425946 975131748 252164777 491106247 64163274 117181508 685750571 859664081 441374890 557206250 351301366 823849620 414173960 983600068 742930641 801179630 652792685 714337022 72005466 287834491 396561184 745628740 374622529 609672504 155065692 652124370 667301822 804562122 942867712 998392648 584044927 745041502 327822662 750429156 708261592 969365058 568204415 701406242 392669782 717044234 17402901 703841498 845487844 848136742 51408251 82596486 147966231 747483868 630182373 948866817 820287132 863077551 993645038 994199022 123026826 293500691 681606071 849353883 675574395 846898943 298947100 794550718 795816636 856760460 245756199 754779289 236670675 365407179 968829380 981760482 79667554 539450568 808930343 937796441 807230564 995338094 160568538 964567027 528675878 578785780 167651015 969109771 141899515 220511601 206679002 349469157 198725794 815439781 52671032 804951589 669492437 978944167 696337653 941473566 95213105 926155262 684210265 727451825 557677642 672109933 336350898 531820103 340295160 419175430 316275202 474434516 242384131 993724148 338966608 759941334 87164256 260366845 657399160 875927988 1 565097935 844221073 905777813 907379084 969060364 693955665 733569757 581496046 677827299 365757343 999927453 720849941 725497520 218054422 581740292 1 996346202 979981204 993615885 525265934 529578206 365540709 661512269 512288829 716855970 450255848 578289008 822082575 934612669 630677743 858759945 871440923 918669750 240346478 367412518 205192995 544828776 147437415 747271094 411317268 928416984 643895385 861019025 608582529 655360049 567870359 815996354 102708608 541229722 894300904 911136710 649406527 882605845 749979241 812708277 164674611 755529585 962896295 966004865 250400756 441359906 367147657 699465938 711293462 850043078 527010849 841222498 767943952 796191899 813877798 848346425 251950923 742951728 975597334 996119327 144456267 430360154 599276305 735558385 212236475 308881848 771886778 944401896 503176127 842503654 610746314 821424212 455094534 776400869 807850208 822925341 788887655 997823670 75158262 255516512 466874342 940668243 625959924 674173324 631099845 842873406 782125060 803761822 61909043 124210999 102668357 623389309 933692681 983603398 713222736 729374376 521970836 953192978 481125860 908041856 244264386 641702433 221376932 954509838 227631785 743562183 507524289 930899538 384476217 944374134 749487787 971004344 56193929 217862246 215594462 758588962 359969126 922366199 512569359 864850755 463167649 730862009 305671121 632461061 958034760 958788073 710009959 828382181 843138968 958676680 233216554 294509506 358423200 499405095 487084454 799268799 312521016 566713661 444107727 849172284 448661263 549293707 557827747 575672289 660813207 942365371 880863965 930808707 203860558 599845398 178484137 412648250 548168448 564755282 986794118 998703939 686595868 875349272 385596003 619048341 172056174 433115629 151508580 739475543 998540843 998643128 896942537 993600963 864273517 967384697 378397768 913409013 470985607 965467576 561596498 730966141 213409803 882135544 639440064 911959891 714062588 963423871 748119216 909112807 623884624 788253807 875487761 958062381 975471484 983992079 877677819 961170759 753305654 940504507 157712695 325819560 211416528 754216393 519832073 558542492 584568767 870397169 955481164 991082497 402250496 715179659 811132437 911726839 918025809 970119944 368670454 747984781 527166693 705366047 432120514 921962865 668731235 757014171 662238185 911655614 764520932 814605904 884054325 977190001 376502200 974921467 152420987 626970377 368665530 385593558 370642636 461983372 347211536 609201909 794773256 855241330 607293880 947898758 832394302 839051851 877993818 955533904 762580444 997114434 196603585 462822197 947939054 948015567 112370040 637197217 478024621 872109277 458438413 738820531 479164600 638169671 604317998 907013475 546111979 653221338 730808699 858277285 881749883 930333427 409395069 531066789 944585587 950612672 973912731 976653418 820602288 870776152 636446685 758480326 959827350 989572274 495300256 539027856 886276764 994738616 398936946 971562267 590830614 722433275 592014257 870449397 830059931 961796534 496847453 579855522 561691895 759615220 708869975 725200692 299792721 689473190 665702839 813704681 952686287 987728450 877641437 969614362 605864240 891617056 13437104 572866780 566478268 868406865 990563959 993853952 889134907 931775719 886999817 912933729 644691224 720820459 910818671 956035395 466876569 518170590 268913867 448644703 447990903 574141141 147681573 736035292 508660533 547520564 473526375 671757317 338353497 858630017 681054862 935785031 681251559 737080858 935804531 964317173 614738232 899784454 94228443 288088932 962503644 986829772 809960130 970057601 702233509 954427130 419360004 505057442 958908714 963739158 438564960 465460118 132901188 906593850 680487971 730547252 87757804 375997457 725040004 842237276 604708206 846999663 337022585 636428056 341429927 691085352 867217338 917355250 327160867 833417601 737972670 823081577 788031314 993025258 775015493 822250327 675630105 808759880 160552789 173661511 978884483 983570284 617409728 950756452 213766349 229538007 295582498 464531977 5828795 739832281 782114903 840306942 571066854 750160777 947388163 953942836 6877896 556970062 169665824 194898304 413350092 978651024 834825061 944073951 361948488 493425444 812709701 863578364 365298773 586586592 576710959 959744101 936751684 986101085 538217609 864524514 905092519 934693101 784294223 893341869 455342097 579870437 721597887 870842423 865049866 950497282 952264552 977294759 788010986 877202098 268989109 307095503 619690724 852581664 232556535 365161059 578444627 938669594 482403819 487190721 601082832 965036661 911073247 926684724 828795336 918842449 805765636 924651965 980090448 984817232 293285402 561458255 462451878 929529745 742605269 960021662 947319041 961920073 302356589 678680054 936266912 993932421 546012340 637802639 785467739 848777350 371464692 676900570 624225083 756993169 11272505 915905220 424536781 776092406 973202713 973359859 693305056 851631414 454038903 606782012 102231807 308324432 253588898 941436595 166720217 294949564 274893764 291137749 755941119 957655279 77215886 843750524 291015047 752489632 364762556 883160128 94604732 370899377 598583163 888420028 250751003 812115347 425241436 817073798 945700034 989887817 984492243 994435120 238591697 485338434 642249941 664779790 212066160 376808624 172349082 725825813 873998247 989015772 819238222 879208665 634757980 999968212 183453662 675371146 210032457 559904905 243942843 766691418 424708883 548409742 95624439 459854141 666497395 937088396 607289739 979577169 837333460 909742201 93268515 928995173 970131353 998628004 453651940 936206590 123667238 802675649 427104908 559574478 947425076 985644328 286593487 866877186 866308980 921826084 94694946 407483634 398438504 572535077 77632809 892202861 702615543 859699879 704296395 746904991 273337825 317057243 16511946 647676468 72384899 692803241 745505059 847745463 409832330 434300116 240426096 777486382 844509337 860264855 221090947 480042416 441370128 996647333 502439039 826920187 785367623 980208312 181211635 815818961 211065804 554001918 948495218 974718148 346344106 477570565 799620264 871629042 668301516 750427759 263281099 835454998 32247028 223673862 71155834 399280243 501579194 920326180 271894884 774197303 202305309 988671258 189011968 756209160 791197366 972954832 144772468 650407509 186448490 249618937 768791555 854273208 681953842 890965989 199110638 913617477 1 17207216 779248345 962392220 430670407 658314175 845568346 945404256 985238705 990547847 383315254 459958132 31234011 585511477 361631571 461608136 807579189 936865181 907915226 918938752 626535574 948826622 706251366 752099334 657777239 752087159 358162696 571692803 299239261 697848557 702001233 937377304 829135660 917562984 111988558 349089664 355683344 525715388 226757399 408913115 281083062 653400642 760715278 795298610 788633377 885313727 606850766 862979295 213225082 357347649 355139970 516264132 609634161 862545748 846694875 963668407 483455628 499048794 671063469 704078132 688262430 735405585 109876928 934110671 433120728 943423214 979855583 987481593 895005902 954575522 386712264 748942745 438913689 570339655 849731115 981673663 733872842 807815479 209605875 444140926 36029547 445349865 659590255 700463660 170948193 445680247 13054196 970350940 591049281 823246043 215858956 639940490 279221346 733397405 902768332 978741858 302668940 630954125 555934248 630077495 916647631 985982301 848871516 889112149 346499756 920168075 476488967 585999842 327577917 750883785 601446537 625278660 186283338 813470516 783052688 786671095 99127442 393964910 606222571 753839378 371872004 773426866 778939793 977867947 16226262 936664598 712810246 892735743 137713247 861499211 625388303 734523713 689286058 736522438 402224678 417423588 529204819 701310760 114733563 768345586 421645658 935699576 569251349 934521913 343707841 792054352 385815403 679724775 587227995 891991255 325527384 394254220 273862778 439370206 222856557 803932442 734542246 902157559 615526886 988458024 625940162 706501667 150167284 197972194 515496437 966871095 601525411 654939069 658332525 980291965 861096991 982188397 314167693 367541166 518059487 918782206 495165050 846897506 946159434 964388111 417861235 687057672 126997271 177261695 119984494 402042232 8279246 575179131 170960330 380861030 664444383 702623117 451124502 496611873 295818532 781212568 632537221 982907934 785432794 946201413 528314315 624088514 224682835 867023443 412694647 933723570 143407646 759958981 666594665 856902956 482023996 508037731 131122979 329793884 510705984 824428774 49241870 394906823 670855914 728504936 951985176 979953822 66146211 634420391 358139322 620390188 1 433837513 723342007 880034514 265489040 362038837 329973834 440565544 770057805 937395395 435602389 633158477 968357875 974457558 438393381 910015796 705228139 830349079 442103095 575227905 211805552 884468120 959553463 979401272 596953315 990912441 777901493 860386510 214553515 774433425 96865771 554643341 218196535 616280924 189447508 888344025 701023450 919173595 50839584 860838240 224058878 929305396 223277272 323405187 348847180 707623432 787456236 901652305 105917281 267763939 687756306 694956405 862917869 990269130 581059785 665039498 363417634 703461555 83152255 620396032 406150387 986286091 328200964 798192234 958151853 998762933 470293145 683274175 748111308 833021077 288857881 332181608 543513023 784096377 377653622 974432819 505532139 957390268 61662715 497903015 623006832 661317975 109098049 690496065 291699315 637921539 320694198 898279714 538995235 555565066 189812169 620820089 593384298 936365643 409944283 998521813 22935545 728800112 19523881 591787529 622496332 645291276 234561690 928221340 227538756 436559060 839745990 960257938 170146761 735290820 771891575 892702685 468523691 898122634 606214578 927143427 707088123 981693580 293732115 921075593 512602238 650059858 311184488 572113474 253027491 303020415 416441060 944521929 174988955 696602791 219099109 260167597 998627888 999816603 591976110 727291981 185881539 734753616 852697036 876044770 935813898 940345729 582831233 628998712 417808706 589216848 406273005 884303490 754775914 820835025 555024570 825453422 237821432 763480280 754450931 909840381 170165139 173783030 587560888 931097343 92842086 781791223 401686112 863607249 806183421 931546013 678833758 956377961 512517532 825668592 520414994 811991413 640614860 994276373 450706765 906810548 980798537 983492811 964459489 974599021 752833022 971762622 681685833 695387503 103347536 953455042 846112890 962629356 318222710 637997149 31025451 526264784 118173032 762223098 767704546 893596932 322362895 867990244 609377882 774371083 6114153 143873887 795151337 860674394 917451620 969343957 598383378 919646023 154486253 239770175 649608072 752479658 705047335 791770037 124705086 849544154 324420280 331226002 274853438 907577203 478381594 627562979 833745747 937402895 804117696 962331971 251304340 513900085 425606693 587635415 81602945 367119057 423434646 435385620 845276010 957036900 880692437 963231680 702186243 795760548 679229578 775714508 355672871 846335086 189897622 797306906 20392935 538670406 218327324 620516527 992697719 994748288 425504269 533535218 552015137 736038838 146657239 412290752 508315374 758675400 439201957 580397117 450961067 836995700 704291055 940268545 400995199 857718385 701993634 853989588 30995336 335398630 659516963 700391791 336330325 546094132 210322812 603606960 722104728 724847102 336762659 406144330 443176871 678945316 907515129 965868482 308007186 481420532 329272333 999714551 418441116 755083677 731283963 790293313 993688176 999918615 326051889 615338151 776079807 925303962 341078775 998372394 733513995 932948882 362121000 710995991 442321786 626096326 625203393 992187668 454252879 958026213 539740707 898357602 371788684 407704384 62726282 700238383 928324426 976161622 285971100 884552511 435437052 769821534 276827234 459837203 893476739 915865323 467071033 894439876 586721455 587088571 840298471 888685206 84661552 118830919 59473702 231899987 203807363 680298647 478975147 759433843 496421381 798038893 23781331 738488354 910123331 965800394 714490819 901052687 505490101 839701527 709832319 803378114 773595733 855427892 833240696 982328961 201577144 975118399 897207057 924904643 774116335 960027094 126233441 140499511 285951224 902371412 107983277 169158561 956661187 998451404 901744262 991669487 191795240 247585959 847491014 879077745 176427815 242930554 534556907 944992932 992388527 995338310 113058502 674535328 838245516 963596139 107630616 830195358 691103302 777061912 292937545 363910323 683887986 834870441 656334310 966334058 343082452 376011441 928439804 938808153 358837003 458084324 849096558 921680045 379484642 584673431 489631384 502570831 61074171 225081429 21771572 795094633 826593868 951810752 621275330 845382051 1 570598390 288469353 383923568 852154802 996227610 969591234 984411200 705346048 894305306 490813838 766994647 869354270 993009208 447993155 778702476 736563768 790883090 204010734 454248700 693498395 761780968 687495585 912667484 53476422 574296616 850959677 953880818 581801721 750097318 778760478 921146725 567171506 830699460 966718207 973658559 986458203 992515766 364965184 747287143 788963015 873205573 4941985 579820038 173973606 215600150 984992621 986127367 585409967 812660308 674322947 784354244 720157405 798826365 1 154966461 986208961 989302165 775829046 830265916 392936542 765317215 624319649 744371463 900997924 999360344 883132073 909578526 947993034 980498750 489288366 789434019 704854562 883038781 799942793 838887184 426944454 951516303 149634728 279428087 899358525 997460988 104451788 497842140 135018028 669806298 566989497 728265648 913329175 937246945 969696580 993223583 309209576 777081990 101349774 337512161 964131180 989310849 739916523 982751938 322205179 998086417 233430330 656912831 810796664 916731994 905490195 999176370 635323901 662967803 754035623 754187663 469093032 685657620 445778870 565609435 873628116 916729686 994239917 997472421 631585871 797296389 132239432 472669750 607405491 656385531 663694155 893652661 280204484 694967870 685028661 792261132 205950278 701673624 966715924 990560874 281383836 657307070 841383715 870223279 949928371 952300408 352827689 832274422 410342372 484800761 29635815 233916381 215510921 222712886 180317873 862784071 188359671 967400882 478185868 725563140 940528104 959780608 310414609 854329029 162166254 322440996 847393528 958074036 646805587 661499878 701397666 813010889 40429211 892699353 539433575 698711446 341921895 880924711 869962390 960519063 117377887 578621712 950375030 978969992 956700082 985799298 807310408 911423570 549142327 764974171 569236863 886909104 1 691710060 138694134 266052396 262692069 353650638 635307068 694157574 982834945 995306095 227867563 235186792 814133475 879382744 35552148 635000845 846365697 923641483 336975762 847051531 172337999 493156025 957023586 986594531 860495696 956436001 497959972 600462984 780889060 952017946 176453289 614965458 662714183 912017821 600583559 878280925 999632328 999709831 139412434 269141751 72078206 514594390 6763059 837935270 133335317 918987200 760977685 985511777 83875616 264736323 923516374 957060156 221561506 861283614 166467857 980947065 947810702 992694392 347248261 615986128 483808296 699951848 728252697 728702697 217299679 781442274 867133291 943707843 272426227 376374637 338405161 436572943 1 931025841 399734870 682920676 642360465 876388618 152469704 863981389 837565598 880867044 455071930 809133319 17481340 399355123 555106178 777338561 360180067 729971455 645645143 927547712 788650798 883748443 598894116 625304800 616907349 859442169 65904461 158074398 254144441 625958721 623993947 675336757 25349726 473311234 896580525 930482914 714922540 804233873 901359633 912421852 954363546 963079024 738645590 827177134 664771425 897750692 211642555 940350555 261897777 709509490 570415267 715330161 947943942 997386967 17100813 565537645 780070565 835529065 12108390 588910046 981139993 990758214 225803964 974704399 415357441 928199594 558774012 963441588 1 510431011 111291984 826873146 206028047 857603478 126677419 384665542 771170663 833094830 103051451 695362185 883116890 980302079 771285878 870410252 66444648 738189726 833107195 873269401 727635729 947061886 385775489 755482805 301113995 992066937 488421459 877870775 275125406 803446396 346564197 355117054 309197976 582532565 262722986 694544447 121893036 317321636 70749626 782867720 694583379 729104638 842703412 916693162 753214324 866979935 346284204 404032961 778229398 983228347 590237425 623853289 251931316 571474052 676688565 932650540 409610350 908320199 3677965 364837734 195034623 479402616 291120795 897401443 436891285 661861697 934541709 945845781 205934981 445483900 377806399 433741935 670718795 742000570 593561135 813219409 708171494 984078703 989151738 994160433 684838183 699064791 616548376 727895657 443535885 861624221 558376263 693412388 801314444 958927115 911080375 915122039 458247651 635956667 187242746 330663834 206580365 562733339 739304696 937958025 543034933 759458245 322968835 329189964 183697303 282924379 290130921 677376704 674602499 938453460 522077176 718263543 479959123 902099802 592101393 709738381 132814256 291119320 153777223 196863462 349092828 939714634 360439816 565613108 761455267 897176109 515023420 958476906 629806730 845785471 928337848 968813522 322766272 834889707 828609066 863246889 656543915 660993468 315910398 829579787 31724540 776098236 851793601 897868435 578873391 625714079 930887290 947867691 299359327 951674110 734375008 802561529 261768596 838942921 485484117 987161098 937583934 966580250 536101181 610338028 717788572 991673086 561618910 882059170 288068407 772071882 556851384 723256967 319423937 845967893 323675507 589437920 311549651 537586189 674723794 854770517 939216071 961329086 675366223 905232002 569423033 960475859 606664550 811627451 764745349 934004867 583149526 702967460 478363320 666844048 803142163 923642416 428541852 931454582 814905153 909549151 493977408 855662760 453797165 905638865 636311897 896823451 683937291 743511944 471696505 904625895 989590955 992161010 394257833 623009926 493925894 571469205 499379399 561517772 187756531 808026729 963929556 965263364 108364957 111411880 153169923 701354805 520011964 936672949 813472703 987451793 133671536 984685738 595396240 875815081 480328566 922786466 673184746 728173197 752626791 889025520 984763238 998530497 332152979 975303959 43205703 724967268 276733346 893219172 457728291 958543448 599986180 965398513 673207215 780546453 817835256 822025841 964239137 989175498 362818947 953360827 733210815 788504500 305644702 673392635 999168271 999868514 409667706 962800238 813892451 895332420 344241880 912799947 611309771 994835369 64753487 528872770 725521816 965345751 967405447 996065027 809645224 876714894 494896917 980827372 224450770 639605083 588896249 977662864 294273969 346180767 216271249 524141720 610107158 759773076 617664763 987007633 197196586 582892301 852038777 971045661 475454908 700851025 941868224 954072420 579058693 951474571 307974863 675361259 103791970 470585709 29902574 323829012 732396335 758748461 460133435 511329305 627082716 852437969 768339837 847991585 784092648 981354574 390512005 455084681 143227716 348608276 635704757 849856024 511321335 512603979 146056969 930839727 960511327 991832038 658505604 935495777 413989428 579811898 927103220 976198492 991734626 996607134 313799937 397365214 518791723 810538753 363647037 466760940 934329908 998843029 404455961 660005930 293540888 792419641 788701774 951180546 512789291 799430831 541547167 681222768 423678551 983755304 715843859 818157648 640367285 999872438 782581095 915906267 979110307 991082532 135265876 985606341 159472918 720815006 997387380 999107166 385828735 628304937 194843042 467683815 753143493 763875193 654325303 905805893 169470820 946622267 858617833 861322523 603809713 617117187 130752498 700003388 997048127 998510455 264299050 668343172 727793396 820624473 869020444 984197178 186717167 504463541 860392645 992350395 187002871 651278903 771312904 808505709 287989772 324381555 335650963 608866137 706212201 892170009 281707784 545971296 604197744 916761986 280617663 619980264 965226831 991093736 444336922 751379862 826601579 952278782 936639793 947843410 998566181 999421507 745059241 835187973 293922978 741541887 518173704 533005142 133714235 149243590 383884871 695950031 188530936 798334752 990590712 996606089 269226271 733480497 314735019 575969687 427339051 745158382 954003312 989926384 416221409 937189979 1107325 355024356 347373306 829197771 360570439 725593531 674742428 781004432 718499344 731848217 186819976 939103505 789330343 829903770 78870436 683023340 229215263 471259200 235937596 287878988 782645499 874325105 361700278 462135663 659717392 886895503 101542946 399549981 519335530 892221895 209770675 291155113 210121781 478439082 195613710 731338328 177819352 232632542 987780431 995181766 388143723 707559601 702435446 901546737 777602777 862172142 580918641 826531037 918950463 971006057 992117575 998144674 474035893 725923762 715223948 955241303 192625895 509222225 125678546 977648855 617030621 727391881 233050383 910162354 818115052 900352251 386010282 398214714 599072757 895731632 449064197 495382041 759252493 784385789 976169053 998992191 628991482 991613242 414881072 806535692 951211458 962379815 713766092 910243750 6926590 955547014 767225832 846112557 177097285 294093111 978741303 983024659 590038814 786749300 657614712 661481221 857509533 919240025 267954674 752642619 525840471 599361563 384630885 644702860 656733828 952668631 726703602 839097569 151621488 378031186 135813849 859054573 677131779 859154786 174591554 492539051 192217681 310033787 1 663769595 83204632 878436635 995591430 996389947 676648918 800583632 115026078 434369057 759469037 936954197 649222541 654132921 669637764 844727373 886083568 947657360 674308826 783418273 6907291 106727086 686925737 734821218 906321082 980890826 828436306 923543347 172342834 182530444 474903323 509184757 237883485 836359180 964581183 994573654 891274402 941563591 558874729 705810606 319310795 867197953 904841632 911661016 907050245 968739243 502916513 621597844 961076581 985445863 463836720 912971804 259322484 321737474 780583586 888839151 111760599 909670382 683620854 845569347 752447193 844706689 145124736 639407685 979957980 986541574 365013620 921206380 758442847 895159427 284849604 922587038 61102514 165716510 754509581 784230459 553084978 707568890 463675431 723837474 999049723 999716238 779453991 853430280 188197874 255216853 720653421 747537190 554799297 978865493 261924910 843122105 549133667 918457601 456845709 921459426 812177813 827921968 412756131 956932131 258602946 740910543 812109423 940000742 709167960 993038558 848153638 868943300 131305351 735144047 874311817 942379932 337450796 549260836 463974114 759918255 893347331 924286507 553916696 613280062 547561520 732546982 693909591 721320571 747263914 787330484 27534167 656771454 62222516 191751276 754027180 874560733 587585651 974648618 943321951 961926447 604795997 806280296 825633398 835536046 678353031 769821924 94658914 610630363 849760790 903015553 827211286 864858102 39171937 445126803 350253634 918871972 22842579 358510489 991394833 996719605 484752307 865933492 551886344 871147041 756701277 757738310 352207570 747229321 725932384 929513834 376772716 480659322 541116651 995460461 999929520 999960617 593513029 765818826 959784922 992970800 715037264 996653973 440285403 667108052 973013969 993988031 878374834 890743217 818202435 823808600 194590131 785563220 397518722 648452851 730894738 864913477 540584213 905844952 437153866 802605827 532449075 972302779 497231069 978459206 9796646 856960216 500100175 550016978 261280014 646099128 33968006 457249090 903079607 988264390 585009531 997585923 750807961 858314443 273365372 759050491 664420330 679771788 777336326 884684267 621032328 665450415 636285807 637208428 883972073 960364402 343740488 837763530 487439406 998065032 244111493 537685079 957951808 967985922 55773951 560474688 338688727 923641117 966734474 994739869 266000214 863619813 356256574 827430592 36850787 744170535 953716119 965205991 463451437 849283752 373679823 461539783 869604578 912879038 786987301 924584437 56844845 781791143 402446542 424540759 530626238 921041283 818297985 971330909 421485439 760536406 894762286 921153159 1 283387076 965540631 990623439 506025215 867354264 729060115 828226998 330935556 693841493 688007572 952646267 952160617 987094359 381942221 681871808 587607323 711642259 815699373 832642470 509118212 654975932 57180310 753581668 647221902 870709964 805175284 820586157 975240253 994095396 67681719 440281632 333190267 630733478 101806243 387557534 22832096 874933067 896605252 992480938 613995270 743717122 168849484 694022105 319316200 454700255 1 306777860 572379928 578478191 246045527 822365662 981076272 989020935 794001631 963032941 454410912 812853776 80015961 816089931 678568935 946565327 529452020 814155708 943860262 951117068 866233120 895992823 498831140 789532471 826794491 894281462 196444710 236098919 467798005 652075580 152412149 514592772 537807214 572820334 523436539 855577925 929645839 964446099 835516893 994281703 454613687 650763891 480026596 637350986 818310612 986552922 374232014 533378281 552881442 630657215 294079627 695107632 75096444 665285506 176562248 681872616 786263390 884791729 949270683 968518346 755402699 954549922 535218185 889885351 9303045 37323825 290340800 924773783 361229595 610213099 524062288 659842281 664094909 754005448 777126518 918046015 445771641 861539066 524932413 749197239 151065988 896365080 898539384 947669408 121930028 565376560 374770955 517692351 963981813 972665178 556605997 624793277 349328756 732442193 973740702 990651290 542210289 916533174 900487746 994984988 415827956 760337136 816700245 931269375 20482700 183594990 884472085 972403386 602358564 698702492 738148089 940966707 957687464 993303779 591936317 990492592 212118916 463137606 359455321 871623667 643764207 653917248 460035584 713221502 964424364 978253443 574700281 965345545 287449129 406912679 576823019 673575689 684187193 740305600 290540653 570642998 41803428 347093096 394451392 971849045 237945639 489242664 258770109 740238853 20764893 502121139 464111535 466934457 181891028 423572078 600085957 883325807 418439081 710522390 224639212 974948764 573742922 775136868 794043976 831211973 127529181 376988356 58315597 678708971 956357092 969852518 599616126 964902035 996542807 997213694 341384135 793050986 87973724 873473232 553133989 998943047 80564098 601084451 110499795 602754437 108154360 656682207 178854787 565429043 278713947 599333026 246167934 413091395 576026213 582931020 315219498 923433393 650845324 868560587 595066049 636803072 664809366 932375586 506188708 630387028 700839076 766654964 634679871 725074118 481542948 983963894 38559759 819631676 785344384 925523398 128325095 177249156 9367066 871119647 611370625 987921034 755434900 866382157 973841752 976314255 529031650 655753732 373302167 679377933 284963438 827266228 547127632 924311233 226274380 450443847 656603871 912003732 995885939 998658833 58561551 679927348 342372687 626686987 276941058 379949633 898977810 985644848 170259324 395608144 749450884 832787853 389472433 916120800 833336782 963609350 641108233 870869991 959677800 980912855 125313099 343288907 500940258 537246350 171036825 815187354 330017692 898134411 145478925 679813488 261505774 561388368 180814442 910095734 474612549 779569634 689716216 757888658 719834098 805023053 545491049 924063187 81239312 721354886 432893812 826428810 601326621 753784214 851625467 997929883 774447748 861005617 784437958 964566502 478400223 913866400 245220235 981319722 341114088 423860871 452903071 989006783 939827115 960875534 119159343 293614348 555800888 836643592 662069268 724169934 528808053 552901773 978740377 984862121 185589997 909144071 303743604 851215089 963932380 984554902 188158060 776038081 622332189 760331016 441857889 720095146 261416727 608935876 568798430 647724501 393354637 992132439 953889438 976229576 585777930 600891039 793450197 814533217 366407149 698899422 461016543 919231243 160566154 265224927 576011652 811813657 493594159 573648268 250455627 729243370 353687855 886659307 224265249 431924354 848885139 898201884 956595767 963854307 793917885 972041879 113472444 492380130 428460633 505002056 308508378 784040868 8175291 517541736 745361165 913779294 530183355 808409918 760198123 919428401 882325534 907812840 641130917 759648480 892462020 935884414 252423153 369111290 741584100 946409827 181823282 557819678 552372357 948560810 851741232 982485693 363137687 557437305 610210598 633238039 443949377 840453155 645926383 900621236 752628811 939376863 344862537 485728759 547854095 849297031 630349315 924945427 425659254 509824489 147005857 962096334 991643466 993940012 910072316 929713276 446896322 864851285 26150492 557795137 57921942 925721348 757992322 963360481 760873803 945583101 167630843 306247264 867193055 992261554 794726190 958936229 93051736 874404044 309291076 579071535 145153604 933916414 196681587 747512591 911254166 967045229 195931326 352889261 752868739 799331939 568727018 637413941 736215033 795885871 467450406 711887273 619834139 736441744 958478013 982240059 239374654 893804045 718394966 903989384 798727200 915813401 488435203 813124394 600967834 683076156 402897311 667098581 673685734 976952311 638951636 816482128 165837596 489311813 632421204 941584265 1 216762043 279233340 697169422 533012691 803926786 120503859 517513987 752153904 959781511 215980912 664738362 312969104 458035286 444929465 763409582 309129740 792882960 565269270 653120770 991376402 993989242 265621313 983059837 279032750 903009790 578357601 947957362 603789247 967124495 796928182 974415823 909708197 920887929 964949326 971117001 933411521 984218025 858830279 970973198 8769120 462183167 559131381 901891144 907113667 934236826 423402906 664581592 238900721 409609401 876407017 918802672 892304824 898188728 266654653 865119997 604790486 698564551 884819144 989410863 651454699 912958376 884940628 887831118 680044163 949195779 440206912 627017087 30844129 158319206 831053257 910309071 428571884 574482854 664501755 894206407 267031458 675241458 282451170 985501919 61926793 488455177 572202113 577130447 685417433 929179218 512297927 650545363 855875047 869866066 116671512 995468637 977598713 996528628 546623317 932745181 905048553 909367277 473414946 942088333 563682513 624827675 868070382 905469632 192894025 958265545 760622359 890626228 823752493 949895406 931261301 949350147 371266858 620301383 314636470 543564696 29372121 548392121 663697979 769390677 19124621 381852064 853242288 951158109 623197195 846229747 783180547 896517561 232859823 281663353 541432594 653169617 665516132 785620160 138823488 382452433 222644879 754693467 158417438 824078161 230277317 270359388 182404571 433336295 512745336 612173017 750477047 845896408 514639394 552008785 625625900 970050180 431532105 702417869 324203291 362499480 605708300 715895634 737342407 769042790 953152469 953469243 467177012 635995027 994772607 996147241 117539879 491014215 842596083 969514044 898984719 971439473 673601719 992140435 898320382 940823464 314727167 732187915 243913802 966866856 248098457 331079077 810914996 969359989 759536971 910309545 153716012 379040277 55991062 223351743 819198771 936736506 69386500 772614129 332886119 726712503 667970603 979963382 491115371 703553789 996801965 999338679 972723067 989649029 474975502 963931100 550288761 629551251 741499443 985450609 850536096 891110043 851699703 999936149 86805013 586209704 277648424 781267446 452501567 783142142 545121347 809187292 622671218 648207376 510896511 744732250 694504322 958949468 646153954 649309583 539913952 659898353 410851475 511514752 813922867 829690903 756666700 965487049 921838578 983975926 113611062 938716898 716126542 843307543 585437518 870264404 425171293 679481676 573770059 877494527 962948208 973776462 260605258 984839605 131077570 875016256 607839130 837437734 475553703 536320119 811834143 946092122 55065475 847803965 791264244 979368559 404496862 862646705 89648733 117265750 974282164 982487171 997440911 997910686 645449183 737863724 604981998 768514328 846089197 913928609 143047665 781775979 139687229 187657502 612770214 942881319 158542516 290372441 932011022 944417703 902637981 930542740 566631314 571299848 377512509 547405680 641207274 725896948 482261743 619749480 409459405 735746911 31759100 819110423 782563557 984420854 605382469 991053145 70207544 875746264 884811413 905383228 127222868 212875930 190695776 432563799 593509029 804055908 851721960 881723222 11252648 773324504 444349789 467530704 274102377 828923655 236220360 615607002 620723538 926778792 226463767 972120301 496186485 882782076 632042010 738667417 240712801 692831551 383105935 709958623 330804758 523355133 643820627 801525791 447027908 920860857 915797853 925600909 297123917 895822432 496087427 707576611 52833735 414640735 873099024 925368101 825489187 860250757 650924845 918684351 130879964 444682932 278930694 572188902 478984994 948347497 703808728 825840817 666761018 878427464 529711031 762394718 693510548 950436745 980856102 988555568 170148083 291078477 428359590 808653603 732012100 772175532 622237754 896012508 866878651 929095748 138646536 671320099 568424884 658599405 119570973 905969470 344285174 620261091 631826767 666330099 134960702 881317188 803884921 928307789 757435643 928552194 664993348 785901104 290794692 938375967 198541198 268191770 65083972 352865947 321981196 925128523 115479160 769688601 539284778 794437785 638866471 709571619 989654066 992724505 443040036 514911859 311727483 923949481 963775303 968282053 56875189 352638277 700802208 711929057 576307532 892391043 774692413 826881381 149109678 178183142 52861581 334081499 1 291323704 565735312 584493253 82643512 730314388 466063305 509117211 816558275 858847214 505877771 686770013 45140036 283669230 920505138 944534469 101352536 250813802 55476697 700774049 441089651 797610256 797490540 970620235 348911834 567112728 708469583 757123961 130520919 708227261 231318430 721489386 82678799 259101700 118360945 140971606 779089029 847424261 560263933 763738370 383987563 888897335 389662533 612724784 977026296 980664135 274565078 954622118 869829351 935532137 286455557 372552359 777628038 972260692 146585693 903259988 388451536 921882034 779195110 857890362 411413671 692933647 201281745 539639536 780515963 985570638 701792969 707892518 166173975 977975847 511299381 588098751 334263403 747008527 668344231 820339198 535478290 856472274 448723010 977827447 277390276 693486185 691137598 713544473 689030394 944768294 420391085 940616125 117738194 562797198 839282039 862335421 458543689 468782170 141802066 241078425 946058668 958166674 822457431 914004610 351723522 426515351 438360415 445944808 988500034 998588695 479298176 601544486 823242939 987451234 364984007 486647436 792458582 832497945 32782976 330885180 284487691 691447165 739656264 820242497 645990924 967987027 618473395 866986694 561753431 976383497 922817086 929940801 71767431 285975478 753402519 967515326 992134910 992893279 421268827 499923470 908868321 958928132 855447223 901970390 19864884 277121057 102221544 610103776 287409653 966130395 764411479 839142751 342047711 636853729 142059053 723529279 212268636 909481203 980732895 985067200 774443255 807752019 45525793 384174623 778411753 880537242 479101963 923872813 58539729 67873362 389756373 630903455 654981984 935373952 827257127 900592846 816820681 947325417 163206558 961395780 988320070 991321968 486530379 728077070 166042427 265501679 522487349 816926970 475457062 955999560 733947730 781267378 648426000 751393695 91984850 199983572 503649030 684275562 107840808 299480757 243792791 631976576 834758555 933927198 529437153 784964522 438039417 734654785 35490255 565285033 350708889 793654320 501984286 958498556 430397255 848320706 703788986 919146907 162189407 482109327 146463157 838947573 260214563 418707234 569114621 736803265 96221624 128329832 643730742 956514423 317887572 550592807 971073449 975803270 681924461 966961682 417758555 656633267 301232148 635262454 446648374 924125244 722393400 904678351 142723087 277075925 377794089 549286033 889281082 989182467 882264081 893524460 984494358 995351032 352983394 500421183 300392968 625015803 307260599 844243640 496368411 761768412 483870038 888859287 179784586 869188347 609554884 658537124 629171726 945233205 548428857 823930802 170733764 310941975 902191326 917916309 534575486 786415432 588103017 657873265 130525177 254485464 325012599 640136359 996088644 999629905 744467674 881466606 898903129 937519026 238302690 832159275 196835264 367072770 395052004 644390373 789166565 856477107 416099123 768200032 265231902 890740688 857827308 914136175 309908032 851912747 987964337 994628643 648198078 947571858 105012083 331017257 810203490 864520772 38609882 901039366 264176215 994437871 383235525 981563062 3654277 804763241 434108584 526054753 318246770 616108663 545223373 796352296 517002251 715491282 895376320 939194632 953367118 985313434 775049748 802088183 235669976 482180525 886913691 931167589 273493875 945260417 516232551 776426080 304871940 324476756 81494504 999671581 974661049 981435950 595083502 918606488 880024034 918423984 920053954 971627527 861394429 869725509 793544524 991164477 750195420 843599897 303097694 992807545 449988152 540715566 586305705 677639495 742246352 762430549 571456020 817123723 733220098 838826258 944530005 958400775 309659004 621145211 384953610 778384495 363362264 639657300 617217528 630013132 518358926 652604556 464567941 823707158 424209549 937759838 133533784 523822041 832096495 949699392 341999834 353658193 599349606 730680181 920593913 985295707 901708779 979811628 605211030 920710961 302899904 567536895 571184950 730965070 290812600 793943895 791949152 859543858 673895680 734319181 474830038 555602025 794934116 913831348 674537028 750157449 52523021 828606998 276939206 806793671 382130339 445474558 440458309 647052473 832725817 998915536 44064058 636874398 43022110 570705282 710283313 849726221 45194961 834468734 56301381 671165091 907069853 996998854 913104703 942824949 878949050 972254437 160353755 301416925 475456953 955332697 33175932 884335505 323754177 881073763 259543589 284350437 536808189 855054770 372532073 820839635 232980808 572766462 287170087 847358463 566737526 817762087 232545809 272018863 996607471 999855682 1 46160184 541943768 558485364 146567814 898498481 477408627 525307824 769441908 813535419 424539941 659599905 504071580 976399369 94553410 880713352 620599619 674033822 302488431 555901274 264344215 906964100 448242808 509179460 198058510 243023191 601058858 648166413 960074999 965702086 441280422 765475122 853819623 942893809 659432304 712433251 49901401 448523620 251632042 732151332 785505247 839560584 834175978 926485194 69840613 237796567 491987919 751632540 220740475 410651234 36153898 440259605 923004554 966240417 179274895 652626811 621461085 790272585 676065230 869552328 404010934 925212617 14303251 561386500 827334702 924594923 359172362 397516911 336941852 835892230 176887597 637090005 533838912 978478812 146594482 183325114 933129474 965290600 193537536 773390745 41609184 706768827 198605995 958480916 195579633 267024466 277419743 932206804 728782009 836827578 775671010 918937204 493915283 818072830 468457352 822934509 168522112 502004885 603027155 829961622 57789580 991909527 626464476 820250863 962112747 992606845 257766755 733577057 534962390 626645343 973533243 998336398 681113390 709815417 315191417 908069853 745751791 848756125 344519614 905331893 148208395 679430865 174118969 488505057 120421529 538034559 930794689 982111060 765488686 851094242 577182387 935669655 213985385 546500397 56890838 65309597 200087196 336201824 142157748 528390114 783125441 849750710 934796046 949001543 910304640 963432293 1 383072041 38864345 883859494 804039124 854716141 431001034 451646822 982872583 993626559 422580495 641529530 346993805 519032409 714194621 916500504 127261947 707783414 479227698 512080116 336270747 501632896 590234721 883847222 480932134 945546589 969388662 982557112 316893523 953959401 643145131 986662817 498407043 923808418 720901843 852945154 794473680 795161604 507528749 778909142 256101446 379585123 844412223 940394284 998880589 999105087 530322139 820881927 469725500 671512790 410001448 670136482 745146014 925169819 748577008 851080833 305886609 345426803 355576015 586542298 600119410 718944861 201270883 569698788 869600374 876842691 848969427 928592884 338338368 361115943 862351754 936867895 870212667 905559246 839867459 945174667 795432543 942328063 577304809 634406761 14853777 746754192 640721585 746918175 907496938 963818370 595710749 606357085 351138160 483470273 966429010 984573639 241072130 725187769 826816852 899993513 176221518 552704137 891059200 938995691 336478671 878268426 220517357 371531626 754512330 770457776 578320995 818791116 445126882 475208031 232641557 846709361 147538233 298437407 85291061 102888900 408806249 624344586 183436994 784231907 681323681 748209932 737574548 769815906 878577216 894896321 631821383 762678095 370350898 654383192 357942235 395195285 159605735 586981448 435085219 988694672 947668241 959008322 663185613 918988768 412912266 567546877 444594793 779794531 134914159 681439348 354238220 922057822 284128825 876513339 893431483 931716730 725625819 904427586 269501179 640990787 885630838 914807917 16620497 533574354 578198708 863823551 425379772 633456449 390994386 667801593 184028889 862017275 456707097 881375994 333144144 663804964 763851820 809041686 5965264 261476599 559217409 913063532 337586030 396852403 806783484 987443320 914367543 965490778 420102340 736018087 136344419 801610866 434401259 461364608 399993057 731217215 985326599 994490833 9373580 271309713 778940878 792754256 969319788 973860614 942147684 987691455 825464749 997141571 844447009 876282734 597424220 744266672 675248819 679524859 247849278 381965139 407969407 904618240 166706002 235726102 665465175 799407953 470752213 567199253 463152287 888289827 71257293 134440093 101060277 641581949 819840236 966451922 517433294 857284618 883077401 884461098 71389808 625917030 236543084 534730637 748555066 807156626 237663858 492725154 962815528 999827376 843163908 957930258 967498029 995601685 380806831 468917041 466683137 865250258 334263436 586235320 602308519 607793064 465426585 557073533 614156990 730505385 902824561 905417840 35715387 682728595 598818979 774800018 185496525 565319868 858063929 982004315 345967271 353087802 771966759 950865677 437922958 468268383 771209580 940242942 476816209 738350363 991568857 992957437 448975327 933563015 384051506 965403553 954821311 963635643 535201215 990641030 316434436 938765601 267082346 597351350 997404776 999491922 569160308 856492264 727169171 817203030 976138486 989812536 481979941 653383460 578262517 675587258 76113570 507793199 271754672 770821849 12010304 855805153 281565649 714889356 190960977 856607891 110552009 817828138 451600217 830720123 565694057 700629257 709169335 750836650 680388237 686632994 675165662 864269963 492370874 841177107 38836195 477662195 515985955 561222753 223724973 251973187 86799195 324897389 131081958 893868605 632139697 668472854 997466999 999347729 601023039 639356375 324900171 597835523 60944188 295739842 705898299 864304134 761027655 850247616 862971840 939771476 548218371 768911582 490014648 818458811 674478400 871291348 482814781 824393544 118501052 732675436 905003791 947936244 306611379 791857083 408475275 968118940 303685626 335141042 552457126 755120698 428299310 971691839 822381438 965483732 62531251 605099568 729005861 790467643 430145329 882659338 843000029 933795972 797254938 857769807 303385609 636506794 107701063 715193860 755081941 917288722 375435138 590378327 431222110 577064369 563698840 566675375 905595701 906288161 551588183 704923082 613637414 807343618 896942152 934824204 839057580 930839571 600929628 876516803 589875343 856356883 269272211 524013092 932489472 976112409 548473367 777097769 267837132 724017313 689957510 755793985 227241113 484767226 289074684 974190111 729228090 909213631 559398227 962158836 446547681 806795741 348070986 376544300 996777774 997090573 75853335 998735444 392649354 628669617 600414598 666548292 344270745 605162660 738273902 926833358 468437071 934432591 255501597 969266542 526435626 891912814 29910037 405519115 492448744 637411207 827678 608298975 191626198 269070097 265672644 884928056 834434645 909341338 117161763 222162104 216382327 442827814 122103778 270492053 342688421 796292194 19882317 560025583 661090234 797529126 400899477 768214915 949140631 995770072 178105729 872315169 545015147 914869889 38392618 586912966 889642223 941495041 972944860 993805371 101764412 822294506 337633353 385109341 287464779 850176527 766775587 881724632 736726286 760442013 83792016 230658358 744729657 938736590 283167741 684433951 44968815 995300163 861533409 913197811 338638300 426199661 936317651 985544202 871279209 951583293 567788385 801359247 138026624 865511336 316933584 351681534 231151553 751140519 504966776 713553516 739359460 743648607 303681242 663608875 703891633 810157148 911130362 982850076 520890485 653870206 342007215 643324534 362060743 579241586 388735242 740200192 776938225 867191544 49031674 535032469 640034592 729081488 979163304 980617565 891566690 977296221 539377498 925007707 481329862 593648099 470416487 926051379 16387239 110470703 554977536 897232484 424463297 901629238 754358619 978137552 748329619 782386006 661417878 828671460 127551894 780194895 974768241 990217274 485373723 541967587 694206906 940387909 988455817 991725574 805129498 979666265 793892885 918609282 890236263 983855501 959908563 971962455 75684195 795272157 479720872 767551421 820742975 992468397 410880872 825038417 512092273 898725147 185493458 209251038 635232567 885786738 368483352 391012590 921386437 989267386 283839934 895794329 840372549 938858131 32169470 319602767 939379235 978656873 930697701 990037809 612214015 654499322 35594685 736774771 745618346 930889754 217663773 441940304 151688948 374029116 189169028 631982596 245456036 582779106 502220461 716983457 478444020 684068875 209592540 361728247 44443195 916846226 410450475 471959396 568613754 738306875 124882618 758046341 94290215 515262193 830735451 841891110 147642751 637705709 742932046 768890582 616604206 937183251 209780371 812656196 139340960 495979825 433772916 910096447 389354323 688915715 369746799 666104102 12553893 91599535 708605568 933096326 571061157 602477700 549913271 991987486 1 202079633 307135897 426611395 959930300 964907395 268729978 309739066 745440023 815096627 808538193 919256947 1 159639598 655118525 805248503 1 175225702 184610535 783726493 249903922 708887975 856965344 896355221 568886629 651045020 677883390 903991439 563211734 937979776 588582944 750857335 895378428 943826785 527016071 602472765 821834746 835159544 91536739 587038641 268174817 304684054 43499231 460777806 866079403 983291257 964452152 981684458 49157990 655878387 978396789 984189063 813562594 927848272 816817600 980287407 134486405 230865430 186170466 805776995 187317612 843086404 27102523 954006216 842980674 979911435 715633039 978745578 472844697 824253678 690126392 758502221 899214413 982126800 591487164 816984105 248756939 748534298 577707043 799181294 709341893 984411327 738728072 938473669 433420768 681412155 364914557 880977436 199631041 738494513 798557445 970621498 199233880 316163701 92492346 404456292 127992685 215705261 692691066 742588155 945029404 951209966 245117273 579574330 478601566 783650697 912324480 940863376 364129632 890561522 595631681 795724335 668054669 720889393 164910515 427232470 548743732 611908359 665206806 876727204 641988500 696858493 620300754 739754331 90136605 299228277 760292975 787376930 671116006 806719549 750886216 845385689 453745005 618780823 798583905 800049716 844138129 883520623 370843648 960382487 253286137 299360025 884482892 950219716 17593258 774744400 292005293 552697592 312839522 713851103 287233229 490364976 38451391 732072699 937118297 944624166 438603250 952301076 477531146 667287691 502184524 970110250 697141420 857797021 778039218 889740164 811323636 851098931 714269435 936285903 673499469 685287592 726862791 736419265 914510373 925971533 117601701 948757788 427206501 829390516 790412473 815406741 778624886 786636192 847554061 965346643 342067463 468940434 127244773 458859449 627879568 785513110 151186304 622927327 1587293 78334153 505991383 720391959 913713771 981046885 685117450 996324347 796153708 964465495 906443939 918818671 119908343 390921984 465904269 575109085 270641390 743809106 718319374 839948132 252634089 701141548 233721260 606318290 563454705 903585842 517353507 698750481 715045404 850681406 339836848 988587751 593695853 979785631 523557742 907799039 410590478 725797068 971239234 995971653 856530714 992495331 9231531 831413242 491956301 738705144 947286374 973009346 850541852 875532912 528488953 927119780 69396664 980713298 182123195 663330974 673313463 805690621 934369033 974178704 968466273 981806927 394202124 679069200 8147659 700278021 214450366 885669167 31070484 648782019 914437836 981680297 375143734 927376787 656863532 996179728 657129569 723281967 697433695 917517540 102484385 435201500 93159695 972923060 757278076 998952476 848879714 934104669 692190075 773709274 829057062 891527263 654050788 696561694 370532577 843415865 43145074 638521560 166129615 907360125 130996856 139547180 587346347 744482609 861072799 928338907 328056759 343942869 754187233 969152743 498481960 971908060 326603009 997635942 691915221 724406364 414361986 930906994 554370236 691637121 103434456 782658218 807129844 819551502 806342695 839704735 110367398 959806677 669228704 773296575 650920006 974833200 432390133 556066874 672657337 775161078 526045922 913569835 345262529 980365125 36773945 926851442 554485097 917637552 342856244 426049961 842216528 965439745 955627353 973371947 599185003 880389770 890606762 960429815 143976755 427348840 761854331 994133557 492698073 590382657 189611850 892420564 604283482 787790252 43376825 187340223 868473996 976776729 416529575 905906409 588501890 821571293 733595479 789307344 770784438 866739143 623186742 809971941 496483701 950368391 424526674 953195610 701582229 862229965 588416455 866586442 986010809 994503401 27151097 247474998 549050415 661143360 695734436 789372127 354753741 743798842 731030578 885003072 149312893 190861429 936176715 983287003 328703673 340186926 490307224 597241639 444262463 897272347 800369186 974041273 717620022 744227584 851345794 856486253 539749155 789537067 855185778 876222255 534347799 924802592 697650138 721836166 790746505 856833033 603292679 954786740 153033496 562472489 738524560 995969300 793645854 880397460 940282534 967746411 236391785 319645788 726483101 919932087 312833841 500878415 341812030 569537123 28113475 173906611 694688428 890295352 504589893 868163168 180290580 550197773 836543114 890860894 182682055 344977067 437876756 616109865 850698204 907098498 440156457 727403380 626035246 810158748 447820695 682497337 627272332 954920105 424924753 623294445 95005802 443458392 179235059 924804215 1 473149309 997494551 999498696 545603813 643799359 371224022 763829097 977247680 977885032 958647991 972471587 455672695 631351855 859069855 972933525 740418861 980185039 713084920 979202207 307328088 468371134 253277268 341283254 51576709 568486384 71179381 750038553 255551296 843041236 462491409 529721922 88784111 759090253 527568320 611166975 345681124 777180370 552128396 613322654 538361628 981432594 778167117 887793696 704819328 854156758 477774222 631872283 87622508 318184402 205845790 544618831 512314060 653374697 125145697 497222140 851703174 996665871 771763373 935756479 886463197 917624201 518297574 677530483 181372693 581740048 143934500 949181319 189896294 240395081 167400802 248781559 971580961 997055286 572677358 988286780 910665747 945771787 520286978 819261797 204096760 260026868 701655789 780967812 814859716 827952039 76757800 470690520 831970872 967437000 791209508 996662169 992372473 993601301 34095920 141077861 322565336 729861276 428176450 516695837 771456011 852939487 972033404 972564585 389005617 673674969 949616914 992462030 864744573 898293929 759052307 804479598 88552580 857805307 919837828 984696967 793308598 898892156 221030226 816845690 130098067 622945241 231380087 688448394 986229700 995724632 124548047 535731868 802513078 909040309 697426520 993316104 848489037 973128750 788814611 989819393 41662487 838493480 410720542 569982343 982848752 992382780 785975251 880889923 777757987 832851657 632954661 949855977 86931004 894663988 113119147 393976083 22724528 135223649 678236792 723545343 325488871 764386229 466625949 604498229 220695416 711010888 687017135 744443748 499995791 540162622 329698619 961562373 968303233 992621801 497269473 611236372 92367334 731053903 412926468 923723264 20576505 641106431 91597509 723225233 57915874 530746588 831000612 971497896 869281607 973194452 581060330 695856876 519161562 600411410 69595848 789477086 551074514 729500873 679524585 879893633 157709688 694036542 567690259 767211752 218545055 552373289 78081255 216637742 989772375 992800012 13873868 929634929 907036457 997029880 978295846 981445577 236839269 552548498 880174859 997617958 27390661 125530299 652383276 781855641 738566377 984904640 150439446 417833944 594980351 813989670 121003971 412819424 856834771 921743039 441556496 905972045 247808277 270204855 148604513 817670877 514954666 811639133 415026906 751895456 717710108 821144991 722010637 839909590 905867507 947659126 205077779 222747390 83115476 996280962 746885506 796705720 45159859 538814410 377921819 499267217 760990508 813567531 22854935 450081267 80156887 408567040 328321769 459931121 309234855 806460684 574191837 600625132 608708940 891430768 177523126 566395944 688941206 933524591 243561714 419384351 730227977 934667883 692876413 939718109 891837921 979539366 632400202 727361464 598621911 982548179 384980726 759991703 480176977 547675553 243666375 770176781 64488048 291771814 467960268 656084350 187604998 665646412 351792009 740963997 546213174 657678186 259881134 775097657 819743560 905454088 906079046 936662998 924887697 989587090 756053037 804968468 981466484 981810175 447138379 825234666 561893797 846962163 109266031 407697499 29333918 641041720 596020181 866262588 894970389 960850793 277294044 452197301 224651294 923321969 875247062 924958419 72066493 552716951 38623801 890218388 509403019 768030500 95649702 240441354 265334547 310221553 345267787 773473296 350205268 666209735 499846578 948972900 767882028 833557935 138546986 220334013 269003329 640381149 914921249 977563807 351008967 379447534 635811241 990533413 653601972 912723559 434150350 903118907 869768509 882019917 56740274 642645236 310577314 353849638 484098120 572449487 750079067 929038204 346528260 516366393 353087436 747688832 603194477 759937370 997568747 999305383 897234437 997417435 603565917 789596897 967974739 982370886 677330346 951633349 870963262 932065436 29266165 368170637 636187296 771759297 505614700 794569292 614258909 983998385 286090635 830281916 484105955 720265818 546915842 675090757 372155114 915909517 862182233 898721153 526403540 721488242 390334737 949917385 391391682 932595372 821245026 857442894 836824158 863725488 690982345 740631029 826380119 928728340 104090747 190710278 107145794 230846995 559461950 678626847 67942768 129682883 996484092 999084702 742956573 748242021 649750569 890307824 663670033 816281098 315522941 341632863 935097596 989032456 183725717 327037266 668869469 916980737 804114070 985654817 858062939 924940328 986628733 997882520 928647659 934711630 399900406 803017885 636716835 734866337 689281348 709004621 340008453 660370433 206591680 843909664 602367923 755271565 630591694 913963250 228188514 290556979 881241157 979045168 715323178 889051076 104661219 369497912 759907738 864737512 460046666 921691929 433222265 442903476 522213249 962252857 65979121 179231518 324274574 782480857 798624563 996305839 971014456 977293132 127651286 312649643 460839454 585847997 218761241 491770968 917323950 950601493 382048808 867045525 154391934 351547240 928816066 929862816 89866985 187576508 247010972 962801455 86776689 849993056 895010605 950236796 632267168 791670635 249449084 268398283 176426892 267745780 903132768 982274357 640834554 927782910 431258414 915609502 645344412 761278430 287065632 706160629 9499575 434793265 272921883 782483627 456790040 580195209 735032849 810319555 940188596 991522940 607119234 650075100 233733574 250651518 350929532 635393358 125104149 967018393 217506051 867680875 309184770 586205590 983560083 998268092 437241306 456305004 541623542 712031417 280830612 983983815 426839436 649146127 725524701 899304195 859021276 863037869 427583153 855987097 84640270 268807127 881913929 896542417 785517066 862178150 424832233 691469619 385991222 556107719 873057543 955640438 25088448 823805627 117241577 967937206 179228195 230104202 106102718 645071691 469085972 626332576 933966513 934412699 915252505 948894125 570034458 852200594 922634867 929930919 435987527 515783091 656070673 938315413 483829299 942460019 678199827 773744254 59957962 583334836 138903408 354976945 164269610 628891887 75437645 556547704 406775529 904895181 381711592 944609560 567076364 793891316 115596445 453896498 886897574 902428924 131043835 539171803 810969385 873214827 1 825853419 191882968 819368138 294979253 732124320 351251462 446840086 687998145 742608428 694892117 770175782 642215742 807906820 372702186 787150430 705007457 724805958 128475124 299467899 87676878 666909457 126791105 451849636 982892860 982975505 743037506 774471193 728327653 942998746 980161887 983617567 496774143 599046020 174585860 925866383 158716706 518827463 975894204 986511300 415157426 771410827 330755536 505930206 873318430 909571016 854931342 971079234 460939912 891689123 888556974 926370057 254359501 757272032 732374691 818138087 909190081 915236091 415137566 550825460 621970656 881036160 135941880 260556048 195261401 236510123 134597048 360398615 329374777 455084509 142741027 231811298 131589850 260167789 98006867 551908888 723140706 994317830 691744817 889629525 847403005 865648626 319635941 685617498 6950839 298513767 938300288 995222875 586367992 751909068 74904297 894889483 912929592 955837955 66226797 958389588 469772688 749813109 764263257 938554830 354288001 867731874 998681502 999814745 306321650 596653897 2004989 766687398 1 272203644 162469546 987056553 189964722 446194998 1 480700023 161506149 191747351 773116170 833922360 14383059 585036273 400707832 713322806 788937092 860043965 29239326 59523739 150252429 760759026 861767587 903143748 805109866 848154917 841563993 915596184 406383376 791805637 894350723 963720488 886072883 969293064 655498141 689027388 708880822 751637671 731765162 967899277 368796893 701104854 531321061 772980070 983902310 988830811 538201997 842455398 697705485 836145819 503523161 927605978 964950266 976761430 362865768 466124419 884139533 895924324 657694070 702526948 1 993914995 552079438 911728980 680849019 692948779 956555729 976352510 880588066 905753383 324719701 630119123 366890249 703751275 759644852 862645147 701384695 888434699 117083790 169262305 178475400 561641626 263295951 812908672 1 969515290 301601802 349352023 102537693 738279041 700645746 841554825 197575154 334601160 105477172 622675288 944263606 971395761 504528997 815466053 636329005 682060248 289624204 829066039 244313263 811451079 593896385 945407948 468353668 717044561 819063884 826147709 81262901 886610455 952228732 986336667 838282462 982005681 1 691857187 298350431 817560824 563517082 918044516 325744570 879960595 831177563 960477377 466482267 516268030 257932419 511128100 736779801 895806530 790090797 913866495 339172997 946154920 828798053 847018224 782986841 962809608 553007822 847623167 58148319 85606189 563802678 633348609 298465528 765082292 240580953 644913830 380286607 442665374 266877628 904632400 97889453 796464692 629822814 704074669 581881918 881848884 485667382 803747929 1 545033001 931810425 991994659 536827400 838649390 4359487 359159766 107180552 816657787 952800794 964376627 65925086 917493396 953457110 973155771 698831049 781279672 540241995 738035990 338073044 979464684 345844450 967785264 751968742 857132599 882159667 982223278 348399014 797515200 335015440 925435104 114702578 840888947 378021079 720241534 36148510 745802372 579839929 627758326 907812203 957832897 717957606 842387010 770418407 817482787 604547717 783948481 120637305 959543200 554827298 713875099 249135188 731316271 668919018 862859280 912564306 982706411 604658996 998102323 941943748 991578104 696871249 808452475 656548118 657940158 857930500 963519077 197895943 877328232 692056624 736901214 136521097 585306501 488992005 921483379 312661717 601738967 673408800 717162034 624768947 711690742 778476160 839287390 185333483 386104584 21985987 751431176 933065368 937542163 667819156 729860586 69605368 848267336 370159362 659515827 804232600 965918590 227895466 354944587 597191690 915725873 41313872 880724645 773519820 861529615 507131546 723775517 189008032 334549324 217145182 417002670 491022943 538519323 670827835 826336352 12524756 688499334 311959440 842773175 835422347 934691843 954175642 955112796 450401590 525728623 270158306 409016640 191956003 692563231 207550938 376209905 687496445 882791000 846985589 984293612 760874717 829422011 235161541 819352789 769247220 936714137 405461109 589487137 410749493 852491874 959144282 964937236 790453132 867349244 899457466 972183022 297359696 721655396 807064652 851801029 523101327 565654964 530847378 884419965 587082079 848187999 14294137 744808127 297201767 531801000 983901715 997130188 912793325 944319098 183265459 357817202 137538295 977512370 569247945 956141866 181614781 342267794 535425602 688591327 199703407 818922582 729325744 817328654 205713959 638463256 867302639 980589842 745451553 999280170 208984706 290520025 825242020 874706617 920109657 994767150 194348440 360827095 819370123 982276278 359329264 426213312 490894805 700651038 58031805 968294152 733385530 995792789 496225332 617533573 708723546 793913719 239713096 552578155 613841801 728386808 627299721 749030576 107890668 406716371 847159685 898102531 380419640 531068675 759391749 813650465 14073378 673794442 37035614 225752853 176207315 499483065 751952054 785437738 343596454 591701950 773155226 920364751 853738310 872514120 66692686 441823298 884141514 980312815 164544910 541738304 550848418 760493114 144344980 442353930 917769536 991903532 14278883 808933303 1882017 834656559 635646599 683732667 979058529 982292667 252871641 686529487 248480338 680726045 793217927 868860332 37333851 993913871 646206960 671360288 860804167 947298487 784584347 873467562 583465309 961359984 845714322 895103589 686997946 867798134 257666265 408408218 653946179 769660975 994654516 994868512 757954427 914609044 369969032 662515388 745606242 885619644 13351303 233342992 782268591 819799997 43905334 294499138 116206209 241109171 374751325 484190784 792312010 865726933 974955640 976758111 756921144 951694534 67161048 361260977 610462686 806412259 776293490 781605850 565108393 675175761 570824679 828683745 23561191 760157756 865230994 934290751 615088013 764068283 364732569 376227163 334122433 347002639 249391724 851314030 932172582 952072190 277219641 389158629 364823428 413714728 816058692 961944937 447623782 897750495 817538345 930559834 282070287 920810884 819137189 875485418 977976432 996427644 966125192 968531380 215514629 275722348 265339775 664772710 490675524 581401831 517650562 803571825 117566606 996397524 32586161 58500961 239735405 240113104 610488934 768941407 597862487 744478662 233569688 947040334 579811368 671922441 706976759 825908153 267767489 327676759 451864911 853802441 651800160 883340885 222526256 381287388 336985990 898685764 142163336 377957534 155062920 293628063 348193683 359301408 335822412 881233416 817347143 996468567 982110459 991470260 465762309 508785736 823126646 841103509 616924602 893230247 165141211 443163130 847897237 868258310 694802210 965753752 625492009 737703907 238015550 856139088 206080128 821579812 196363918 651009365 573260588 854090517 878491011 945490255 665821606 841932533 190160296 599123482 59027303 115912353 670580864 784083685 847471421 982037743 335376889 445861278 923419348 925938082 770738563 962816915 676818634 763517964 35082333 659303935 455945479 640834405 946348541 992603280 942136076 959401006 378770672 857108281 303095009 559879800 184523251 330237347 230797460 966092813 418882825 928513822 215624516 539405952 407456197 671760672 11975648 494029360 321410325 749537474 614652902 712846884 554648969 793263431 585833732 720623798 670588698 700965163 857066528 989359494 682149837 915647571 664717306 935542749 493879 945659443 277880821 344397728 264020839 389516980 461658952 505055120 94116624 278926570 37413430 170305525 971717018 974731473 609889729 920785806 262072838 619478730 434464711 783954271 462629774 783343151 471629057 949089540 842817868 949799586 376124957 993260635 19767090 973081478 657601755 897387083 66237974 947990726 221250316 240655573 564849974 991578453 110248994 514141691 331625164 936777643 898928192 933183044 793527138 802545952 242280431 258159665 304496047 998858942 672451451 974239764 189441979 774340906 804820148 984237217 75121400 582979700 394966749 987342143 504614599 687850535 355960158 395664763 347197933 796831084 440056147 997912912 163944551 757111146 372231190 893199203 269275404 363429818 740555402 789405447 467367235 706414503 680439153 787237533 748078337 800857092 159360365 305699341 365588675 627378818 795892898 810537734 129133041 697841693 497883079 800461500 100643819 361718443 347546432 370342955 642097420 898716041 205441972 518816983 592558146 707865823 602166073 627145766 209820721 501349981 502129653 904408899 899184426 983915557 373667165 612249138 396647202 652997171 95881543 434893188 157754312 628275349 132047422 406526998 77640243 521520267 932571869 993905684 783686021 984738948 136643228 499212540 320740932 764103523 357271207 779026644 330874023 863998229 776945663 904083088 313405759 833181634 734033533 983572150 751495189 878169593 595637245 989714922 324145650 686884263 314514527 814428694 285916469 806583064 867351474 988491245 608583001 711226422 450219156 848367126 993094233 996088975 408330396 608576439 564636794 709146304 7060804 447760063 954814155 994248200 602475702 962427969 219192163 967800006 33147772 935668703 713585852 755334170 915641180 989901793 343288455 515345427 645586362 816213318 999206681 999401506 263923997 990668505 189440520 621004478 604228627 875711730 545035048 699885033 352951144 826459397 617276848 795893138 472163778 783708121 643650733 964942746 480654999 539670874 618229049 931784863 392986513 472061788 511370147 812957693 150638494 362072330 647819265 684829071 768768775 880609123 561915185 620784084 127408914 974474559 164502221 748311797 733481222 776911972 801199369 942666510 252208818 311356060 207746408 443313298 205935761 950301567 331934192 385893295 596175623 993344893 131123631 457844510 420680403 831732946 545637363 644643042 436364886 669010831 738699645 795886398 32730760 911798450 753265538 966489628 702737881 923973639 341902542 687633842 495336320 537054069 266920298 529774027 119839254 970355952 898856837 999037429 822026573 965328186 45251518 826132682 285032870 347231195 941639344 988471143 980458339 992715366 569477924 969241709 647352419 763711230 303291951 455872667 606730021 666741329 642407784 653269256 774643060 775870874 152370503 910761478 415530195 958187313 245672141 415249002 138985776 365501453 39547078 874518375 488668251 855851762 311167588 685669985 377286854 495006993 407839537 690497477 799337033 905755340 951852947 963335731 936069469 986080459 949908686 961175894 559819662 888235254 755521839 934863397 42272317 240377759 198796014 934376570 849690112 980329234 388467747 761109317 230271760 915751462 30804917 958856212 29898628 116149266 196660747 502495011 704297378 934964896 642705253 762647860 822546320 949120649 720182097 802444989 31916654 826256160 640589499 814278703 145048369 283270923 828174692 908427480 781418095 897916206 625503965 837853255 795967955 998789925 619902748 761391539 87627867 402103624 276471733 376853357 349392919 800951276 286317793 719645290 439991368 869936955 822141285 891033367 999298451 999824575 553107003 764103277 796490429 931481322 657046038 933577810 159006392 695231171 575556311 925272877 608141154 942969510 257469541 820680098 596282309 749039411 147499783 980332123 914064949 934288475 584341062 724440485 418284153 616633735 291332040 886370086 892457187 933739376 263175310 457798632 524895582 892853990 632478482 910123553 929253446 945940136 899864841 962461918 478664063 742579946 669880809 904550435 460677327 810131919 485696990 827163563 184422641 993594117 762789162 813286484 344170200 569025324 123559181 563260661 911355 606567048 425537211 583695200 525487487 664598034 780825176 995568420 283089996 475202686 874486010 902854228 940272271 943653329 152308101 262608294 1 899057967 43992535 808171335 209376530 930171256 326911351 569457772 705043918 939986993 727859163 748297237 623184122 971801530 588611178 959425385 221777179 601804973 966481664 967601038 584265026 779354049 844568738 871704263 888455482 975939095 869634273 913692064 370014832 439457537 786972457 790479306 332785812 818941843 883110300 959386661 351762949 612060083 865744834 914295664 795418170 981555109 212325315 678480122 275155716 921678495 994642315 997791184 928504947 930766486 448536453 811623396 106466449 617675745 134702401 144993882 783193432 986243140 600874037 666597929 445953758 779129513 324160869 624769831 1 174588732 67209686 776053597 715165234 874023291 604752384 728325010 231368886 809284795 873730292 991531791 177993962 728115118 948723422 998941190 353417853 443128411 927791136 945663296 855400684 900254763 888568123 930668524 755049223 951445441 673191502 907738744 966969754 969831803 733453832 836971348 487334697 968661083 77845298 785058592 473947887 815066368 993857595 996686848 322134074 656234550 642840886 709100133 1 139999627 89536295 300500193 128991505 134025503 444490871 722370414 199068008 779163159 289298451 742470128 273167840 984546122 196509184 436112051 225474234 725271915 355637062 917605148 461600721 929259070 203333029 569493961 293403174 432204430 601290563 903111858 122143683 849363342 726492194 760034489 867048623 966146462 675389736 839693466 313792664 522301208 115020406 151863423 239716778 741744293 500341109 972713156 679568405 821287822 654900178 968826114 272806197 552461139 574008042 854522331 962539482 973251905 368873870 959699595 489275747 776491289 259149056 594292926 770958853 876214868 999493476 999769307 588412658 972593568 102903391 561276854 275147760 450767779 811539382 830085853 550757045 918451250 559570697 694825084 257188688 472812518 498203034 677124405 771171887 847617052 970237696 981168841 981701567 993471775 563666882 637532100 46765874 614048989 394341876 826561506 79682729 734668631 419333857 885112844 120111161 168519931 797649968 968581182 418172789 534552329 883808442 916749664 895586485 999307490 322348895 742971672 510806749 774351350 349068000 501596707 1733393 150585592 931943912 962411817 280273166 540848710 25644674 651428270 952126333 966213973 705176121 956396024 586842600 763513974 370129176 758641272 139122034 899133480 781169746 972151886 177219760 711359863 829311034 907527724 283947518 799595957 758552315 809111854 905766207 919385844 246573039 271131527 360250062 897489984 811645276 883327314 603012910 865528088 807642683 907472915 928364390 971120331 907405079 975325896 417250543 960834893 854068994 989174100 903629787 973956693 310892196 935428226 304177523 388887481 212797510 295874280 154603035 671245106 268748225 918020195 526127292 623484064 351702703 955825829 5942126 698916972 501737151 907111535 819512283 890109484 549761992 957673232 698384392 916716289 466345967 493871697 700901153 813529576 468124604 694299455 811785836 914729735 559158021 790587608 871366310 880863394 595495335 671540826 537875932 791828211 206498752 569688265 877141954 944199014 678808094 702434210 512933782 849635092 265571148 618531662 406851743 613972234 669636695 828610949 491243542 677650866 880988588 927857460 960038283 989899093 600294262 941570638 83507567 567912204 752352936 947516175 155374799 978628547 447174351 463638690 412361787 427677935 556834629 769062699 674659986 922695425 655565808 722383061 437967165 843753732 113263334 353378244 46487224 968268382 140880189 811173046 119916995 712028979 508034612 737870144 949710090 971908535 500352666 949644974 655703842 824765428 196212144 769857729 462080827 659341212 226704984 634507691 207857987 686898441 531323076 640298928 714704679 967571896 36421561 291696443 409435670 957261878 496149052 567943556 291579653 521824728 711130651 774666328 138950120 475896972 382687891 625437247 784046566 882422883 205569122 464256695 919454381 992578934 644588327 671844219 400031387 739291850 759033763 773595078 731134920 965933784 444206170 664100569 687691418 783946940 388414681 465510117 803834984 907666297 585350292 977098334 125020364 263105877 350011424 498244059 959653063 987947036 594715367 847393343 277779430 689974595 141051669 945513030 80757156 145530472 210931323 348519655 175064450 431976590 666645005 899177915 159206138 763336570 303494436 846363614 515850806 907218694 110375001 524899064 221561168 465875954 462004892 691294887 181420878 713800498 323217425 426390199 405682948 826949771 700523169 826339528 638124130 781913525 752745242 906762168 775202685 823348474 279360691 887294883 984400244 988452174 439906900 641944516 1 259112370 558152935 999447977 885900003 919157034 660662569 963297594 592125396 887630272 476397204 771165275 774715295 973610237 257233212 621632758 384969044 897577167 8876659 689605411 353450300 495738600 708881390 777047200 456967386 600549652 650167331 926808602 942666233 965502933 271634647 901703006 564221778 878610516 99578102 452359771 692968185 934948491 498301482 823455210 892511605 975108106 444227416 596401866 784025132 897833543 1 582200124 325515610 642161505 40157101 644015715 812537000 861732094 741946069 773017116 22007903 801215033 365539922 388193210 706792565 801678531 296540554 782082196 938865578 980593662 427904790 961032007 357499555 382469183 203163430 588729293 871967282 966620257 201177566 591908756 61007275 523425537 822183270 942254231 637871067 978745500 450663202 593827809 382022783 632571961 182375543 681996748 270967888 597146351 840202820 927079691 613336246 939052776 748538933 982533474 398262013 822205086 593006047 784409546 541572501 814518885 818034340 847899814 359397191 509705904 303823696 699465195 819944527 937395911 319558992 763088606 77760398 385647573 495241733 738484846 956029250 978402299 610325852 804642707 141301207 439140267 613991700 776624504 362666843 682639384 353094163 903112432 464992482 467948598 781486529 960810592 811309914 920095174 211502228 948802590 782805802 908165405 738890212 850869895 996627867 998448243 145768032 623352907 105029276 638621943 356667033 857204912 507606087 859555149 544462405 691135707 507817705 766807513 796730486 885451184 177505673 924672171 15126722 861721481 596828048 847824009 609513173 703741284 346650331 932694456 249789394 894889151 105491222 479672104 632107766 821063122 356766867 877754732 440247242 826886236 484382210 947954672 734233523 840792800 593755927 684017759 508521441 625031558 304601693 923086517 726040663 925945139 460285452 628163555 844157563 974406245 259249788 363126573 323974261 518951881 256674924 633272204 95048383 696615020 322036785 451899461 716243091 868023295 727085421 948978674 819838787 888821771 657317588 713198245 436420041 982228074 382550048 708619895 9666539 823788858 238319488 412621568 865467255 877247475 74376085 978088191 349382604 686791503 125700238 520928685 349313670 949052997 652662885 699364387 900845298 920041123 587110883 760966355 60080699 416831006 155101677 225616167 854998070 981973610 723707509 765193699 533578260 993011272 699467703 887418732 81618215 822414887 516079414 617040421 989084809 998238613 46218230 271342333 805016800 868235750 846295079 888365328 50966475 425378796 567857707 710266795 791599804 910759522 878958719 991495948 492569021 746223992 936734279 966529167 732971558 918904578 124879798 903390362 611169656 614638462 9406886 363759203 403343457 633058596 565481749 751074416 286236135 405863882 709948995 991982823 910247472 957038263 3533662 231850407 352642288 484248772 104770494 998825735 706236168 774694922 204053653 453799101 495975445 901996602 67069629 653395980 703283776 924536988 232941753 585506543 40478812 441041953 353855442 838088145 648517639 925283036 314995066 315691238 23004050 927209301 391833263 394664293 884561871 903608057 867719773 888278836 846592759 936103913 413788328 687840510 294552931 790519065 251212918 694978620 548681099 973835037 287105153 341069382 716821100 941979867 753124393 978683137 419966541 811788302 697742838 970966251 953871253 984974010 856444333 969106227 938192364 992178102 681109968 761948671 606640029 618424606 226649809 571079238 650452545 797803492 935755191 969484640 338956391 866047743 709743829 761943808 557955461 770668990 570571579 983115930 300351923 778020834 186549563 625546032 732287565 951887285 46980521 917545321 117666091 214150910 904179530 991477892 423260046 942453384 745201072 776386476 661451023 715999360 735340996 895202245 91894849 205310959 258686207 772161628 586095018 987539169 243744891 492354827 221829840 864013065 786666576 841241955 65852490 369971961 231526658 965908326 587578689 992519718 509166531 668256727 79440994 249913494 347130927 651342874 388040183 490918234 52679763 265333945 448253320 694534303 612153697 768738818 982783092 993219068 561062001 750275996 984443063 999991672 164720156 698749688 117815587 523676589 111175697 647428897 955781094 991747430 309843531 577695366 43926364 935629718 418112199 862441721 215244278 758219591 495017324 496469706 103690640 305668086 6717687 267992895 688275765 728772432 513494639 669299496 805699507 985730818 832994562 873668293 91212821 816130915 227185598 897598355 215744410 498478607 613318079 779320946 270492517 663508588 868140852 983318300 395968311 705363724 257063400 331618818 783313049 898514842 799770510 888196368 179786081 355323267 641058117 996372631 672802918 985357131 117018538 966894710 565504899 708176396 124926082 905094212 760206427 838469118 626970203 768064781 450478590 824127016 163549909 642754535 871939788 994287693 1129010 965482348 331389072 942028861 420476552 876704282 915194953 935429191 173832132 649902039 732813631 979099297 372035053 998911929 501853424 938420473 555619113 835619493 851284815 920420450 791429000 840708431 1 785165931 434943931 573309890 120922941 577262933 579544178 919992331 50077999 695554162 903978140 979986954 213216290 743596844 689837544 916373894 229426627 610558632 48787955 875225760 819517451 945665847 575088715 583249844 38179892 153905753 645512239 676101481 925073580 972989378 603787489 609935030 874965928 966019836 134375721 857404328 803549474 910518651 843188260 941812173 69193098 124176766 166125233 737724888 307519256 742961131 1 516727299 227578677 442040512 952398640 986251684 127653295 411750752 728928442 985855208 279051507 631186724 548349998 752904476 747227158 919611152 872151170 995279393 735313940 751137951 113460676 883930567 564942482 952588379 403955478 810725604 708697244 755080066 518006622 834490748 510294596 703170743 673429680 990580476 606154917 638606914 1 287717563 611478350 971788841 395660943 884602366 378297164 843050957 288429155 307636826 323517448 941682409 372230934 924849857 153725473 465287320 458496057 840053137 993842686 998935145 166180578 668926174 307777368 447610052 242223441 818307968 811376644 893605823 78242919 671678896 306039450 540300093 355864586 508926131 964638140 996841133 452065058 924834613 827932240 857309938 1236850 342207776 409546824 570546646 875221540 963111882 168416314 246432742 299526227 881709869 644091856 795303165 414852915 661736111 71623806 616820985 74626488 453106828 536776885 789981529 153431738 493368186 411356678 782634710 277517990 540603158 361855130 882433252 699235603 972804921 11027373 705921749 839569254 879687684 572000379 981042033 359460018 740056207 514485007 554959502 527350255 589110459 535614967 745718670 183763355 962573671 85845782 734913645 390033119 614464009 178978981 716880575 46107489 832203042 126314941 573033947 570330148 963218498 912208918 977714250 126571030 522290037 567604197 923368425 699533206 862771080 671037817 857472523 253486017 431629218 21851161 92492163 666321132 914769009 672863247 895959603 485782820 510153257 367457595 393807563 594186702 728078936 552216436 578078580 668772299 914368681 521561604 932101960 41787583 796564419 433869095 641121158 125135017 351274837 702343271 840109397 946628534 954373413 1 867258524 216114032 653981506 469472366 598406450 160626200 806277898 594725538 633165319 258228551 948208675 442751012 549382756 946639014 984390428 908631894 910986094 615627165 701448397 948250795 973948769 442513128 662019551 967426169 980169988 398892653 408777410 337031370 635485752 673212507 848282097 990080330 994533696 537580098 838943868 303886046 836607514 1 556274416 196572617 484944204 864638793 922654267 947931509 963375389 93837081 739290554 19488141 869906282 531584458 577932662 632783370 992591491 547119589 921821131 244892887 261326857 48824506 328726119 433442505 621798811 403851109 628503195 777205546 995298042 905113403 934393358 995161967 998110502 671568426 927504892 933253579 981113190 915088286 991176536 649233829 913536649 748719380 946183823 505352493 710739095 442855068 464321680 425329426 483840583 182700588 892383697 804378916 962751101 25154098 215452198 719451823 783334593 903213024 992575428 519713764 798908867 516281696 998060993 608918644 707133028 55390683 709057483 155705121 718298573 961263765 963240049 550336462 953735400 677718536 798214607 698797233 758595381 756105529 766175709 463799583 553537127 891677200 899522356 57780633 407571282 858716756 957624467 359804787 930237467 638425060 856272460 176729440 385815655 64508459 249568135 480915274 781130185 474794242 817406254 271086350 450014485 606659736 830934848 52030323 230030968 446617306 587781721 866199160 890951059 606755165 995095832 795040648 965613899 913546219 960225343 869970601 926316193 861645816 978587754 137411379 247599079 83950468 179038335 926606997 952904233 878671294 946561286 341851238 440077519 190314558 795191731 540438335 601413270 411338488 720366763 874099175 881904482 723781868 779504936 465115869 744824483 171755542 444345139 580962238 904731457 749437789 759155900 961294115 993452044 991910714 998236595 181493911 350835462 199066540 794300412 640529634 742867175 237137311 573106168 1 691280690 139138032 519143718 339537870 907671613 554163958 747445882 223197134 485271438 798799063 817542440 657368260 927301337 898069374 918391706 706533778 712493979 776617447 912143122 181300255 435165093 789191596 857643638 140146261 846274576 122575747 989365617 166239252 574822055 313724173 952385038 586919473 905163273 312898942 483888191 90079948 771476889 494501168 827949011 129614268 490483859 454756902 790268809 411639422 751510654 580683172 791363996 651746389 935891661 856229706 977625494 68607190 867055627 813397257 974669100 419342424 932582051 713022517 876141293 600218245 777423110 859724608 918246509 359530078 769154635 540523884 648742043 215892973 256713103 960902064 990996331 627984129 731571658 30065843 672282217 305804289 478939702 74464301 353229007 637383237 730744286 308373562 990012704 885022365 885138650 907522308 987328872 141696538 483860850 821503526 914373932 177326924 530036336 414238279 562476915 164261740 768955887 912001517 992689445 665440323 728086900 35071681 455720152 842192490 924705011 214463698 776005331 526897774 687837682 902690894 950924808 424376196 482327807 878366550 911637902 88281229 961705255 21997263 982615067 142973345 308539868 793909266 849005695 849626900 975457429 406483613 441987624 423505466 564107184 638163016 702050799 419077563 607850798 491248958 635149503 945585736 983267305 892449627 989602501 510455941 529957912 521566370 921692759 784789550 896452529 622453998 639770955 203207959 498747616 283868253 921371316 832784536 847868768 579261757 635009485 621355064 738335959 317709963 382155256 69561214 423938018 575808823 999877229 556365828 560593110 421961512 498048041 440859076 541393035 409815722 831539994 241966208 404775393 306152637 612377456 176664378 846457386 668522229 875140879 699106566 782705710 248076983 890271846 719933628 860078796 127622554 904306362 953394571 983122397 576636421 590790072 757832478 899104787 159673686 764595756 751074688 790360586 430683457 456323264 338310625 825529984 262072930 757578635 411664109 655217784 476743538 811370056 541255005 711666491 889580565 993319129 171620485 986709779 905983958 960333639 472051690 849446324 240618566 355356489 605222611 800921701 312119951 554654363 101982921 511360368 665814292 676247509 977452781 978255865 158532847 296653388 818419300 910889748 153705884 870762719 267899929 304123556 260538848 290403921 575716436 839128945 182270103 678340330 201319464 275699208 971101102 973169406 970793444 971336008 997343245 999270076 781805422 925856403 589903357 797732423 859887681 974886194 581610354 716548723 170197853 639226054 813697784 819716022 178075571 625851441 441491811 687171906 572528230 710903770 223963633 358338852 781416599 897821552 953237371 964506151 976343841 983449999 521687552 970449864 817644338 907260103 767940354 986567860 903884509 993865187 444835967 635120074 253469936 973341672 350331444 847906647 850318150 901416065 543941059 630525503 557986129 768086362 570122692 821540155 255868259 714270954 614834080 893576473 541022896 754484117 136633723 489191191 9118540 451549491 638540937 916590955 416948715 472726519 890805812 951047694 613175462 744041885 812322276 817152174 658402812 991157855 594950872 732014659 628666734 707954313 181513540 240533754 147715197 398145127 719719506 783539337 949543912 980790524 993452679 998363087 86396140 300600787 355576725 840257085 818901493 988763924 745408752 900446236 396184939 581941433 829250898 961581181 591772488 902851745 762052869 925708017 802177119 845629514 672450748 975823887 227473039 365052257 982320546 997023631 527520994 551173888 375949185 521544915 466788745 997829852 944859900 981721872 93936651 821084616 433671001 700546054 794770385 991372856 77786616 845397732 231704672 513521328 661092500 876689206 177229036 877006264 506197693 597403925 304125592 791163406 591060475 688586803 211840040 826392036 863521203 998728123 564560866 905997096 964926061 994899204 909227623 910639800 749236921 990027582 428321657 451531887 130725091 644251754 131365647 957388637 543557595 725685452 470642848 481196436 659780630 829737158 863981295 885862572 456149364 787011304 528524240 884593605 504064225 611801440 468827489 558804810 252055191 894508915 127066431 423489292 904691208 936211310 2695708 728956335 317317643 610241181 65979300 440999315 723442891 977839267 162211281 385361873 98502147 225933256 579252234 979525389 289945441 534364229 166730626 632834475 386284581 823885413 707884505 873977728 733672658 990726889 312867776 839338154 572182163 964309704 193718389 960863574 402039393 722929828 139551712 990303603 702241664 755842684 667333005 712247213 854419684 939791396 555982257 985364948 736211230 833929894 719383965 803422866 12477698 577717959 946618296 948134977 220137761 457646890 837034553 967510748 208446960 765741789 29636587 653217659 87172830 107238400 566327635 610780868 439175273 980677847 394124583 582531910 362480638 460597324 210230161 214225844 144229395 173328958 40050502 581525858 472813175 538362352 899970059 985585278 96118978 951854464 638500956 646898942 866324527 978011496 166714092 754765720 110007332 259022143 506330297 850164364 913008137 930569822 368608338 940727365 609060917 792017713 811386124 871535461 756938565 930821520 644717377 847313643 62827483 257117974 414209178 921389355 910077678 999236742 2410682 313672133 233200168 717965581 140019971 970602811 890406462 904613647 989421542 994440049 348895450 637349436 489127387 977362716 62152904 557915234 246785150 407999937 837367512 931165533 644762370 707352145 538411525 950450428 397972407 653901778 932058811 960454493 112199561 417038814 784097900 942379965 391171637 406290266 307147061 938788957 552116769 845536189 860008528 969643907 966812099 983854973 581935113 796303164 71960464 242339660 527397007 530976110 47305370 892419348 164000812 792737302 244417228 866718764 345121958 464629412 747497349 797632641 824626463 937444836 56130612 970037645 962274983 963224299 342980775 657128208 954871227 996518628 379009725 412778174 530872006 828485651 452230359 792743386 731992090 905101912 359644050 960255110 367174915 986331037 572901005 817595588 281858629 381174078 277160489 382191957 83724155 573204393 975865447 990062032 822374850 884488810 421714845 511286638 403300320 569767478 499411613 891850860 203382392 382306915 27540666 301905416 607112436 801833306 362118868 902608336 587023572 800534179 109749570 325639178 681909104 687929062 895655067 964480597 860440459 951880121 49919464 76560214 273893499 824460642 485945808 881384389 863087821 933217666 99010219 231166175 89690285 804089946 248670404 393182522 790711152 907037960 862005662 867779076 611987753 818708319 551141199 764456939 865094869 911593292 888597479 989246158 642167583 802270031 502726362 588754987 381935154 439774062 886833936 928702376 715786809 851423507 896331021 902180755 539848685 767811088 335672880 484123309 285022296 603741868 719102853 831371366 859951300 927091721 220360871 606024061 362609487 382107578 131015343 277457327 784917383 798219189 200539890 677504285 911966863 995551834 768029105 823094908 859119408 939771988 380125698 775536841 424446380 819342749 335180588 371567815 517339744 650684657 274095145 766956585 725560225 776698056 5878215 375863469 398152327 826999789 974618781 992595112 39871766 772354642 218773609 777556167 223558300 319426010 46161288 531050864 198993703 244216500 344979176 576083224 657001503 962592757 841329411 980598063 681634841 858357749 479884198 580426124 790172223 792584916 452317150 948936741 822185896 915821804 735224549 756221754 160587765 456453127 306452019 948042927 840936428 980893519 620947618 937098162 151742964 601543458 428336572 504666407 225128178 713982891 555484733 815379168 588868853 674587060 699153955 746328461 95743057 918405747 684208158 748964054 421071320 533266989 645721978 951249266 784176984 943694655 911740216 942100580 631335250 768826852 880101533 935737789 444620586 519863223 996828434 997976026 430449262 813518996 49325415 167594134 868829424 906329841 719658331 929053906 325647267 526916538 316283760 890442692 289617710 361018047 387390369 448660126 732084367 941623092 813469021 893985040 852829675 971122771 1 668307831 298729656 367608124 755273353 863558425 360064100 619968956 170635214 987423980 643808693 841523464 680756193 737347572 756266242 863912307 543284365 922439258 72218085 599203531 747859666 970888004 20666564 505053273 808642288 959227497 220992175 898744023 645303981 765876846 415754608 677651457 701315886 851083548 408551636 423121097 237282525 728349204 725985787 980300797 553773623 803093663 973935236 985358630 286418301 559456691 391891920 523091601 101130842 831061567 956041756 991216196 253228724 511813934 157856735 187956526 445433771 845413002 256446023 482014443 210096740 930158723 337938551 656765182 42751381 470549102 448858851 712091551 181690735 652083169 772418800 919918575 15095538 731264722 109414541 375848558 661747582 969523556 787832015 920236057 690108138 725336928 85810646 801157202 326758206 674612118 707995070 895375069 480783992 893897058 538093118 879161873 943706553 965462558 90119310 360516265 718306441 870663491 146529188 549054819 216705926 280822266 959475455 981284170 910623860 946900480 883067636 996648701 26003142 996059828 163928110 420160576 953888578 986475591 613766550 939530395 430326880 524440267 988657291 991926630 753312435 849815145 533356779 607753618 430959216 845295882 840791332 854180783 687882708 953870250 568732594 600480780 840994076 908087125 665957845 978168170 868219810 876579226 685835455 721573706 38640973 73810700 851752661 870019742 710286581 854386117 356001525 366617353 171523823 615305709 694865946 973908120 689450238 989589965 773687969 916493429 369569873 437009148 597113629 959119238 51598000 253949458 815428141 980677035 965626231 976176572 842839290 908579752 744899384 895272377 412739216 646070717 666858844 880301471 127642800 785902289 328316936 583061050 138062732 510553606 498558880 801369508 752340221 819966982 168365363 770270894 675461567 889851759 773157170 918259550 392992357 866808866 51843449 312894118 404452355 708593461 280202430 843665400 519407173 532129746 177276530 830415249 921492304 954466452 228660267 699387047 913586955 969017346 687087561 893441586 761504556 761914613 860275984 887369866 296108167 515883655 501536156 958198863 36336552 854683699 432628141 749903470 855673828 918180960 990921408 993568132 515478504 614648438 609781600 873319308 237281098 914065993 830383176 924836382 786280317 853905165 295290914 883428126 434943537 829638692 230724535 353653647 260130078 949660403 473753379 951837140 461248995 959983966 256233681 404749509 764227746 787949663 192172207 250098044 725913243 869476937 755826387 775819439 681665877 940927905 402692928 859871430 105268295 852795658 942368852 988642677 616985613 782461246 985936668 986036977 860938329 891999721 679391609 897687167 12197097 470531414 123939103 783242610 133204398 874654655 788001030 863944424 524165943 897091534 164857484 857150839 66771517 781702636 476041799 735068755 812708408 840740095 867778092 910117721 568064375 889095487 743235852 783400138 420353617 988732416 831289698 884777047 698813465 766961872 578088941 686913803 240486090 818722883 19609928 312994703 69653378 684404651 919942111 927199585 690073793 981173541 792474821 817843644 424092855 800295881 187061669 789493733 212776157 728169300 208343030 894693881 592075695 910458993 490999626 941071425 853154031 888629702 84569711 624327594 919342296 960079229 641466399 766271509 701741592 994352925 60868966 658940679 421164201 506502170 228720084 344832218 24057692 392955037 41026152 693667477 105121027 392245423 71089158 993771793 15145471 573527378 41241036 863299739 988497065 998497887 978024948 981018789 575611840 699885262 469088590 500672694 359937949 541911096 609147746 898079071 409464942 887176017 139625771 921257111 606076902 672818068 499683814 813900889 657439088 765122479 252539129 417700525 979772558 989306522 522134994 962166394 641053797 746955905 974246704 980456501 257878679 713906984 54679345 343995493 328923342 698092119 120390073 894635765 5024098 185521345 28631895 422672128 510134334 788058753 337819320 433600121 25772905 222311859 324127924 963426229 381976420 738226273 827102226 959546643 530759262 810940705 629643769 910372417 782765621 908825957 567349512 597083727 715443267 832937283 708672212 818578846 515770571 627572450 771887406 855098817 992798971 999409697 823116071 997479372 652392502 667531506 406564969 956882369 885160466 993051497 214355137 561755448 430685244 761133657 666873887 671259865 418949251 719023635 161565526 927089943 1 489902739 632799896 862183634 900836995 936909279 894642336 909021993 757729782 942845443 545039765 678918332 157411130 538179719 129095710 704651003 250271909 408546758 640603908 988370546 949685509 995726381 889586992 969661916 864190608 939886086 12085501 989761998 778875014 837559603 610457014 780750335 755717092 811856195 229394144 337310074 833102170 903177201 557767772 629628371 641947840 688046402 28153408 752438155 650024460 756683851 739335878 807956596 940324556 963372229 587851768 739373995 653238963 827592966 261711915 522860998 973900769 985887911 541666127 844520894 583117480 666043670 591854987 711662367 1 87974965 924913134 928277430 705010249 851748267 914014455 969822326 696329911 965808150 702785401 902758850 232488787 944661203 485733435 673505498 117641723 134233005 455527537 507500204 326317190 493438558 663563698 737454623 103347695 611963405 200656356 465231038 182150817 498283610 228440485 753864519 530837889 802499089 316190785 596558779 922085819 927581580 673868399 856136416 314388071 816439271 243942160 818205030 991821777 993235876 295767126 819666866 912131153 987649890 575409268 910544518 906169415 917340522 98946269 725336785 880559218 970709143 674605458 908327004 231316551 322304471 736181781 787792938 151237913 261935432 122207766 521869975 345381350 852236524 873523744 942193797 1400827 495791943 485633556 743885831 833255969 999333787 996767625 998340172 612518638 911517779 950319402 964722117 377129834 532860435 376392955 769959214 399750179 656642744 568544134 582377269 398856873 948312278 479005740 968085236 423001911 548396416 218687795 544825564 824262638 990535377 440212869 459615903 9996989 192858061 80681740 777767778 145110720 441355573 554464381 560479477 282429306 954587768 982055428 990108026 282046991 890777475 7057102 146851161 58825555 711819951 966343366 968245838 337675067 640846126 599440050 684578489 942208713 943017114 474894239 971468603 412278413 995818315 890114680 970662177 313885059 400255924 660364522 717883113 336266708 822982134 22858610 609265552 630073728 676788311 966375542 992570365 434999976 677764239 373773520 470497168 280229362 426330141 636941234 932414148 814563091 976612652 171590667 597727662 971001738 986357827 121461906 855197964 453089709 784119414 249477680 818495116 478886225 638558811 39120151 997877273 168301452 379991732 267988394 943729544 284362036 399757434 859788182 995287539 152028173 230923670 709996475 727626907 326900547 947963766 917501684 994581473 241496183 306254296 887845837 902324793 457357514 606261604 590354992 754051517 519890698 579549359 34431478 77339903 546213281 828901184 986439625 991307417 226751246 745789337 405459094 639167770 944964404 954751938 823806590 885397132 372967354 659645798 427470649 540394394 146531058 449264879 326666877 888862543 62672965 671279294 710003424 765125310 813491854 901729907 530850376 897691971 692297467 998630040 383640812 448572913 262369008 486332897 423688178 684128200 656311982 947603967 827163439 980383372 570373808 887545973 777625135 954465585 386289946 429426634 476533496 669029609 697388287 770789648 569629756 756181363 244747422 859761185 295608622 331149668 253088328 971546737 557960988 803114706 74757935 544009373 560360882 707682932 446232434 554912762 675213719 736246599 390218757 426386941 656713539 901022652 440932272 992245026 896554408 914698249 574162365 686574684 792150215 955410902 747541574 824660566 914537059 923775259 683307801 718695512 330673129 485513341 669786992 996342113 501391068 904817132 482014286 535133495 498153429 725175202 940101868 977888685 121757305 455942257 785925391 995322830 491880 921874801 851394804 854813585 128401918 679327741 262622681 919741619 255062772 425464568 613570321 868518366 426595895 751904416 283153700 528453526 963112232 985033159 736009365 870814116 474777551 590782913 249833630 703391703 11794210 365715026 804739535 918633350 904013865 918090600 480639713 529650808 63647055 953139706 637206836 743819475 730897576 911296000 308456508 667979799 591969479 691102711 812005008 823235925 990533604 993548783 327712034 524796323 649782194 720788065 722675196 852022455 883139015 958334857 936536601 953675889 214946168 905029741 410270655 946458014 114427526 875501204 10792335 108532937 289689637 855667792 917231552 998980402 174017484 998392221 781254989 884850146 261968670 815018897 107292351 949912267 835896426 899387240 778118541 880188391 409503200 756708180 664037446 910172456 434887594 864630038 680654833 819005678 192614954 769722313 674002464 861323364 397236035 403881829 621157916 749590512 153227931 714171216 330824237 820041377 897904531 999704451 752205429 773083186 343951519 921366100 34722195 877706612 336051925 645973167 974632459 987603303 681456607 956885112 194865002 470624448 560330254 589607541 962610474 977134598 291036334 663615843 376873987 619884381 759138864 823020887 455198984 512935430 308035933 638865693 322131484 688923333 627964325 868187228 957322393 964401903 399174181 688213576 924546399 929620661 911017231 966931529 561591944 915748338 468527463 711556947 831078550 865151534 1 156780405 856064035 945555145 672241893 819421242 939683765 996333573 866645539 972238404 646563383 734942533 809818066 964834710 2192096 667077260 728393581 874103075 723427422 766941214 13018688 254851721 691818430 816407193 788208202 799797298 953998459 984775345 566156909 864768086 253803387 851216305 983094526 997743739 310182173 375127599 468583333 879565494 831402879 841730294 659218854 964369779 116518132 521073481 569921610 894904454 373921902 768503251 720983817 977556898 505618712 849508932 474648586 714408264 16080276 37628211 16002970 920850815 32295290 838965115 89157067 761887878 466154717 484974794 282111141 902539342 423726848 635482832 311475869 568060160 755422225 986487249 593168708 723046263 778674548 933590040 472451028 910776663 145705525 621002632 291631850 511238440 798321391 941785258 987847644 993817114 625602524 727468248 862949738 894803324 852631563 947868455 247145112 458605425 761794628 938725617 128367626 779586900 519669186 999845302 611276883 911574670 226686712 623031177 107965117 592371711 289838793 866513788 570897680 708777648 264479887 815769733 324624486 557622832 719509156 732226232 619106634 809798567 555867891 841178471 335258844 583067119 493057571 709987032 677052924 991158934 954232050 962695563 583919198 795270090 478877803 832935939 142474073 359368526 522355599 897863735 924000118 997978081 597813250 717200576 611745050 763627129 265811323 970873929 349402784 624978263 51879900 652706393 963220215 995667015 293013257 314416295 860924123 933568745 989170321 994397386 850671249 953077730 10530706 471561674 339765067 486673477 268521764 331028761 95006877 279559485 938873423 965954374 103815687 319651933 1 180426234 416165355 758303127 811857649 963039311 939515366 951223750 47229194 805783313 875272866 877602906 629013218 931034783 215022767 483642745 26843101 863595605 315737469 890285869 539075209 763524869 940854333 978594540 219949544 599499427 620263793 749660857 9037495 384939290 591771041 604236325 432489202 743699754 107492767 943087886 771228718 936396251 544863136 955934916 788561913 946298853 896373724 921966728 406299671 425788504 289887084 620672171 610271397 668960312 424980500 460580639 680759178 766718176 89552441 301798884 805190052 810484740 619655573 908299828 50324406 677774952 853467213 977683025 449585775 652303586 984478961 987415081 908214282 926211195 550196508 640059260 429227613 914028288 16417024 240045450 800989976 875228645 666690807 835954280 523031942 694917621 659507053 814480480 95981246 392429205 716527724 778937423 103337462 152070800 670531778 912673524 410240372 871395516 911963274 962403617 550469990 884710246 743370629 930693595 661607034 703429259 324876348 908089331 290677439 827551446 31460741 186110316 349266446 786806754 58417525 164584150 286381519 915619010 183772655 593975333 147901853 973129969 476571178 696345315 634961915 722894191 453653296 882303408 769817111 930416888 470909450 646752039 709367885 862968521 93284043 189236044 487256586 921551027 662094438 872833179 119584920 151201052 80124642 99822544 471079033 791051945 426626629 977993990 374378564 530197046 272317708 906688043 734215978 977981585 837771596 970681143 335130770 788963933 281251064 758212764 991861452 991941410 7020017 998359212 441860454 752820280 833027904 867925974 211905712 501366246 1 113296732 109781207 900467065 479505030 655234591 265496288 533818203 1 701494387 1 921929578 443503895 453250472 182963435 929427274 20732175 806703450 540350146 629211409 608641904 619141182 531534463 999812485 483721854 867486817 400906091 596411017 459092527 582307584 610554674 663597177 136847792 403203309 651762656 707967000 894529978 913484897 913834417 966417572 655459881 736557777 268905560 887029663 554829140 785732041 765636860 901094496 622202767 692867343 97008257 876042367 962213974 966803971 809581918 840119088 961993167 962707029 314669226 928842249 601879470 741785324 50117239 313185836 985592468 987756822 102777438 995709102 208761622 348773905 791818985 826038999 1 963202589 713768852 920217308 907802738 989512591 472602235 840363617 549974065 615182360 289010060 757638238 10599905 847507303 84962358 666576081 983649426 996687579 797079486 856301524 775204553 781432873 43411475 152043561 173025918 744113592 637206843 675970223 497151569 585083026 44106462 71488398 295606050 836601994 563626413 721980873 685277060 719726239 392516855 527098911 370485821 421664337 974177573 990748818 52830161 924811446 621605918 691444894 593999442 606103838 973530704 982104016 142597551 710640090 602861161 803879571 129504929 373428005 460301078 812071318 548959455 855165364 831715447 870236580 36115920 399357067 595561995 900610910 283136946 397216882 612364146 797868602 329937986 795075394 557324812 562932394 760787813 872709394 634093932 972947273 88172933 663140338 325873738 801797537 456888301 831546414 1 764479941 134677369 655193853 115580300 417938709 404123642 993594227 548442112 672744113 815749299 836171892 386034950 746382077 620448977 646379318 521237538 849101179 338218185 589532367 249724113 826127074 203961141 534796578 851001326 892098445 274025932 407436238 365848428 963919197 427614819 913673954 421633978 446020794 357530557 938011980 648636841 912514644 318964636 358336246 513032823 722812373 565973309 600083178 58766402 469299504 368345069 779867116 160964901 459567008 283880493 676395582 780560895 915178168 180151218 583459197 782118312 986212775 701744056 878674412 225343381 440639933 39979544 385278023 1 363240370 321806876 774545323 377707366 795903235 300938924 358345615 875587973 884630336 488485916 526677701 72843139 90821916 603610905 791308275 457911269 471213016 673918295 687718564 770618987 806095121 486075026 928608345 665325998 825286302 335025546 902669010 438336490 502694832 347956426 932958828 445711057 793921831 519220394 928261872 223492771 529961325 348030089 756413977 557693207 671566164 345049058 695336271 465921388 987456887 937146285 945697589 26290168 451157355 371922912 928271656 369691185 636291350 666872335 813529122 259912635 367743155 158206706 858222874 254157271 994234082 517208368 879318760 381367932 561347807 998601390 999707271 404767446 603438427 476930811 918986983 24214624 864708746 343622270 778487289 16583503 351249776 919202604 965468120 513206589 897672371 136582864 910975913 720971993 755898164 83622271 774908961 28254052 231154394 626491214 890549669 770599224 857143844 442579522 470006519 791557777 866363034 678081522 998413286 857177884 930218786 841258098 847044768 784447669 995847250 310682854 660591570 978169125 996056073 142245333 688081745 449781524 959796239 670651163 702808196 135710 85707103 614323642 740861844 320973488 822923813 434800562 794780283 876627788 916170026 581636669 834867955 484778317 754589493 17663606 291784224 431996992 842441507 990353147 993212468 822253765 901333916 372966607 430053533 916393044 919068184 426277396 884276950 502463609 933325793 690786936 919644927 554919974 586132882 454818247 624564518 706223826 777879682 220162912 463465622 332759314 629245271 18255475 666323694 498534141 544186079 441071187 734876935 561648839 776392829 983505830 985334436 951681161 993203480 643613211 794737238 263892148 641416867 898134445 906197252 540234612 630543358 877362171 978712678 865094183 966851187 524780929 829610035 825293792 842723645 343110979 995676469 607714751 987417696 851348133 931171261 305415973 585485092 853716668 974747434 106909919 795561313 463640289 709304830 996732809 999639826 597585347 957404411 18567771 617205112 806724484 857664584 670635958 946309501 673077816 707948715 755420826 800029347 839683933 971399319 518256415 609987362 964021144 991237871 358714935 948175571 830004337 898744841 221937619 957044683 674682467 944264433 751054363 912995475 92414443 557369963 519410977 937158808 960424073 989052163 266728233 316427522 976558489 992382665 588375347 888916484 338430905 918232850 699252242 907516903 754915190 798614934 376009566 397659569 369077126 804993857 243978448 359771488 679548328 735556825 134129779 161037977 130099889 515924575 136749550 385176628 252982035 778963883 651985625 706201367 392423487 919650740 923907725 942059865 753452635 777728544 370989315 843787398 815331333 861829100 230094219 422388061 975795328 991697362 483892233 694712132 606059747 682201216 581912835 962784671 186509130 955432574 847374564 939143391 802917926 837565677 274141433 415336430 45452670 474511047 918170503 936664109 63504955 690635351 433990044 883362119 726798582 900884745 895451051 897269985 361052805 893035780 813092015 829881868 454226014 875008435 214541587 236746796 131091436 310585107 125878468 870711179 274247582 290257775 131013424 529338942 366460228 638486310 911075133 953036659 793679224 956817321 854937296 861905820 524722621 654828746 724456216 976137820 27116662 514682518 101010021 938325412 680293265 998866849 436674949 544826145 810842920 902192121 136161470 916894670 888511168 988934135 112115903 620161197 270953370 668046817 565413588 717727801 366670799 390826164 752040307 928373354 820585630 916899308 798715593 807049615 676889172 706185830 265064089 647873236 418248323 457376371 331934047 721747089 894663806 951947000 691984048 918867705 940565484 977874609 589936555 968340288 392702679 456109751 470444808 835207406 389107938 415067998 939358304 952318098 375862681 933146713 571817897 877835873 960615815 997254343 274779253 983634377 963987968 989016690 839486444 943086382 25748165 317520505 405213007 885717443 749683532 822463746 225949962 573612818 591463226 981876265 416311892 917008555 820487680 987652458 709966857 885296011 950725103 983352196 436756258 755508378 1 750498980 799081657 958331798 351394863 577439862 919996607 962386771 429171050 643813099 538619322 732922985 153188118 568303385 661631698 815363609 39479095 864669303 864603712 906196567 842330288 881801539 589609795 903541510 860254405 868477805 401402913 880504562 127659684 366684254 234664585 245265375 785123236 873380701 897848141 961400684 627720492 631184696 757284448 957956028 438833788 651145131 150228907 264298632 852987601 989717345 481287899 723324223 820953929 864498018 552374032 656035277 950235850 989673562 27239859 219739526 733043223 917388084 402293861 407193929 140525863 297709134 345733966 667182519 47569477 690752596 253409469 622539486 211099753 951166231 461062082 937855012 705672679 813678684 880770090 972084385 864957398 885370337 751832656 863323035 570731303 749627251 963347190 989169841 24739537 244225360 945990320 974462902 665735172 780487677 567986153 840117387 726045989 980611280 386899786 943772537 10432780 513186079 854700376 982379221 839075706 973808813 244572581 704969895 1 43693143 27608748 817457098 739068650 784934975 962716528 965508341 353696290 883069715 969606281 970092280 222504424 478227476 301739497 959166851 130973374 252891019 358815877 366957980 498253528 875553376 466222993 825990510 558841800 678126045 441754137 651632321 325002050 804601669 53934516 514614445 230236608 699827917 218798636 924108055 923076369 951343041 442940963 532778398 377446283 583085419 310007364 953432513 144595826 975169455 900546552 990852355 475524665 811845372 897666566 926699372 158475756 414103255 440847162 450875973 216250992 413365942 328336571 460158548 100128782 637505898 31451181 113032066 911186550 972494956 759616832 841861954 277745521 279389429 392921625 936666355 954238761 984150936 459179880 829521179 583165043 732348349 738933437 825041335 614245142 922311203 10212727 432134525 575042275 602670981 172645832 756108871 932389912 995617749 2464194 472854127 897014747 930240427 27066278 577780488 118208261 432768970 574130814 603651016 993747436 994006774 553580269 929073925 784735035 803473599 637682257 667987643 904186751 956765816 130676552 309104372 243543697 524579272 123026322 804304025 496745936 906795548 33387217 856714421 835889765 940191125 784367599 938616052 632257905 773575045 627494541 862553262 854630230 967099515 599448450 627157224 625805968 748251448 836398889 893022299 3980082 211161084 473344150 911851086 926699619 950209377 621688827 978555012 403383092 891967270 814783849 925808475 646119789 929253264 129717466 442853608 31916497 240201297 739062924 986231108 790712681 839149267 972162433 994766339 205968182 222489434 736885202 776834991 679360224 850931376 229141867 691607685 703179196 853243360 684333521 847090102 873114250 925704730 900330754 993468815 227601690 512321351 369768465 383955726 430253255 506936953 469246472 794071553 799391363 829003227 78486533 325780303 740030334 954654626 392741303 395194314 584071753 746668957 695969873 877103397 88007497 135033641 39717831 910128833 954773424 974030453 627602604 841738443 333208661 704481210 915975500 933556149 217112595 488631031 377148995 912878825 527906470 898333562 923162767 995833598 528831832 627968149 477270834 658030620 799490627 980176285 824818653 901283040 845780911 949521851 925165875 930043959 239523973 821043611 614485021 643770458 611860034 812727571 944360963 974637302 293380408 735657898 797003849 896087527 792892481 888215814 792834856 805107912 475903703 935936939 911342538 922013018 705994412 992204613 906275328 943042120 247059136 688950961 173435021 605798112 682744043 713315585 847649503 973426040 188197395 664706941 136736342 950117392 994181664 998505841 766302707 819639908 1 959851310 284091145 789728554 832357317 896921873 135551314 963696795 749949705 875540972 160863475 686376784 616438304 659289495 956434393 975217907 172824828 430608981 544198107 740535568 538357850 885344620 962404875 985836635 463491524 648962253 338729785 381524845 22087769 282928236 587229360 852237673 665914210 871772658 445353047 523147586 414344917 587978073 355883299 573786704 898449099 936667659 453410133 918911669 488453 89630119 312411712 915886939 752015119 947592141 838501431 955837527 965593811 982981342 933626792 955872084 977030231 996936334 980643438 985241670 887483853 897962579 223106657 480308219 889853629 921377759 706137118 805210258 382090925 691172419 703928188 717787353 610329117 784750871 33004414 916914395 324926542 508750575 862256130 923321656 754411233 914032987 471376962 487703818 467061168 887001353 210537515 314104408 922854000 996597883 518606953 768269633 210101534 653197647 967186396 998165349 418775736 477127781 312936664 640645294 323953876 977309304 996027396 999363189 935184448 971510211 526482107 590080692 275178573 282276072 686117535 912744137 2076600 637607380 662719479 747411877 845470320 919652717 740363440 994529059 814980152 913702161 53779855 99694104 709006035 880095363 750617053 827869080 887512375 897453893 532154377 654905628 108233930 747875693 824669572 998569120 175408260 522684743 622476723 810540780 589842455 728054387 219560561 964427425 897441361 955891046 389052730 715361799 678878601 993169209 486596963 926832592 83442305 152276296 447781466 687780611 615665507 952989965 594203910 996129058 768031931 905721966 144032989 414519997 724966922 961188190 144138494 198130403 438239461 499897673 25364168 810202396 698986930 946188922 300311188 768568756 462321924 827630813 408111226 895627615 315336309 916779779 917197260 955985302 379674799 931770151 484903428 761069100 741975996 848707792 954211954 955797527 637019022 650131675 848794895 913295032 387141346 427163828 621446707 919781826 646482896 751395999 332348896 362212144 23168090 344381415 996352620 997977596 214512431 693797748 727719060 736855584 205401790 580850838 632971214 944881100 166438691 233208362 564428651 839575567 201208725 657600829 652019725 851745991 605025672 646244326 461652138 748621227 883665893 908383744 15977997 233722895 511535937 638192985 881658844 908025572 844822187 965913080 679853711 800779507 947550886 963875721 330111481 556944964 818115856 931110116 931323164 956497053 416329024 911685254 919852067 948620535 357562672 433962838 83100049 539872035 305272403 434855539 224287282 389446600 244220000 275459877 241989971 380837672 195118721 491019732 917833123 939882055 220786418 780873376 21619358 927817221 311088743 581995491 191343929 775067866 447958065 696546694 10242776 961008780 991136925 994807995 705714192 789646869 160716143 332731772 2034547 139834434 715974482 853965030 682504908 793615232 197241137 609873701 150423505 712262424 909832362 945837825 471623534 776762809 326696320 898218486 3528761 653561699 248404193 576253135 946035956 967238068 273106686 977540796 737979929 918902766 922837824 966615529 504748423 534719518 654401731 988660827 454288038 568038504 272647267 720487947 159267991 425271367 777519860 896115624 782583802 997377159 642091254 967877310 199674357 786621346 59047441 804248894 307749834 716112930 889115072 997956125 70386166 580700527 514491272 714204532 167245847 321716491 628420602 927971460 621105781 754523798 404303674 991605115 235481751 472318550 552162966 583714234 602645901 620642903 176847398 405017142 414454670 757045979 803575285 950395016 674535023 936377785 237040533 521410899 519958839 816793696 806977166 963839541 637003320 698429370 951648694 996474527 300462266 617526989 923972992 996946759 188626238 938489895 788406210 992654076 701265020 987807060 877914682 933956661 389833648 936812062 149401930 946934191 333569695 436447213 301863242 896561679 319064245 686327249 92048819 809444670 985964500 996713644 682502018 998859267 318226895 716092355 725781309 910761480 227494672 547874331 165009217 312144553 590708319 998707826 800663741 880775944 642577533 831946346 921227762 967921020 477046746 523715690 183699644 551235073 177681547 341612071 233136750 919141438 319268983 726163070 746425490 825767854 744231434 967396550 555202934 661322415 292187326 332052137 608229653 785597662 794446460 959150496 705204097 985826378 515144176 641768460 595477145 621965492 198657281 223322558 425593270 428079495 175052700 486419566 744967385 916295436 271869651 486448177 281701370 438962022 354560443 616875235 261675787 269467302 921938353 985883651 688366810 892218606 366172862 770274056 553455170 592195017 854470317 888337282 922171245 970524221 1 194125564 497966076 973856044 48347211 995299658 294960784 747813943 700921309 788256270 462049157 927417956 358716728 370466177 823781164 983075578 108297317 518324870 343178024 397277805 772588540 960046535 140096948 750122290 434922902 747119018 498767237 935227923 660307602 736971977 18964983 645268509 486578842 937875991 552950324 845608740 334204678 716137542 1 470096531 904056224 941325865 435020205 714390414 707520944 930957192 809763666 821110078 161632976 226712890 280963466 550114511 729826810 793641795 170319075 756454998 682572269 912113432 902051997 967189240 441093639 483615844 239555500 543951213 325966438 666985233 572695101 967767953 795341397 993973158 944127155 996388093 310056347 907548045 419659299 571098859 998395421 999380883 855867083 927693727 54710230 332520434 244745777 505493267 296174311 988374200 454006774 663037655 628673139 758158909 672239113 733053299 1 400663013 936094420 999273878 711273207 768808092 119524881 399162725 817773275 903834568 622303840 924316040 777631239 993085914 803797546 929220852 346967845 548388916 199272870 800818036 621493307 633793269 642179464 913207802 175301090 529430720 91316691 837928485 197971028 673208998 25696086 830421533 760115203 955788902 594522586 840098312 304024353 644632840 538869116 586910193 31956129 123861163 649622326 957930840 180106796 652363896 43984621 558809623 545910478 839090605 806109 54249225 262210957 642802556 476315946 842105170 399657661 969041313 753479579 941659355 257939165 823891309 172686628 624629365 13181640 131622313 214284773 805916812 639276612 958154559 168630095 317701584 700784922 786189708 46528994 242549176 203483461 560195425 376726730 661472593 707577655 954079802 267315259 784395805 878366176 884931131 138926549 407961461 272073467 314923711 559057913 746805638 476521828 622207813 658391183 963079772 204201269 533833977 206295609 474674419 416759313 967965314 241244710 261694724 664701480 828322073 982275604 998068132 299901707 650199815 415087177 750750784 962676067 999819649 199035898 708885584 407174878 706989441 617741379 724258783 998597326 998736363 194149272 577587221 490308906 597023192 860843182 932637168 282579225 633687187 644725788 653217319 795646426 842299907 113572890 937996962 682041556 870980282 458027034 606391050 401154259 884866502 942872592 943657693 610746228 902794042 953381908 971015370 685735131 711025579 847255103 952038565 720637491 937893026 623548073 732484522 692889335 778063527 948233769 989749988 147190954 161310270 700756044 933504170 201456158 368444691 870992144 884582046 814822764 988613523 657052633 939470793 57088693 222226896 66746629 408954494 712086421 860131156 836864656 912384885 56603074 171956555 886739176 920992658 78814384 170409752 966150361 981794143 243341104 569311814 877352715 934325585 328601601 813713611 579385194 791940649 450891385 762569296 566241330 667862566 754975562 825557955 219168768 460689668 381347885 866938541 348951326 811710248 993743770 997963798 593955755 752182117 146219889 200656887 22053652 527150216 1 348181939 941517414 983450541 103403886 899911498 568259571 881332418 804557899 965021120 570677784 962384503 617715219 674733309 624999791 947132902 183801143 425614126 408680679 807813038 155298779 784939891 8095850 49237303 889234786 921136499 131466167 273103067 287071099 332013718 67344357 140959942 122676272 189571599 551306531 646521823 785633066 831187632 855392378 896212363 62838713 437573510 496460308 857105206 988463604 991986620 966732184 976998358 820059946 960691138 251720349 753340683 531822676 983375617 838988232 904069295 172105353 377859040 767444073 934623134 100477346 511890967 996433704 997391063 645658537 833707267 281528526 844052395 381841055 383896710 270173940 500021501 193636070 239486101 915985286 936690917 45949404 639747932 87743256 591745215 913373391 976742979 585644436 591136009 315715357 619171324 67907597 92895694 376182697 744401176 750881248 815786731 742999190 850581259 664626265 820325862 257337489 378350722 217946812 653103037 480790038 931123854 21142120 944238813 579027407 903268751 460682018 757340147 251973678 858512202 875386194 937378474 822902347 928729098 357870391 939914122 174622195 771524727 877639957 977330780 906757858 928709245 263804096 727516989 145341555 814527491 350310034 989594282 1 494185399 150341682 174663683 345416933 356190330 26426767 809723637 721426364 873106964 621205893 746172582 566910744 959597190 954401854 963264895 394045541 441434674 635163662 772788623 529953177 840003900 372717974 955555626 339744059 924199297 291529855 953676824 785170275 878065709 901911179 914676055 463164905 563272102 641641503 699245293 167468136 180126334 461177102 825827499 945491820 989408811 517573336 710183172 108065996 186885521 760085525 805508401 142379404 683560499 273693554 922908901 758916695 801799616 34677401 383154598 172882751 277552239 336606442 861298956 314328060 930750128 388561927 565457963 512179040 693647175 983406853 997712309 841713407 907551301 455575646 614013461 370420463 812588181 212543899 859311992 20729809 798709763 1 716269632 847821468 912663470 663344123 949550963 910285218 941185624 241743142 993671965 613280331 989992469 190231161 486747085 12457507 959192710 608255003 901712980 316060173 498503717 510371226 946206164 631161422 672324018 995679643 996526023 390942537 660252200 570504885 852266656 241453072 912980906 607299378 766739752 878680963 996652857 223527599 741541362 118143620 498631993 871329601 873521812 895767177 942831774 916453525 963589550 55250870 376222195 497650187 966449201 1 116914648 607640680 692375008 463766668 996893246 49647911 837096384 198731225 832873186 655223170 849022784 234366804 636263806 841546123 930356129 742599891 835816605 678968838 728592070 340243218 541747315 346681022 411885293 530318724 628278348 1 478161150 994009540 994969111 805932588 899014625 844227078 875898688 703726284 871377939 244920529 596954186 101233618 778585006 931266918 981462992 916484208 967843923 265184625 812553409 854394491 895913989 207865449 749733734 119485014 282616128 241567694 994965876 502374363 860961633 175146863 707356655 860013003 887584210 90857805 358781182 198256678 826025314 508173511 856926560 817588411 897437830 713522616 781786593 384407290 622055948 142428065 756192985 946791313 953755756 195910199 536868792 661586387 683205509 716116408 898450116 336242238 745550726 202884065 979261099 700363449 714387905 7868499 197975408 826102270 857813964 721403842 999507604 93392627 673586645 711471559 960588412 551117154 741375356 558945446 605003996 842368155 950425825 657410815 725920237 826321788 886969561 698678640 780186484 156552942 990480212 817522030 940013828 753400679 847336071 610023484 961565630 752031404 823509504 221409153 597836461 915788861 975595966 542281034 675855516 400531246 752169516 701468939 741222208 535488468 577295324 501233335 546765787 400922751 403676984 764571942 891901014 959318727 998096589 810649147 885399816 115727586 721358627 590754620 658407711 384488191 601288337 831813921 979434879 872104992 894111144 555582266 776752449 836789526 908028343 215808988 836766981 769907708 946985116 410398366 857812255 1 567780327 940559156 952696676 3520203 762091721 252624629 762760221 292163299 614005223 40235491 976662819 166581975 199203766 530101227 677818958 609301948 957063744 773263987 942099674 297643956 961811807 321210741 491870502 738223223 788534874 34806670 474002828 882777992 954588322 305456907 317905420 917333511 941789891 601211951 917861542 559334276 808447481 234545162 438335939 848590280 945778320 510699348 699502289 328046567 425648866 163908608 611211570 699918057 701787147 941016944 961647543 375776433 577675294 634049813 916783424 461320341 515073554 981295098 990371768 846626087 906546599 571555368 735660947 302914803 644935598 156830462 793925557 126149124 841157060 484199676 894360978 977255921 981374436 587578379 957757875 134788604 961515813 997480871 998950425 50663154 276375970 996156493 996528856 183630032 426801159 478484338 608383151 969969691 992429023 407391598 939463065 982191495 998616037 472275334 609100052 130337996 746961213 90847154 661050994 527635763 728705573 741856483 933313601 711734076 831069703 919608444 985855157 217652685 907667277 583254157 644949892 90511679 296354028 685414156 816755221 295243801 615516735 632791563 713285585 828345445 956359532 104561706 784586816 93003185 738394361 904484739 907309843 295165687 464314410 615475892 957119551 743857491 883517149 536237500 899065907 935061304 979717517 287317749 685338645 621038074 921787113 91304619 982790022 975577836 976085988 334597474 918439577 903788747 984808653 65442967 205407276 480787171 844951554 109387580 850735523 720648680 804777251 920041207 989333788 111643258 746718155 1 773449681 190735429 843120943 231564162 852568462 286653116 945197509 626496378 655909771 758639883 955499293 645260503 980588765 478521157 764839999 179371572 895113077 587422192 937969416 515858187 717419668 337082585 649745166 321188669 883991679 749324196 891928288 97315631 779818525 791331852 908782536 555393559 911163072 299309767 318487867 659265036 669967786 982443398 986048886 7534332 89999434 267048622 618134689 799939322 804685952 814291965 850124389 501138474 568079316 644021314 688112447 390768839 418063606 74896476 799624990 530797465 618838049 26155516 38818619 618744553 655627909 582816807 715249183 95744660 972200734 504762395 721787148 822127989 927166150 518217386 656486345 13444874 17353602 646263953 868087184 145337046 310278702 929036405 995685147 880993554 988716793 250235447 494684682 511075382 798767039 243090836 819761706 803148329 823467087 603700983 649118234 816276090 819553770 834063071 943471748 108586350 680921234 666916342 845704916 769844736 827234621 31900013 303215087 962574416 985628914 27128992 489009413 906017303 983894453 533341977 775949120 123606493 757340169 125905300 778752118 385897012 386542328 619168075 766253530 94272188 442626921 486571083 918925871 188085418 693287517 346066711 913453130 909061470 958536632 982336550 994224129 888415117 959159718 165021957 501572534 703406209 995969884 717255342 911637113 648858245 713007404 957492598 985484502 555898599 788894805 331779791 501805425 170148989 622516781 560823375 770505694 6144283 701717398 843038012 986759033 926333808 987436915 498557387 715194806 493797802 892941316 85042542 403144973 456173722 807747954 786466365 844962772 504230825 673274832 72771967 487254647 654768845 850178269 888448809 915563483 86621614 704812490 774193542 913974047 363410767 391635992 82808486 886960584 444804043 671250903 991013506 999050878 971162377 996961505 368852848 927139795 253130788 963718825 260010790 995666355 915082333 948343815 643098633 669383268 437807804 967708243 843226932 976729614 461976553 807881625 886490510 999650603 488503272 941550501 757183162 867550180 669706091 679729845 362769149 438970307 739343412 792780670 932304718 998875726 226781273 697887704 669734653 810870790 365282687 395349694 731294578 790648805 591508873 659474019 56649764 925212076 242793476 687766844 510629310 659656521 441288065 736844452 691177330 807044362 564840818 746295671 41390298 450266353 934618650 959056171 910977060 984947484 925932128 966962200 506887625 654427526 43064935 518260662 49318064 325079667 334586254 458680608 941614573 947130521 83247222 447268519 310195751 396627775 967621623 986218401 65686059 908211272 808795128 878825163 897131377 949844850 652283073 766281981 164625458 198644424 134770011 761958558 690349880 905042909 890182411 925467943 791906142 915098836 480360055 706556659 805332712 858445365 801215314 861371952 303889521 816943275 366110169 514215768 965951749 996820530 727244896 924972945 335431969 535711693 276574329 969486550 278113942 719345685 766827085 817461670 902134898 993945281 170025223 894378314 140663378 448832380 244048507 798454618 8438626 621398799 966421206 966481755 765436487 995383436 460087736 578635436 644397709 827731984 630767255 930471950 320160596 938337474 966010152 968834704 865234591 928226841 882345246 974837764 97208541 334032031 587031105 669684567 244673928 831060935 814293777 878486285 746295914 813947654 232739375 307713766 941958386 983799555 835866043 877942476 305325409 335079755 975063337 995238683 629004064 863523563 830384975 945781628 900492845 995449119 897493025 978187228 332625494 370686989 891147931 894274008 626490000 879927519 712656007 890028787 389089417 518661494 91555299 799440838 565092233 836531411 919961468 993110368 521256390 552485695 67657848 989290089 367122159 896762022 157506211 365672113 903932529 942321979 541711997 633624333 87260192 917706212 845387724 922064835 229842196 757276519 457687811 536507880 770392340 854432147 193177241 338716020 536283837 742734760 530759591 949196543 560389703 817471981 317889290 872926748 286442098 884756243 955418157 962763600 424752167 523115166 738408600 885383432 961421919 988061653 401713446 677508575 293144530 640872759 857138572 936419227 313152065 618458180 350888505 480928212 277572429 425312741 85470957 561230991 35201360 514869077 759312700 968960875 158741889 662615018 727038766 754425902 563466922 888680046 43667199 466133846 722279811 922540077 823402597 963892782 816067472 825085559 471664628 693052381 612880539 667003073 552478211 987901301 823320903 993537995 545982253 671453527 679894776 775719605 115032474 874909971 843394708 947013672 405566539 496600255 417051468 461725989 557202877 656344055 628757271 830505689 170100033 460512035 486234077 721975845 996354850 998175072 176773553 332038945 795897403 840687243 857111550 908268994 693505996 886071369 642405636 971152099 132417356 772190342 274497984 472279841 968060366 978700887 703214391 766126561 603271002 977309267 675588853 847689800 770672472 940142044 54668582 58049689 965025624 991973167 423622462 537819936 730691717 766386351 600912748 803887888 498548725 634272856 553603653 812739014 408732149 581376183 1 798779771 839188144 947469592 863470215 929526646 605715286 942612605 888008860 920956170 116239484 531597722 393677987 998768364 237103547 367667783 97369598 714377445 572642913 601757365 576862124 738277968 388109112 744158954 801394974 886401372 71503837 917048431 638609010 682396763 988164143 999790822 130677038 340937167 347952531 870598120 822612997 923125950 831098737 914578078 340738760 353674954 383152549 834657586 870783045 996706767 772596363 981218445 950716891 954787680 986458377 990387223 669272691 858274344 982624121 985391729 98025666 123114504 642508379 799444687 318383225 414801142 69867663 648109248 624672603 841988770 654775600 868679977 389596538 399638517 10548867 777963876 800308959 857207783 732727872 771995909 202293052 586464039 377251098 405234514 39742787 887856425 824193413 938057011 461928988 500270808 225747019 867501392 530488388 743564677 586861069 795972308 142706651 236629044 1 171466685 763399342 996048152 138198464 815645302 749115834 977590598 984266305 989839055 819277013 989043201 685883529 919926217 654938548 773103140 366298948 626067256 838188326 878285993 174782906 412254886 210687891 892937190 789663970 902062039 590145529 828423477 218689023 903594674 78292729 88775781 851516941 917064115 617793141 936614419 162033195 891489801 167949498 774108963 920137491 956629353 29434795 679087853 882564373 948376183 263584023 860671744 605356626 900970463 545828717 961809933 230822840 678813097 472378564 493940121 849613181 898231420 664884569 922709584 242804374 502663933 210074302 276031596 659038976 850055968 84740865 231113376 829652048 894939282 346150953 410492920 417481709 431960962 273066842 466471621 150302052 221309034 679378763 996554371 161991120 298008888 154049889 326486473 607598532 979799701 356343626 598443597 986636726 987483574 792232390 903589179 866874403 937842796 470015667 956897606 964740375 970714665 680759930 841290770 642931978 974421242 440654983 960805876 699718807 798610237 182838594 549772617 108238208 832657002 23548997 414742165 648368092 688904160 721150639 893365993 169651506 293776554 733237808 973435952 526149593 705837157 58480631 571478316 765017108 947323268 890458898 936714826 1 740065990 617180697 849063899 323290683 345797721 499741607 992983293 535659302 688475691 673128707 960621130 418872190 839980418 237414428 997529285 744993670 842622125 486732425 811704757 453858833 881477711 394837367 617208180 510986981 584478275 196563342 472195868 862066954 935598462 439104108 976797601 720582739 765192492 367533192 749699814 870266941 952446132 102048372 329401445 702180568 945773075 281597065 445971778 520102302 956225773 792518871 873249514 996783013 999530931 714050370 805307418 176680789 553177551 303508098 981741989 202467794 418445283 32102222 786072753 858730104 883401598 664186642 865009878 750632346 893693746 183684229 499001428 477545735 844707089 832446777 907258743 218585281 351586355 364106420 646042644 585855924 802110384 625703630 830240745 299151428 441316586 253579925 495916628 441511645 738433663 310948071 317718267 529101942 655259978 202284537 999402547 377381671 647491798 821876560 996786550 441437550 895056227 520802644 546980456 642606266 759494562 777707837 811947061 827193846 878777799 13732179 985248807 147980585 232162049 725049519 749127948 791269580 906133185 692907022 936851013 738741064 873445303 737889952 884995428 243696436 983504474 837742106 888763047 758710367 834489636 109146205 327962919 880193740 969847374 815672124 818555030 977542131 985617170 179280484 838303154 941123373 981293443 125579783 436030329 706723361 777220562 594641544 901422885 132965088 495984594 628219034 638457848 721496241 965921041 853010068 857296186 423878451 550748549 639582750 668758195 52665236 610838909 892246700 956447079 840826135 944820593 586684284 755044535 615699227 778758435 617942097 665353458 153946369 656065047 931046662 985952880 515932614 853795097 658591554 684133724 552183099 996212293 283262157 926650199 506235695 962521735 918304780 985246383 140497 695789340 243756199 812758534 433188962 954297245 417568671 966709389 308507718 510484957 774169632 999604581 90944483 755095022 950216617 971537836 133989832 472950263 279045138 625135941 983600007 986714480 343633396 862375558 229947904 585465491 179324563 235761860 503756105 868380181 679602545 738724751 813161849 827012893 941138804 984776752 699870275 747068457 671104914 949339003 814773442 838720330 483248389 917481089 221084319 801354378 7823578 370946466 425630618 578982918 789535507 952151406 483215718 815519255 909168203 965183443 751539531 841962152 574000536 581088782 146108244 338209507 903259100 924786277 101248704 707254342 274078215 901786557 568369204 611110779 903523566 997699727 848620114 999039126 1 922168199 203301951 493563855 60344535 882119290 554981163 820723478 163583952 694684032 775250289 977020931 973307932 988459503 68034395 128380229 715878851 899510923 547137834 683415223 249278782 490855950 483550377 492898558 839017309 950613083 908227890 928786832 174606339 356567194 343645622 535516529 522310763 789928180 458641632 675680389 223507668 264659103 417086822 847760883 683052094 762636436 500215878 894993263 627061993 674245774 227030704 391075318 459888715 990194513 842803467 913825568 324488944 641995881 878320751 955464795 120205502 469005779 464648136 515891715 89708822 223103211 22257092 152653438 436887624 722027546 274499715 469758044 612009743 763546807 588106661 793998240 740486464 785390286 820324349 943703359 700381642 956448926 123317903 517597462 714306557 786278227 998019780 999267805 369314799 659732589 401085798 910178035 528718242 765283086 7922282 61203130 430864304 662915531 336679522 691255613 193328405 216088814 287161928 818396563 641283634 857307168 554022544 740375778 691153838 753751574 780191856 844044940 225766788 871725161 616078515 868307675 163325680 764849066 473568657 747278306 326576661 851061313 759205872 870520844 250632015 922579117 609599669 935348876 96771939 730797538 272302300 924244178 174997846 205888197 768889035 915347711 340968574 916702139 778881478 801572700 570550531 783298630 259229376 833924585 389326754 771666879 754870045 852842859 934232790 993014129 198615376 803722437 813908446 826439374 96622594 363887938 207683497 834898425 142762800 426651451 398810989 799100228 220207496 475934257 31047078 548597099 234691740 515774060 327170812 382604740 278815714 952830501 717655571 837729849 460942197 763347235 119803800 772513273 782899541 848668951 799253006 828389206 513717194 518995918 892003719 950722477 601994013 676297140 737977967 866663949 619543537 913926966 684018631 831202410 582262121 753474344 200697556 438723095 134828833 232559978 503042209 890373593 831718941 986911352 32905698 178083790 378715620 572769965 688633297 960346492 513799242 993944217 798352608 831274487 921289255 939919754 167002563 418919258 531232936 739201025 797189230 944272424 743380804 856611861 792244125 905743918 776930632 858821751 630822228 726563687 777735716 969164591 484570918 960277088 372203244 784676271 798775138 857390463 562964308 615101318 269454741 898283545 461964603 981178597 852371281 949489086 77998200 523038319 838809609 945413395 635584711 763813594 975831108 994416296 336541625 699276017 425123669 616050605 30340078 293093769 921405403 930979873 598894839 938882871 765695532 864582776 405879125 901030075 822046951 937117128 709132773 974169631 593056191 974548866 418004331 968067557 197199167 258178058 604119434 899183073 508226380 662896074 164197709 206114612 741911970 920732928 864119530 869350811 825946549 984827087 431437972 780566325 383891398 798557293 189111490 335076185 523385318 834103522 316850137 327730443 313403604 520664308 375014894 771309371 51298812 740278557 205479312 840908784 196859227 224119075 523863572 558475602 811555334 967451444 745029552 983338090 205247969 991100552 257409147 259402256 959683560 990737245 26149618 736777995 405313088 641061932 513149802 533262033 661992824 725262617 608661898 845643971 701872921 818415035 98762286 224175663 755583730 756256906 668972551 915349748 705736997 859383472 285030397 981819581 328898579 975620553 530842601 576277181 355904162 654103441 965686414 968882897 199650034 480177065 641389581 895039550 961531729 996359902 294334166 945911417