1-09.in

1000 5 971520280
533605236 701084501 225042367 527400207 367023257 933535230 548491374 243661913 224998491 517071417 438693462 183361179 406179127 661226635 991637014 813828180 897414777 351372795 193946769 416051197 165405956 859692920 945324139 334456665 236740950 573207605 201207459 323870564 699637804 207912450 447806902 197208849 890886313 186031580 430155165 552591502 305379693 743311962 705712744 420358089 644394871 666515363 454399084 377986522 790255872 705574100 237660514 697591488 930213947 629843220 606646087 832229495 311291725 821857630 352564647 304975457 429990323 171182083 650887485 391398985 756080771 958901538 779600130 455507356 978413495 442900147 637784773 923765526 120475128 979201363 382485223 579829099 838016299 375670319 134348656 299671836 780197148 921058822 443167909 552947368 573137334 319119926 327006244 259522795 462901762 147026177 718361054 150788931 481707686 120876483 722008191 316634441 652029196 718961319 310519496 732135096 857022900 292455196 635629240 933196209 744019597 617459204 484862994 837203086 792685495 926549984 229313698 872001946 657791643 877434697 531629324 436970390 339134043 474623161 788706321 918987210 247831023 519323493 354593590 755522307 827307836 670418759 585801982 670989118 781617209 346786603 925541160 253943523 120731646 572324285 816372589 243113116 145069478 163060891 973187179 224039584 284049012 514506720 584790138 519724118 164405271 522896486 524628494 457132561 869467364 110237427 585918280 421760762 849536410 870313778 598902634 907704007 822011960 840864172 663447817 875158551 340975699 799494148 205529901 550289188 476549648 189036552 782772847 191041875 674701653 986005694 806202033 626120617 608668038 302723861 556602208 928457563 140455354 768430350 559178950 820109835 421849535 239736122 358873929 840947538 632346113 250419038 891395386 583404767 955450028 983156737 836268986 585736586 230853009 126748826 332182345 531505728 436046637 211531403 922454422 500363949 561119502 605129039 776129602 593097967 432524384 432814331 546675212 145114371 477654941 220803716 797529119 112214000 531466751 646609192 453005807 891007832 386099121 637868502 950856078 785591425 210778526 768098069 575021676 427056830 919796919 163617771 988636424 299700911 948316832 376437462 884891144 492720032 935867139 673864495 952079597 666765342 979781527 453791459 648114141 929708194 411475637 968431454 493060803 395236471 373603073 358894497 267660092 976834430 908989351 359553509 278226801 263570501 842846566 713183641 679741100 737546489 229334190 520467888 787960250 656222881 345493606 526409418 933608446 226900755 113810729 456624108 232973704 387239349 807784886 475429854 838889454 314736369 773655250 684682002 177502090 303371796 881985688 513047177 791383666 528517198 475204608 895041361 319957121 870538360 335607895 691373976 227663084 596954325 617481486 911177040 797211551 460108063 693501337 877822106 923391751 905741689 679147668 243600681 823787589 621315359 632752469 529141540 233528413 770198046 219069881 211355230 673145010 794468149 694387624 811242754 340302747 385127669 545835822 294948059 137913765 465494426 957111346 292996136 303079122 385414163 914953061 826770232 196403253 627797271 500133824 582056168 358821754 293261072 643536615 773568901 253058356 817321655 320749338 623943436 727137292 877173540 624124972 257641342 329238165 699192100 641557742 843476501 530055457 649502072 331115473 563942823 111288146 798502119 109335593 346143633 493379156 744316028 777144784 657600172 546576647 714917615 961478132 396928987 755897852 563978343 518713458 534165535 194827699 839904957 535145897 369346449 872673343 719632421 681896370 363389748 112043755 207521632 592469020 980143212 860855660 299701967 579655425 541385341 705593032 309457217 682900990 261676857 775130226 166244845 497101839 540141886 439269240 998050068 726280603 835849835 419412110 118513474 147058752 460396420 893704683 272883197 157966332 473638592 308974008 921002068 239813829 949176956 755791060 249691938 666697393 561765059 966485301 799557798 833436643 385947796 229651925 998092211 941361782 551731901 431441375 346649184 358596282 409481258 464307408 200944051 775076780 407874509 857115541 402442591 542894477 805101650 457459074 540974470 314375432 931331613 262930888 191306858 419757928 478077155 610916182 283660807 222253593 533029871 438916080 587299107 793991094 920198787 365034517 165140059 570679107 694217168 151992645 686857302 732887899 761041088 484383018 337163116 805210867 694554510 506631820 119118688 336945560 981968062 227453038 996621689 877212983 437008958 211095369 908825691 683979604 268717280 147684371 418694959 729717392 531098978 411278379 469539654 313579060 398079610 458622340 454741331 599391960 846619445 801696519 861315272 688461231 505102668 899250357 169599530 652227306 613438297 437917066 508778023 481086411 617882951 231695425 838544505 890780753 711529003 413293697 434628355 781498396 136531915 885454366 773798579 231408304 117830914 764280832 895784763 576241867 584488123 247343441 129184206 894838633 476178368 487455854 224184309 164958678 524205574 593437854 740150084 526107916 340746483 519797713 126539220 722094764 332785391 361400766 816275723 167228895 182686483 177751876 803654072 918820172 458630492 654535942 235226833 185145744 764035474 479302678 433284395 672970984 756775982 728152095 452272789 833962059 673267844 342763797 919282246 636587162 950078060 310042234 455137215 346901957 484232690 815887482 479763920 585632442 443705061 109439882 303941282 968881249 188390062 519910505 673744883 785207421 598474677 872941347 757956497 133601009 145645360 449658273 244648199 603763763 904423448 101561311 192503363 869024121 535310268 164124921 428005867 822464674 291239951 405006526 498033086 451990319 496467303 624608584 846173048 431301301 837502539 273252552 406344569 388726021 643863709 667917215 268943437 384319096 348615160 912143035 250169399 225221682 178538959 858587559 530054083 810096865 115002769 199784718 202472642 168014509 848271303 184003295 871445141 481298518 496324776 643009082 866506974 411518608 457321689 968044383 774272789 246345552 154211349 479030289 998209406 436911995 520308900 365337419 754865188 977721257 129783307 613563499 827346792 537686231 798212652 769697421 785333059 972076735 397725225 198385881 355396957 200630710 591619172 589750640 710661947 202078410 662827841 998037423 550413978 725904275 338055134 446186305 660181129 150705803 825014025 175949626 610791411 856158458 163218426 983181812 351198290 946030742 844238586 206641481 356887688 377371411 826722538 243473517 124078282 590979181 760414293 858303375 251754084 988277440 272845535 705204744 174150639 464518062 905201443 784026450 950862519 162192610 739327315 300493265 601264381 390724290 131384466 469435063 842030491 800757303 361418760 771104531 586613719 504772702 599547890 172631041 446518738 410226297 499684816 354139226 183134532 176665516 141745769 855061997 683529015 756115206 304325609 130379855 848653678 820948975 446169394 855985911 292627203 921890170 427786115 226253416 152222981 306377003 940128993 770597942 430132227 731733000 805690548 749152653 686438271 601876057 367567062 532715243 923788084 619582595 365081579 663810557 301686505 798789006 617542072 773677696 581747900 183335603 198525546 512868726 790958052 504853893 630307443 251338378 258887894 721440651 330751045 516834498 314598759 336777167 570465249 992262254 632270859 507968500 509427369 382704918 283124771 836926199 870472606 251118135 264872777 966545792 529573936 411466223 223946551 997690498 271969005 291368973 508027963 839883379 899879276 765863208 562180339 417881355 325307116 839176607 177623368 365759714 859776755 883295792 567565346 916052752 640612793 466000956 763224818 835632946 822971049 870787518 476132162 553841304 948920891 114562487 620283927 740837652 171359401 133441880 476312413 666883980 420871129 283973454 505466197 270914876 157528216 445317674 653566568 838003864 245605495 239250118 640251615 598570163 136255808 815673263 535065686 120621350 283099785 123639459 993291880 466059602 948600306 174439656 185586773 594370384 737997346 435217204 182121197 475711179 806199808 286541761 684789928 468329953 805107579 811574836 589287533 502873002 548679717 265886195 233638612 364006504 519500509 884101681 466834484 165739599 711795193 829734962 414064933 945518382 225645052 824875787 995500916 978706660 664587066 370993908 760721884 504122547 822444068 222682451 112824620 919973096 790264556 292311846 758017906 938030086 294234547 427823630 658340856 626539685 637227673 524371647 385842049 185767152 593222055 408084667 243563639 539479064 711333739 280729621 913553139 173098445 131262549 964852276 789704448 673202560 203408126 770590229 994329132 713766541 102951497 765621403 844801740 107027616 262520479 981970491 337568735 903626703 148637727 952791188 788617741 881381878 673715257 882372678 962519113 837410166 488911561 577814181 195662044 889975032 896632894 775519208 808918546 177930348 239228970 918136604 770860296 361649806 993124023 715363626 872485202 401540473 363867299 862806781 544283131 664065245 248422620 102279708 679830819 450311837 329113578 462979395 759166187 715103917 214808181 136780813 337864552 810943371 372218870 355774068 517958768 708743408 822540577 662304869 256748222 422239433 155846871 360351321 831779571 509322847 959701469 714735495 801796804 786860805 358217352 839009093 285417163 696628356 847718415 724586380 908177629 681332188 829063555 561477911 648644669 802659781 852523684 166662183 544163963 429529879 117091898 802075429 560667947 132669311 827046699 729038419 923932338 408098417 911289567 848479596 190326836 648308555 629968396 462751571 966433459 379469366 277527682 566232735 433600736 758474773 924327719 708365304 831136703 377664059 626390521 352660468 422994562 788842806 210409123 178211012 500125524 422223509 164603611 109393097 281683956 166762835 908778253 718802814 280868539 460567946 166437307 762792556 159438378
713578260 987167368 379790255 414672340 805983427 549021194 927080058 318389373 296691509 542742563 208391733 685384802 204240245 869043598 740854340 701400634 590665873 390165249 443798381 534947340 883752318 784863101 363728341 562701585 950021691 984553865 489686345 620894901 617037320 594249090 133010337 991815054 333303667 851140809 723693370 405465411 760099432 381284726 992872066 356255829 315288184 287063027 889513742 455960340 190759969 395707206 815758965 726906293 226267519 721940051 934816433 549275734 370691417 626566643 630188159 253593294 645571137 703382548 165191091 202681078 578611162 978004111 304769133 943730780 176962227 621838403 188974754 264955677 701803291 919873029 862293722 145743420 728970452 299001579 874243215 547506996 259790876 609721369 137805503 611356300 651635258 630992761 742123025 818965924 387288228 462264407 395110472 563478057 229370352 621547334 243862217 404085772 574959398 135021404 489384211 802329404 472370007 885312863 453604600 146874560 943500007 419529568 216348123 299664229 198920453 448072808 321148367 589230817 754744440 760707662 395279630 970341654 332692455 298665119 192017976 922192878 878344648 760200942 932445333 690933561 751203209 241482386 116612701 309230535 167455719 976579694 697874848 756713189 317832933 367548749 308886731 951989080 641917083 577522727 415008328 125728855 880100162 132049748 749505125 317171752 230302052 606550369 739639053 119291722 711402483 159016097 623946740 745136048 862990485 156626089 779453904 177697660 978211224 909566094 699936061 356677998 379008433 667248833 934056306 953146904 484475748 614744705 309375568 279677539 915783680 972999113 140378683 979728211 248125548 933199403 776463735 268875566 778599377 134975476 845180955 601308956 423162665 657649043 859289577 309281972 775683408 494816240 981510332 920054738 416196191 312652708 201810026 437014041 224474762 229900926 708214869 127103216 296092653 590193493 850429994 462260273 809744266 808037151 754357703 601182224 370940028 533861276 651545678 684047372 265187807 647862501 849741277 521583696 267138539 670209685 149635134 978724383 450135637 754615694 619879213 703466958 632973746 236702691 151149433 629669784 709494794 115736003 920806088 223247623 279554719 156732570 678495483 170230108 340367188 794153921 372745183 972378461 422244462 262888116 537100563 452358991 697971368 696371541 211870757 518281204 452154760 886899398 366866595 978567028 784056177 185387665 781228843 157825651 807342141 334271557 539719061 667547427 901281778 553691119 890427568 182352423 366663647 886863999 919547250 728258748 567152940 399803542 425597346 633410794 108835716 509399592 215053304 815347363 582750753 855286125 810603682 892129815 172356172 182531876 861528113 773189392 186296177 274099560 606893007 491282450 261404995 577478982 160408627 707908002 204627798 236225709 487205357 256721203 532505238 913341797 774802027 669848600 511079190 992399451 494675108 448781747 131679931 696864795 224879125 964938700 419680679 156929971 869838446 927339241 845797451 250812929 590824326 280267653 685332479 247578521 768544402 299680680 818841936 137706108 675497956 319551677 534765359 782371138 404641789 241158843 918573089 150642917 523992197 521965507 315383955 981183572 426694031 586800957 140808571 331970283 369314701 849662377 863480105 830388582 851281958 855032792 511055997 200510841 630391880 590880060 483875070 641594526 270671514 877083119 322845627 424267387 969348650 821299710 249041972 858304214 897981070 515238109 299281939 550233354 259506608 943932549 800722255 341186360 343708965 772562285 972940448 690544716 328329667 114506263 533051090 477612220 578583467 476711881 809368322 856209805 674854732 351161745 841199629 972337776 717255891 448638400 641738188 706856572 666587399 998126551 945972233 787042788 112160056 586619338 272843418 122308662 498704588 305803103 320354870 372994294 605504623 571215779 801648457 527576362 349618034 714616889 312881162 294393359 775851507 288379083 233515709 771950223 333966402 359089741 873440165 336672965 675490298 147716302 660412987 554921348 430760173 950665237 624879415 338283244 355373187 574452792 163131646 693910314 290266023 733721060 976387492 517737860 240409363 470790160 411663178 324312993 972121427 201091022 209622166 998512667 489502114 774497464 792771708 234466670 712209935 950073803 826796703 250630847 141502335 912430470 381472656 997435546 457039603 325440361 694965396 941139858 897486605 776401572 986831774 541121061 628085280 669498980 811728855 973346548 219179357 374213503 732695625 252575076 189857681 593330628 121384781 763263364 723961181 981496956 497884728 822166794 866753211 892310362 539543547 839237618 736818556 505357909 431831789 937315601 178087342 581089298 634503835 773543428 892170192 538686933 329888866 649658015 480362746 501497356 812040577 938122386 294886200 999135765 748316186 733866132 275660163 881991689 815905410 410113319 916929039 166018097 182640144 337130393 287905341 826724219 121867100 227938199 296841433 987781997 413786114 951574277 545868694 324952948 966405541 367495047 224115415 932380102 445313735 948679476 443495847 761588857 648346953 304047285 860697320 537161172 444875763 140754858 210005559 319903588 452026437 856847448 871308380 633999092 931043136 855944539 746864542 495144750 597626334 962789478 928579584 309745704 612377500 563843154 368648568 924467098 245322266 448897768 888940405 902511923 365654657 491666365 904591784 897179795 359860243 842524797 930650937 342856510 863636837 184193907 626244071 876619251 938116520 399807462 489030929 727672260 205059065 568121182 303957668 888429165 609795062 512045764 459011912 125519049 107840528 370929631 467573868 196960673 123590314 230865544 706412448 282436432 224734176 232478159 907164367 337289532 198015001 630919065 107511380 818050671 746786790 553045698 261484629 737908158 725763516 674290027 539506046 363635984 993456473 276105597 601603505 320654547 966465607 849078287 889255665 634798372 269150050 404373596 577866506 993724478 159504007 159296661 738424715 143856137 601957019 144536402 604455575 849286123 401933243 865698625 760917565 330725020 562497786 941467863 132809489 885665725 832351418 218835708 922282410 596593179 345734238 463625173 879288474 867065795 563433283 398071191 458926742 145367968 858491716 916281344 972373426 969163348 912898458 282946555 636325049 604206159 933462683 990521937 954178235 136343591 715353101 334000017 899166141 268011219 999337243 814106901 634577237 181048631 450084477 468913216 224371604 540255387 407107717 432052180 875484173 946688301 697317947 243271645 906840603 250408421 696837160 146315555 850823797 284714223 557184172 701004722 571692520 247657492 891087813 439589858 850429361 159474528 135004740 394768729 545564645 149809913 405090589 116357826 479394618 449568635 990313394 781633912 926363227 443539601 586256169 843018202 560862039 927909089 846596303 856049094 729840522 136270064 986862619 425776858 892650717 615854705 266642058 920389501 442939527 691567623 612343140 155646979 591455495 961424575 576648107 313033504 480586460 444288987 695872118 344212634 887844623 157228759 730511099 645751152 980341814 418740105 875599024 894978815 775692134 906856697 364287010 914085224 894523875 771302722 501142066 345510550 652592252 260583614 922276286 251116314 587419070 591580033 927054803 914139672 293035793 575626466 492205512 333205668 335333409 363562762 162018102 800625541 385584500 669022837 839792889 490561131 911047797 561469186 340411104 136492824 416814904 119578236 498652105 856657626 822656384 895532803 972814287 844516162 450296372 408778710 178643550 747186812 568881089 801973611 761329546 124742630 507787062 251201594 270637240 931694475 238445367 944566177 144560722 104919137 478433252 362707444 198476946 653114612 256131718 640259467 114429244 152849962 387725111 441436939 587885122 706318228 237274520 834546603 294863807 248667962 118247752 253711140 859949794 872735935 787572668 242524101 930656858 968352547 654151737 806142997 934259869 745709446 825883646 754080357 223682831 668877019 292045939 678507693 374854102 779018574 641819160 515966503 277570356 315712906 596239331 963430552 217557155 238334963 840012876 978870980 976474743 568771702 870718319 181207945 574716605 278936441 193380505 770984652 110330107 570218801 662981349 587789014 544069287 147707683 368303853 649224483 844596213 565645255 471346535 657525590 925255295 849510001 423673367 528963079 194743893 739740907 974968914 204292893 446521617 694844066 831379874 812759983 537248521 498177581 232288784 896087606 532203994 810491563 824686153 748186140 189741646 108482472 190813231 749082385 751261813 497809125 426632835 705033671 108245124 185252364 799828239 295080360 555418496 222589079 712681986 131053981 153796345 898545164 981209330 401105915 997982861 776547726 649264504 777276555 681713875 626666035 133750480 191111900 138869407 822406236 793091599 140685532 481799639 530301277 816597694 818046324 566793769 317877006 185927353 461516880 788629054 234848783 445570474 892709075 830612810 657756165 486700081 377435766 380977148 360306083 756181809 242662549 436211110 928612552 750429862 663224437 289554421 911387792 801713944 686128398 293924683 478267018 377096966 143966736 499489458 937277131 968861677 523697195 876278528 934373808 128117251 108416108 946955929 380678070 669490943 873261957 126534988 370371117 416634230 795082274 804412668 770056257 503798176 430811834 327688288 630628538 894113180 210124203 469511195 742247894 385236498 441723161 983016444 233979946 760903657 459097537 344255308 580637737 631162224 413079459 179027301 391656832 357860540 397464529 372217598 136195369 751506850 250587722 185193116 458282924 683561587 254963726 618628568 130661237 747435156 939188479 605854639 352671966 528166425 816443720 587792518 575982896 381653811 713408243 345482544 299335721 383302923 598193347 275102675 143875626 405017071 239681440 984878983 326237103 724745670 524789793