#include "bits/stdc++.h" using namespace std; const int N=1<<17,H=(int)(1e9); int i,q=1<<18; int main() { srand(time(NULL)); //initialize seed cout<<N<<endl; for(i=0;i<N;i++) cout<<rand()%H+1<<" "; cout<<endl; cout<<q<<endl; while(q--) cout<<rand()%N<<" "<<rand()%N+1<<endl; }
Standard input is empty
131072 323816872 135542558 898261756 158207659 1480110 811728982 358050343 579441471 954851419 278253299 381531684 910056898 220316958 332951306 346560797 374792791 210340342 834962103 751493267 877734050 656082496 669972063 866467440 836801292 110925003 702791507 632484090 373955930 985895812 724027671 15358842 309712683 859570228 913620597 467920341 713566689 577865931 825970684 145524511 385233701 104223982 379572547 295290598 177057291 712523852 641851394 404366433 922864193 329329849 8376051 653114595 985412344 678348113 519582034 674729987 641789468 74889892 159730429 15745397 60785704 736274451 31104238 223014738 448361031 797241186 690935079 14444071 227623468 369422114 159968582 612857168 326162447 539541128 908147766 355736090 104581331 402515511 760102522 27445523 731845359 768478573 533076469 569774054 299343037 52658503 97020393 941132504 127548394 109267173 809394252 40850449 845541623 693014841 263865187 293902653 342772379 807316617 308346724 570395846 29255082 320831657 183253014 355417528 860372784 943917131 711153617 964954114 198948993 323772491 844915988 930794352 92251063 230508809 353084757 391594099 135683663 302621501 185242955 115748408 411888673 994637206 156598857 257430296 687652047 272980395 403849300 30424425 80297011 712196023 453336622 109552092 33027679 636589635 317485971 745916814 433023117 28639588 563387279 631972110 204928430 260819619 415282813 297179492 491328427 768367569 541289942 627012089 70989070 726532896 742760496 335394094 721170102 751875704 592824389 261338500 24856098 996673689 144279276 105153108 561386063 597615897 67221551 446930094 86721884 384707522 45363259 519745000 265863461 461266890 4233461 470791890 722086508 419516273 620487733 65931286 40400194 161777674 545459726 111389263 888310570 140736573 299299708 461997023 892612277 892124097 575851874 917468374 741314137 720131149 875137834 155216551 170263397 794875736 454662996 109501632 32099609 500026255 629246632 297963069 961293144 633480092 621271310 535896003 52996365 241759042 454343640 93396558 256053068 999803365 57302172 144363637 140539937 209118231 458877011 33152213 101242327 34728884 803136939 695072815 607376384 530791124 702805718 630156132 178183211 157468713 739657764 210282820 510011319 221420747 508245888 323820814 854900838 129517198 859716816 760413554 223792591 166576807 706326463 479845658 166380171 616144986 476725646 159436460 825263217 788119008 45105024 779021895 675364243 848241962 326611062 135256978 231549437 29416779 765413110 409732648 39401843 505070873 620015467 549413162 726491619 980777706 873233975 433908808 962811255 585467143 46838714 39120198 752043949 605681528 518965855 770940472 74342866 848207853 930376931 899606082 636326860 975481954 531144328 164207455 676240268 710271741 299464432 907789704 592204871 64877541 170038703 631606714 422464765 642570521 33536227 1472735 623348227 759286553 435381543 438675833 197270047 334736608 477796030 949313996 940418135 996761885 572770819 14761000 697486089 503147749 766883433 186329300 331146054 150544113 350536754 7386321 860815853 650001186 767692377 453020724 714878726 937731079 937143789 137343491 432817952 970680015 138816225 56166178 582482919 426714119 347358362 779752966 761450726 825154392 581583313 554385213 674432628 154354131 569146212 371918716 510018231 188545997 558248015 841164284 339090109 908784769 848550605 199905961 411302306 468759333 505443036 126181031 259006763 442586824 116040873 691824714 265783190 107373450 600507243 848266109 386603920 947865605 480535426 570998 773019996 62118738 554956210 299968975 68989220 976618773 671887690 579007450 165164769 82652056 420171733 504254877 843953176 121238689 556677190 255255481 589998021 62120225 233952864 849004784 357223401 202510088 393345849 623006590 162399889 993853092 323789050 401520161 941718696 804324475 402091158 567255043 718959564 809563719 867224017 787948783 786182491 391628058 366956232 803863612 326796465 639644317 160634840 170749641 760883005 717312029 278521473 203397378 779432254 512474336 904918513 136655654 567500776 298264361 612178595 729900664 144633804 788483997 131420824 86352499 445324823 386028333 506123893 164284387 48108403 225864261 952233169 834290894 470008670 171705753 490670857 796805135 811350069 651305696 967554775 424749425 368617725 98592599 480663154 566330 611066935 385581666 989738335 31084062 536362379 454433281 760984725 680996182 242917277 744921901 619865033 688242100 983466585 125988925 705042838 31574988 204369538 509792358 718382233 674378207 681498110 209053089 323699693 345364530 860358784 143770819 622630307 81492860 242363418 103293460 82059189 853430352 341391478 924313875 884514413 877753856 378747156 498015489 558750037 474180784 95453741 31131421 14939235 78920326 9636698 719982072 963011665 214006235 229774430 681393897 740900793 763788891 742963337 64600486 109153421 455838472 208371304 584300079 537331332 450734721 687593538 471906872 156681424 28985015 248737099 893712188 759255222 627484254 244244029 170521611 101665037 339697769 201653031 116604272 271134446 211289728 689102695 86662462 425295962 918877124 768056358 18713107 535182367 363536046 83313592 496852139 819374518 144201247 81152217 209222201 594935968 621262106 681129072 604133743 502763473 929866170 497845931 262018694 409866775 742089959 432540304 364048164 934304079 634193335 333168787 57954877 845483062 22271481 144617338 123295376 793664957 912673696 142008482 181363675 128726093 77838425 678215813 948100610 222039671 759368029 157322810 816975638 233146486 690968234 273625733 735909958 473350755 771471663 997928652 883217530 366077973 282985307 99782045 152898403 769694993 285467183 210853279 467694407 160255015 355470617 590989782 953919971 120660664 585514615 135283645 249386756 663353039 666015809 197487366 885392709 277900189 207326527 554884699 511046675 898294760 828510431 246956632 371645515 452498445 97401635 107379396 818576417 232903294 59677792 971474819 2598286 345144974 34844450 470292692 505399988 390315066 913798825 311836311 510975729 499313439 299636307 760362484 15182829 965652116 957849849 900575538 243552304 17692728 455460236 754598978 915987487 136487018 854071962 140149353 588985462 951473596 247528748 260078230 36893241 307206539 84069400 39491527 652351512 118913849 362300570 10267852 509228914 276099395 322104162 20204642 627929185 621740468 780567126 643112014 587392583 590933326 543687551 683461239 608626053 851664138 290576568 377129892 988151155 144648529 517279244 577136616 948638477 764807992 837214845 985531717 924530882 921284244 25023243 429398746 40198093 239840165 439666597 401943358 515939559 761770758 422148000 143868743 383511225 55231477 639497108 823420160 498681154 35701010 506881398 107307207 887365147 797457965 336953450 875516301 794622846 854232693 305169268 743261322 471557036 994900464 581309390 396087918 768701060 458848985 825486663 661415504 698689149 117669611 63358861 67145059 879440368 338023212 63530153 115467944 393254688 703027261 938888103 891935842 738728270 298285852 851759400 626093417 95743817 41229201 354126069 742883014 895461893 511811689 338660687 367018929 506712152 919970076 615623198 127929563 378819060 293626212 789345066 77508208 411295822 852703927 144653266 290736189 43243490 60699771 406204132 436498178 763727031 197608587 180950371 502455300 495894438 885226122 981065068 444154606 926455322 187707489 187037619 821917214 699519177 525698305 41452494 58747680 298184733 657075691 186677243 677003792 950701902 976022308 607028352 214514075 681242586 604197969 505250263 724486076 664897739 763970747 13500605 281141121 961579333 194450975 783596421 457473770 79677096 617177840 901628376 858648769 804885328 941182346 533082334 504404504 319397003 574534828 563152184 617581735 84126870 749829426 147101878 887345124 578368085 754130229 101859198 259610671 210844550 459625813 984096746 728258640 223596559 997597350 9399761 37692243 44564676 645512533 495166012 976758123 262690372 249310739 835406891 67575700 43009437 221005576 424496555 362406439 795540403 840165090 979988173 732183625 442510867 127090050 619528748 20878952 733736631 573904297 133005974 944581180 33530109 117102719 525356171 109643019 967216420 534755931 147335261 864297447 32784815 642501273 841055569 295475187 744328363 528978811 215567238 787337799 749984386 492580144 149744237 398041141 332745234 129732409 130224765 775256100 109338811 602269864 648651403 843075441 28690512 781657376 640172972 62220621 751276446 18045494 171863639 571009217 552801425 319198900 435306663 585586239 814216524 128878583 733577777 558544886 510373745 949145014 198399037 112874483 294241510 348143273 510915623 626986743 330392034 493656739 254759194 292247196 948442954 903410597 135322636 977133465 537584324 628011959 39354085 288860770 646057452 63734076 859869986 51375228 235449327 147693001 489477819 49665850 129087935 223055595 460727087 639461680 24716961 659126123 752336162 318958470 7269396 115768136 798461564 190177781 609424874 53220757 482424976 410384179 809147705 470263963 387517643 199248381 950792273 279388080 488109150 449366076 195638507 200495487 500741304 431087833 200704839 990219122 480753682 329792774 65791068 941480768 969254453 90508028 453123243 721590614 261982849 312908990 837358749 60444412 503086770 299299974 966181521 838028097 709684152 627845577 160808411 949718146 827093957 111600683 81622577 167719458 560966758 277261083 220731297 914224413 708348915 421436135 756959886 41618948 751228908 822750954 983099716 720483360 765775333 288739310 294590325 880274534 601648299 984465425 793235297 104735068 136281750 611933169 795279516 845965901 92295098 956087926 648200399 919389054 67688608 729822975 939624864 481171717 7084058 160356160 247912482 715432972 581792294 4872367 757051920 185537554 680139672 592667987 906020913 298431357 881407296 53127590 178705890 335571946 37593014 971941186 292823365 26391116 436390707 88102880 872357016 528685804 44190805 373073766 300591209 964395764 102896741 240216072 298083832 109980798 253088583 545996313 677930121 834880877 403385032 287498392 20418430 83524703 732682730 778955694 381956059 466606377 684599635 413178300 802178322 574709001 237635838 95001686 601100116 674026544 35620917 325973483 202712347 79811721 699047249 503303555 896723836 801943989 596035979 47324020 764441138 849124561 445836684 294887610 536521789 849221715 434902354 409456570 932746418 167585083 40928616 167218828 634191460 725528250 580397128 288886133 300237250 818032965 383887819 901337365 344575860 419508735 79827200 547288206 351836808 778874448 903108112 101076995 433334788 499144090 917366 50292277 200785003 446754050 345179886 737306791 295975764 780082239 146763361 81238533 800183674 187691976 100973713 286891485 913220225 681370840 575777617 65973827 351920156 959665435 819827543 696496015 231690522 899654742 96300572 436043681 678529189 999408683 537120675 111863976 351069125 538038041 14672604 551854127 984792090 359852490 141677269 133284205 992451080 288440629 67039090 792634753 328648956 168012802 79526237 94385533 849383641 507820206 160359359 53820148 320001992 980186901 602832514 551692513 732357995 699133085 987736193 263403535 551058119 377373220 227783863 754643595 767927612 242456466 159014073 605236053 602308955 300691342 738520257 447276387 589131970 805559346 92427491 917780926 973572147 24470080 12166458 675472139 532290285 25042168 581808638 852292276 857745420 184641151 256501141 590103414 736290587 96753685 853506949 139865058 474126904 81290811 894508652 94570867 176263628 53522725 699806919 778572583 354214066 290843528 78365321 795862387 96402873 170792811 566159664 922491372 195262890 430842473 450479862 727553174 455884640 32288500 579845450 166146412 69446002 836346590 756249825 805736589 933100274 462273125 945601646 259743530 396080287 692626649 354314396 572343915 746149373 54121315 203432849 952879790 197481194 281798169 748742177 146400418 452590979 167418192 68891789 647853869 598260665 371888003 227923394 54145304 256692854 807768843 72808067 178655207 496631784 829057892 984391795 282248410 143847368 782509792 394508291 392444007 327652793 748822686 964787921 73802165 655460352 20737121 879198307 852941545 155051641 480456835 999341963 607642619 647875026 920750103 108012839 246135690 145154457 335936233 152797346 254363662 996221427 225605412 433018869 345369563 907179655 269927015 627617972 51027023 52436807 22126262 295987381 232605951 623465299 113291653 158924467 131442003 134028773 38122773 836899899 289080413 518579607 688758213 749239383 18970985 462024668 857252222 265106674 607179124 45704806 270420371 861542786 41926232 496025783 147078006 239812146 255721789 417005020 867430117 159265163 321958178 742072730 455252543 554564128 218054381 568544195 713488595 202012735 702572967 751611367 38912633 844169731 122707326 727670846 593409114 141678310 42211865 303177687 259301335 649390988 201398844 529721706 363450125 95841427 25747488 510528130 335653573 133985628 927533150 55600041 293250791 102007679 797672771 748503333 656571807 868243503 317047528 370060401 70256237 872136846 974188119 109168869 716306577 96895444 689356066 162232042 91090105 731567930 317926080 350391440 233475270 519324923 880113145 449441746 615166349 758376984 959969876 950819921 892362611 740019377 6419962 38129753 842027055 656609084 786633086 351115213 524852586 103680613 721175613 447625174 828333810 547880084 409310394 397156738 497291879 98666460 559388779 588381984 682750741 877314858 791289775 768742362 249156132 523919271 218184108 864322481 134812606 30670335 815142401 27175216 623206063 674078714 65304969 317749469 330687797 704454406 668864682 708056734 660651370 242556646 155681907 488985179 790436729 564992301 886141917 287728608 516175112 298047047 728626943 51442204 27878257 519916717 820184566 277034388 43835987 890885025 141356868 31164944 921555359 809015621 58340159 397277773 335610686 976161479 715027241 666298483 533132236 383891922 226871568 193783605 626448568 382553475 535285136 269401648 800062127 273943404 557130255 168753590 571990450 138273549 220195793 452385058 658190265 892896710 729419446 554542603 783781734 723292665 585707546 557853444 384824637 496564057 955131216 720435323 325241887 522674809 239250157 858374123 906566730 466121724 904674079 385531649 701191550 439959214 654933297 501253676 713902617 64579903 670007265 138409419 202853452 742719410 590794476 713560068 635616119 172730273 120619023 271914205 748539290 706326568 682284000 133363926 55406976 489931568 706315600 233165215 12606376 798082108 91539337 771689457 116720184 848729767 9737458 817911733 141205333 664670754 171681761 855107949 581767008 841689025 846033719 784620459 436924786 289344547 350696879 72540905 462074819 471315901 196971461 63130460 30158820 879255460 49010738 85565796 221703379 755326337 318731010 234309754 405924797 262786698 5999211 522644980 111516464 15736668 340556712 105238148 532923773 512238472 960346097 114690780 206443849 658896167 751827591 643368634 948240713 102524469 568425890 262831884 426356721 617913702 325962343 456515540 349685514 374973080 542081335 571388892 130299417 713328696 805698646 388740565 976115393 664214208 911385544 940148209 532467227 104458607 45386356 917907351 616697079 858248804 885114482 675657279 369661323 489458424 171542264 317902035 444499244 739968154 580733918 870855964 210398207 906696261 327371504 560083720 134185692 721969190 131472612 117001460 435297886 789687609 505742024 263929630 306418168 417127567 56594190 838885394 521586174 954496898 609309096 990799604 665262053 494423577 666456882 34923375 983882001 837999145 205341762 280897596 430483650 786075679 151753560 640881857 545288291 331641415 53481928 679473983 53610604 184954539 796475442 341424841 974642147 154733818 605354471 133576666 571861384 514465012 972462059 945963909 468961909 434287506 936763512 134223962 928711083 455736745 21663688 765109435 146252242 227005449 46007030 429252243 865597480 50276941 70134099 263402122 381918355 123616027 942876104 288045311 161086917 591867898 629470151 988245416 746601715 87340973 121822081 170979450 601805985 946800492 116943359 70767893 381087997 906223222 57508206 162315431 214476319 931688246 779941217 213244912 11210046 678464599 642497154 876807525 728741539 565147605 140209647 963176246 541279983 935602102 251221556 702366899 379986351 880691706 543128666 126588065 968032679 664950747 150083867 422355015 464267590 119543577 345639259 845355586 878283150 255663817 860187369 92759468 187352062 640128585 158520731 198562107 171109535 801017885 75369632 899851074 366165489 68095630 715543671 907445471 3697731 966765226 462328721 236200434 699973283 5457387 215304850 520522313 522924485 365388716 942877327 987192074 337448644 141032938 685064011 215731794 396696754 397767731 161007613 584048815 37896316 319528344 635127273 61522202 120546228 563013256 961373275 339228068 631108885 529433297 99189890 487322968 348714874 414034962 723523401 48688157 272008700 938828250 421726821 794933184 156733318 217120500 634641609 494181961 358153437 172221972 562430106 754850190 569989702 723437719 191415356 460402369 895482414 826542628 521924571 868544993 242072236 335814197 60289412 873181120 865247494 159479301 213020439 66478719 573514262 789060191 115166875 845522962 580404793 389410048 492972497 737138110 459046899 980130458 83836422 817200335 4868781 646266528 424566876 574858482 222220598 468498583 887777203 117703011 147557562 262218125 838764355 389629797 598032321 899053766 115327269 315796166 58533066 328347707 382274885 484563679 117407898 349958111 182602992 550329042 591884510 528091841 139983503 50931408 508222298 223819924 720648094 513091078 722602803 145214969 940465911 944823400 466229903 828243113 915042762 613787465 90461237 606323468 3417261 541009910 505377233 118744529 709322427 416426650 299608588 91597311 753506681 269532837 294071774 936109672 819861878 885956283 316717864 959845380 789404043 824940161 36181655 510052136 190547590 758784458 507783457 131013501 556124209 974013359 811772965 323683323 440317175 754750554 930006790 443734436 148276815 287900375 414995316 857599241 704327024 714603903 801712904 310350056 984136739 948301029 98976080 803998616 686773663 415693943 616360347 476177705 93150456 652542002 838746193 283698045 411326459 199046001 267227897 967450667 25575711 931517214 143650341 465892886 538784119 73657131 909627321 687060933 361557505 177138988 397176525 918400880 891742891 51405780 228750936 875879629 999706808 327727015 532394597 538996823 743420957 1271295 15174527 836571412 653813296 706437071 972785809 65139754 905483071 92530057 885106773 931058782 24047270 28757113 396951667 562831388 954930595 159095339 102408672 169004451 336234326 352101549 87405331 80493568 403507328 168672618 956373197 255730488 496399632 341284145 794727310 92336940 342555439 662418188 781424704 996368735 221371611 754210512 914024840 126854681 846740568 651647964 57913462 723304190 532921429 307381480 138651929 340368375 318993170 241060601 509372826 655227496 593162149 596778156 735721063 849185828 765450773 544610611 104916315 114366756 738411107 752159976 59220047 80966546 267094516 840644750 929851632 488466126 447371613 696392823 467837158 146628533 200557139 378266972 869932722 585994919 685648451 8584650 926363293 4641621 102161602 435736118 512385468 695323750 885030625 100622882 397025930 502997749 497749845 354458596 617364504 236160951 106618572 676584551 169643848 226229439 369745652 952011831 567211916 817117265 500921006 35049073 963745797 701478144 413316044 833678518 139989414 951480847 694779519 66352706 808638819 796941121 354605176 173540638 344781222 239635800 274163519 741807151 742633549 771913363 96265747 212514404 860590666 55400670 741615306 30234513 134146460 111360958 834762696 701358375 928478222 335683701 736407447 744740370 889678196 2239843 430935239 29667609 953720689 125714757 96020314 614875859 922655877 303141841 788416496 119953451 542777641 62580014 861760601 137927541 687009729 958026347 202958296 400116746 865943368 944573602 282867610 89827 55934559 117630305 701448201 836929132 305830357 290372000 434185853 195508552 145128194 865121091 77692512 98848882 990835847 26229178 566241092 766008076 329371018 354657587 885961526 872148658 269753952 600238478 862592550 809280032 410781177 65550846 209396777 276724544 10124447 492264387 129330723 918575357 462411043 830778923 608020840 768241400 973667274 42206692 963749951 118795467 759844134 41442463 70160700 603196332 67671640 636401791 221720759 249559009 843575729 107682284 121707667 113329681 560437114 836816568 775126064 971218290 902367413 984522841 100459185 765008211 329303579 229789907 536099919 791714621 60568830 996637110 412472372 886752455 891360153 228738675 5547922 651204286 122697489 928224973 106916970 42885480 417143116 328637728 292444488 260718844 288836364 266668506 226564876 849273477 103485074 1690940 820491766 858368838 838730132 920950950 475893401 20550062 3257209 11993319 664781034 63826038 861146781 77253406 803094844 752506933 305992080 661159117 256227571 428689568 589384090 363144540 471575047 6527205 691782267 764019534 119762400 980618630 30688040 198843628 682408458 986689465 53050919 355416575 845058302 891781050 128883877 173468054 764847463 132141085 37977725 429628496 48483474 899124505 359398253 851578317 504147789 665390332 512737434 760375359 946596251 954637875 976036250 270687649 813681431 520334869 34707183 933443830 353469850 917911574 132287457 35878308 757117390 37854727 391294882 454692043 929635776 520178758 628160097 546999590 652319842 666137821 976628086 700803315 565262325 188542690 404897984 69410113 853933022 917635417 682301824 653045624 724789643 510854425 923733273 538471073 31189293 810956807 324431254 384659143 581384732 309235063 273053802 338502121 347089789 664348683 793194163 129241917 37043793 273870611 676241506 541879986 940008431 505385943 95199653 357787107 693928633 500097636 279713572 400378006 270249404 962015395 53423629 995039046 325386171 829673253 386026470 356575464 640630059 710457723 593750958 74531142 872209137 866804759 413033262 71815278 383669793 58743777 201057194 420713585 332614387 729815051 962593571 125139170 87717346 57793223 482926276 781645978 410407210 762639847 34540335 680656613 577171593 940480315 675695658 902557764 770153568 61722127 111649579 263299978 624696201 705400536 337831120 349421690 572205294 603380733 421236967 955875086 662124509 622294160 229105023 847255248 204625562 44214945 972394417 292342907 954524519 455320692 73988884 364931728 70476891 961045570 45588340 647648483 901525885 573800349 550206246 524195804 488038827 661855824 640012133 965251379 219772711 977843252 314673068 791978004 433740337 735910034 600369442 95864845 210720545 681990816 795636444 415346107 726205760 768030860 707689013 533246630 75867904 634194249 898178357 146344794 447756170 796283048 793993276 201798406 222599748 196715874 725994209 563154926 711088049 218522694 528406304 930860760 48882297 695595724 575355115 482622633 284022109 28240908 431003830 494742654 710231723 226640273 762605112 288953834 847187485 322810476 822200463 923055388 957004724 572895171 921916533 257277246 221694570 568426160 459075651 444294317 765142033 37586212 7449242 328746434 256108905 388371898 259607193 304991201 83967621 834962307 787613834 220506081 863203215 218617663 715248734 425951289 297774287 330370197 714905123 144961771 653180673 537105585 920533510 462701748 110000756 842450042 719978993 184211677 263392554 179054644 628505994 28534586 216640855 488471587 209797371 472749759 729359836 469404563 777740959 665843808 156883222 417871144 886349889 872602788 636488806 454114974 298554076 934263093 784485171 13459198 931741215 437665843 403081135 852274725 900367590 365598242 547241118 472862935 549809918 810633671 651917578 30832263 691684609 721074784 371820202 901481979 46340894 101180037 223402894 824081852 767023845 232802467 94469348 505890085 105405254 730958153 960005058 256475681 517737597 744490228 122451231 301995164 34672422 525532365 6786240 787556364 743646958 554027357 260419298 145973227 217177380 764853227 176805490 761378340 485928010 548625691 515376670 532268903 502322079 738779563 208867106 121862275 971582029 303336453 627752359 929503634 886810958 587757417 185979315 257064906 184763996 308430545 559060069 71952770 686479261 565846308 859509133 430126218 119873665 119928430 576099444 189567396 737298008 605421285 950945735 75742369 6563327 318838756 608011271 508885406 57618319 669394728 630747680 881716699 972731181 258500039 663736685 712058490 698773807 849715999 969123395 883537802 10662895 528183464 955490571 697142155 94029771 667516055 979784724 66419787 639960836 408400519 108503534 377258843 13821804 911965620 453001211 20385130 230804376 913528833 529270535 140939046 582923561 12534567 875172096 408171093 271034605 538908780 120229582 969808411 241141130 941869328 705862564 104320376 322569143 513869487 801462530 269115266 33901893 633763605 188051404 673862729 42164124 296554938 51121571 55985927 61036909 356639134 928887408 291841284 122684318 310674295 285296681 705607878 323208861 160468777 966295322 594243465 551893908 939041255 416568227 793035038 880910583 974947142 897355413 55996077 341332980 551334295 325111342 375234873 37614251 513162746 49097601 79778374 809717683 952735523 988280652 870754591 161891008 917168060 15112227 284575326 80358706 300408907 990183203 403567566 313394035 808994877 997811030 865287943 748036131 266895608 510839332 481463065 94359101 260711096 537459142 435692081 812045390 862570483 810926953 849659641 228249580 860024553 781954366 37967262 665276427 770235018 761238205 827167435 539919429 628866783 111742760 620278134 929275689 954442314 23845699 95186076 763437190 874173080 960474018 363989673 993585039 471313349 697969089 87944139 732024444 87944582 523636219 396586186 950515065 187079523 98762178 31280996 47104075 880716543 69248258 564896854 503467912 683002814 392064288 895903692 164385948 356323399 368698177 93661636 310765712 245060227 41364063 926719254 119233306 1838080 143225278 965334696 325667780 841194366 53278835 57692224 929138948 429431405 306794761 732170364 616510928 258073290 763451359 516131354 138789832 685215968 81028207 494774096 220735133 325608846 243194139 385121080 681932244 611892316 331299068 845214308 856952542 372663130 771933561 828702200 374501210 915158838 794036895 700168989 608869555 699832081 610377564 538008502 981779838 769688676 122695217 450807117 27761965 886146576 966938470 19068149 571362543 900483029 366358596 792097676 78608226 609552734 29735107 613056822 221445049 361034174 458271129 78397591 733697304 82721041 759616142 108198513 850396230 406169388 660883853 459265784 106001469 123777769 849790638 940297658 893466444 972485854 391104774 773744761 858632429 210559595 792812909 282511324 963558975 11687856 927125351 42167201 621240589 956860457 507740374 842685638 317894631 966011502 773599580 51591934 901248894 385732073 12306798 751645123 791901460 525707002 63427258 750419280 502001122 913217895 690716937 247983918 738220101 934338062 21728678 449368881 144897657 667057938 731880204 960972983 678745793 511521906 855656535 299986381 468382363 363396908 995188370 638793345 181924761 621304301 542901630 83173654 7036373 407724779 687335128 798937833 933431780 603278738 401873464 287949254 369012984 92590401 535933171 107233084 879444814 557661848 556601965 876858822 77236137 140998520 837831805 755981929 652520426 546004691 55968309 973419140 909401599 903673031 612212484 943842711 524977331 7630465 879532717 384530056 415355243 419384196 35984240 201303374 22662933 437857703 489252627 391675917 382964455 25185797 351425352 262409269 435363996 908027316 139268090 512600132 901542188 829616246 268582060 406578965 228137289 177066721 379998104 137538887 80739751 844726939 933897949 458233433 852357403 813430665 842763488 267712645 85331213 878747727 469016018 107994145 169121782 958268645 352186413 552086236 835970793 703611765 814495504 271334789 464155432 806279946 783934920 365697619 488412543 905033332 772276583 716549831 82100052 4791038 706605069 15356154 849517976 493019370 326105938 554391730 158966386 21385778 822104374 244297598 752649856 143636744 352291743 921771637 954421740 704478155 473857873 790392532 260606271 140869728 914243672 724761703 799666025 550694944 90459321 140594920 455728275 715252256 857144750 390344678 572559645 416266171 258217183 274593973 909285540 436839472 828985702 68251925 458225249 503606428 165065875 63391457 647243171 517357617 985163093 454181262 74352123 311537317 97090145 334958394 452407045 11333817 59720096 104589421 562028760 2695768 245184340 870273386 570464375 102329090 113134415 143024020 371111612 371351597 270134344 132913503 808191068 99120045 53681779 118932669 602726472 218747653 182324125 102485994 588621621 20003569 556667255 662973744 331540886 653757400 850448489 783947930 517607568 762684936 888537350 79636327 617897055 133721690 802426064 40877782 88567131 915560478 36418153 312195094 139428426 306552496 297624948 947619493 405672540 351306726 919068513 860915364 422570731 101392637 963401357 11192351 121396206 372584964 526682446 305453443 878858715 377130934 89401372 396466282 139815869 830455073 328618960 610229276 816693114 131045023 651107057 757776596 899121852 687525209 922488041 38550277 994077704 220112988 838686121 252266595 423936066 757754634 113181958 846506796 711663622 929099667 857699146 685576179 154200982 236897944 991029621 33059696 614028877 932947344 282042329 606361098 615918769 610661288 69106725 285128234 594222662 720213781 895421182 345860865 407738989 817909222 384411141 254333044 890538562 75613613 506599638 314474627 833368246 619781596 13497774 397548220 401397614 871196919 935640750 555598595 108094862 779186723 588658290 574640091 564650418 870700618 33517540 33085538 333878257 102624264 318213772 780617270 822838044 66151305 126478134 83093384 884060526 363405626 337426427 627115439 439019238 844026064 941590065 124903836 316324011 955087838 522452055 717721624 678801109 310609156 125836570 639412322 89795878 714494859 66568764 654446296 437711828 100086303 687531833 624106436 55226918 858261956 404723705 730581313 924413260 383718190 813674696 660990138 747123815 3617474 288105576 186143053 700159890 82211993 311046888 16483900 889816182 686015294 586721876 421133642 996624449 712558445 60545964 86420327 279569656 979631079 593382974 569797835 932233734 133431158 193904271 987460651 991693114 451144327 570558316 768622725 834862517 236749363 429612862 581986331 240366837 570234790 620645735 940526726 652446782 931692622 809526977 394779315 470224267 248765204 815912957 466848716 813840001 728975272 405785394 93409656 708606350 851684719 515723842 493356435 985115876 709628112 333333438 829325341 13288791 903891753 450464418 848151307 140641115 880077279 282653989 233524303 302828420 903299724 26567380 955275201 687508697 836094357 202570868 157732964 937375912 18483824 477098031 751215912 747459095 882883424 697141919 308581796 587084494 65382113 801938231 424716721 775010224 135271668 106558414 788299014 891679772 557022831 488966672 32320886 289616461 771620661 118361541 592444881 674920384 144928920 400236433 214945432 981023276 602807300 372678395 770915540 621291123 849776425 374647803 221266569 585176200 71789722 382364717 24777045 137171834 36819299 449493766 764698409 24607318 556052179 405513775 916287089 113075009 894480446 801124326 402691469 518617458 919485866 995136349 46054193 64414786 247889134 260999625 897954413 850696433 633678019 668869952 324503908 335970796 43517755 545770476 773663347 967823828 928135192 798440392 957512013 964954490 247934157 574726773 989561807 803986335 832756899 758365247 769577695 579753697 559489573 24785515 98371154 331491790 19921864 144425347 395906575 120327349 405424971 146377340 971023781 891619341 815247291 295527688 80106488 711281397 693814516 853769835 531621576 474466059 652210226 341649940 291936901 752660734 768893065 134015059 409163420 601649963 892380306 178741114 33920011 304386230 203526628 132291165 635878019 75964843 129232863 31784594 196292191 534657833 30678285 19832324 278793525 845925575 315360011 358900013 409723324 9174526 212669847 793861251 336156937 717396424 135511191 628093837 470057157 756920607 762108895 879220576 211086921 654489200 910478041 245006932 958875429 114004668 377298096 447269800 42485863 506530958 331570745 91294405 893705142 362249029 111126728 172498666 60690955 426486739 531398678 470414278 288177616 596584876 116791881 624334552 313981299 104819423 104944740 636554807 861740029 867053635 368291734 72826949 374059186 278769774 317833880 185450967 245290794 547648327 632720766 140293008 54179284 964291510 231587412 800400777 326540538 342714140 972899443 387231492 769200878 356814472 710162122 909894845 953399348 826954002 386745749 119896998 931773424 491690488 756451805 793513452 358744122 124743538 718856752 732803308 256029664 36690632 918254274 353836809 436855310 403491391 494129816 343550946 367782900 725717227 143951722 546839789 68431366 969367516 934071280 690148595 178698340 496749753 600043440 132097687 323703754 986789188 104511036 107993529 330996027 713479192 901506980 689740149 690739082 472880084 275059808 946768745 362087067 45830433 153121905 798942376 449321823 647251720 142493321 669621074 372968946 138961395 216460862 293916664 108328910 3048493 984065258 287027249 499798246 436625049 271641287 676018351 275930588 228668675 784011880 606926615 942147866 538035211 149183115 632886947 10915294 424242922 432172043 373002360 322589706 585293947 24461088 771911528 85062018 166954408 294048953 458030964 305915802 510509814 751947627 266761064 366074658 588529236 553788312 865872903 25154285 677945951 394407606 301084872 906614625 178419485 908011486 848762490 716454695 57194600 334165789 579886341 333953873 618854183 952888700 656543578 56664482 977349787 280971457 141726499 996820547 575020409 599757462 155252700 938046574 204221440 422013763 304121232 792750676 975802075 22510486 670421312 506264377 416918091 971506183 412879001 447853927 732034021 114157842 16824974 641744972 300839982 596711314 828215197 919694165 402116365 337275126 976358646 231982504 618246583 118085144 228803050 45783343 570358958 384055749 983829917 774580397 806069512 140467500 419847424 634387938 15494337 90268735 140652314 432412428 914291270 406047666 880266354 498841642 372721859 897091327 993102965 673561841 346318992 821318161 593256005 748435357 11109639 422131002 980417860 629356221 540216145 61737261 527655915 110575102 445793009 364002183 737671851 104378872 504469682 10035626 591283161 519964019 952820713 584451826 804892798 719628334 990499491 537675503 70986327 215737702 287283182 64089291 889299542 633602173 737923804 335071898 382037529 749033442 757202899 214971740 230906014 149935395 276709000 758561928 113026849 722502009 122564111 850698699 679397232 479550144 713250676 270680393 999514162 666071388 855132218 656923311 238216073 698148061 194598814 309202399 913885762 481881995 373291690 655701655 115484167 111215493 990773552 350038048 712765286 747976450 565009787 943671299 897911844 841718787 702233226 10938692 416737147 677313688 714153742 96134378 156863832 279920770 219331122 8894345 945992157 926979692 665817656 36724582 477644104 712932821 345926980 244046217 47331167 719218669 899747871 15331685 682950513 890521422 365369732 248232150 491014223 782895871 191903448 241442418 477131009 746653026 104897462 893868155 423966713 671567555 842518884 433346896 951488324 914366358 442241241 749996833 841346049 960575248 786721414 171506504 673508068 132648393 415552720 720839234 704383414 315300590 736170918 239850278 58338363 954057002 488082428 401868937 736952872 679985875 643311354 66600232 279155252 600725167 960468386 703121965 272292722 655503621 136468860 76297397 422386330 431226452 826294229 116248730 244318051 613015642 287755233 917826118 598180387 703307952 491181703 302563800 18608541 79868973 542414077 929463255 33925974 30496504 331332191 623395197 562998731 827159897 689995428 842153982 427885063 502980165 397792298 552694136 11000137 386777510 628991533 433386467 670520313 455285761 549635196 914838364 920817755 837390429 685180833 518998141 393214732 28878888 674078292 264339625 108747860 69008720 193802879 995190185 99505224 377651422 471101733 515020306 204811318 13613512 209690639 485212732 516593676 459999289 37906868 380110164 846776798 666898400 813496630 369813462 974700512 215648178 284651825 895518266 905554958 969832658 267032758 298769689 998711545 941111049 563109313 959975756 10119769 609428544 955165940 962141344 987079965 278784024 329678001 44407634 292397535 391884991 529620365 808991210 851884279 567527232 41617725 551177428 86941983 855114355 920990890 61642495 923278884 58159066 809677112 828833841 27991723 929226222 980119881 879219619 722853622 395745546 691711726 585489742 5174089 499394017 400147437 992254053 778178040 729825437 36661686 70575574 121710428 418798402 732083135 826111058 986325634 773700860 377288486 925783968 481331566 150795727 839942814 404610449 208954792 502136278 85960641 89462867 431362499 66080521 968682485 6732472 314342418 512910563 592222214 319516506 12304579 992369650 164286910 790482619 574711439 53464947 713574544 548938218 472263349 445657679 375049275 311105334 71874890 604854112 89405653 553206455 755649838 929348467 957816903 964604630 431484744 896293895 54067496 715363594 814890767 875266332 722096065 129233185 388176894 314318278 301266042 252997825 159204280 465552952 43480443 733915718 371534250 609571338 282853935 843797598 55229016 510419561 7419283 127103905 115273673 96824936 532826711 870923510 26173402 343159965 688044491 310174497 239453859 742111986 25538090 54344626 469894670 600150506 36094162 858071563 914468784 337360203 111069387 73673063 655429506 7066181 660105132 26963756 469153871 942959066 723277705 376899238 305894978 730696988 356519495 421168650 680038275 889346205 144608512 558728028 232506170 832653002 868902524 324476380 427281340 746956965 231337357 897176009 199623822 267431518 607763923 114092605 457308073 571349662 40282019 112737578 430932194 552903502 139701333 900086064 348378919 715495390 129501654 654273897 298708729 486021148 75442546 978747003 375367352 72567409 537475030 460389873 757736763 258893905 784866253 37534454 858367221 16203609 934710462 57991042 136151479 394990736 24599999 593459551 818856749 917398369 706197128 102305295 470301871 698414813 2391358 818680789 266426554 131893011 325471037 565135282 470430510 253429935 543882284 845797862 325997343 933873665 158704086 83734105 45283921 943570338 121268558 903651141 959773947 908495371 961642182 95925425 156002459 838758532 541901327 974859207 756156901 100614806 77164501 78975123 799029618 932072211 750172263 65456171 916481573 75643300 483107804 239428435 329073234 26990087 85226296 507586928 813380103 96446733 443837385 858664023 40017071 417622294 762315163 852307369 178634017 576473697 800749145 334636475 267748580 342650471 162012033 23905480 443265276 91692886 955396954 94811246 876281448 705569217 12783768 645279372 633728868 495891572 884707806 962802101 375398010 822450453 322905380 41294465 918897186 766742764 899958487 958914256 184365058 514790002 663737976 362999074 91263698 464487120 550151900 211528629 659653942 712163932 87950461 102919217 656373169 43347414 50246814 532654616 601432982 63030582 30450340 235161849 411438505 915158145 50480301 639352866 737608598 373385681 680647330 509022135 140128444 580605817 320452742 177009853 95395818 984190717 392525278 39175867 301194188 942677177 103220847 960848129 507357461 191171307 916283697 163730629 234518721 966530511 548901597 835951702 882077444 579351936 923629903 146032300 494510080 974110203 785385165 84635029 200012235 318548847 593657163 192657031 899154663 914109904 222183235 847066832 750816972 614708513 738759050 52011159 557385689 841979896 12859287 64743149 33151203 781659336 80990130 120186275 600706198 629891726 808654328 335299993 61760013 732284230 481332292 556270092 558910785 119233808 493421473 611439371 437782654 87078635 804096401 189453668 853704891 26279636 889036851 457038214 493504500 480312252 509049373 50890188 174808500 374425011 968149689 60476054 8600698 901656170 180662328 609306895 384064247 989316655 944606887 445824259 574117237 278455530 2094350 985544373 397689338 348032174 596983743 687988343 287627161 253596496 877442011 141332051 132392483 618995213 450886616 625896982 99307465 959935988 529303521 274115964 186877351 349969561 334592017 195478048 104142082 367770696 804784943 488206328 209603702 601908181 934030586 783720938 880363711 788641288 621781662 130569400 136673461 71281757 818557742 424300621 324878252 548516104 418149023 309787086 167511317 869035639 935684067 119335133 681487978 317503939 393451096 720881680 519989852 580559464 916359728 624131933 948330159 573661022 112338261 157933860 28085554 46368846 794171150 908449264 687526485 415952811 39018663 824199946 487234567 857576405 101016918 664629170 258608860 371682293 974416255 426120176 93234283 762616673 545455308 774722260 80120612 791422755 348120292 452626815 371982218 116996371 76758747 172828728 690657392 41613359 330762588 718742945 87982205 124933737 479708561 628025041 393402899 518727223 304741338 733153818 228819979 405758256 397782987 487428839 777440548 224715594 766065366 870674830 987332266 164037026 497913441 919969229 955459780 846033732 372596043 179958350 963030102 301871142 352787077 506203845 343484500 683549664 77463142 283983056 660999752 557171702 912008097 906919003 928415276 216749434 640072820 9751607 475024041 890372158 497180445 104980940 115087751 115762162 975655769 102420017 279799187 326085562 874905597 235258967 24635645 100017992 415217316 840182099 401889133 768004392 198902295 745373632 304070408 276365436 29356688 817586511 686053489 941364784 724505513 614468765 10630569 217094684 624220371 485654610 107466842 973917167 590635549 75070944 89679328 418807670 30007312 369478515 597409583 904912909 457253833 622045227 4930900 872471148 314743677 259336384 492991891 513645972 4710015 649578650 790011407 34066702 467165161 328581248 827947837 44187025 943050012 691094758 113798061 419786734 29265719 73781254 246220252 619901267 148852197 335899579 891225288 31375861 557894445 488634870 936288769 15148277 963196449 793736020 740135776 277940125 53072403 85644019 791586096 910298769 735222668 434113855 796881823 54904180 762695102 477346011 99091205 558261465 168440768 212889265 830564550 197706486 286670518 76784801 670124105 288039066 265200731 561349392 319414926 823095176 902500614 108220046 838243452 865697062 901956065 430895580 996153538 807544819 516539598 640255986 570359940 251762265 74369840 367241762 306666445 689581293 844587772 258274001 100359109 865544892 471163265 930923658 63251377 610350134 860224810 585891833 898389199 125425540 147241225 217804125 948520715 902258190 326024170 639280519 620471603 80496587 70176098 616625140 740557757 439232047 109397477 310917696 690994311 36283668 530675809 850177107 725864960 227779933 108451107 678740420 93324824 432130723 462180429 9092552 42480856 322405238 594984385 940870055 300347130 594741961 11190531 101384196 349516502 189731052 740664714 969988104 270227638 663357163 439129595 10785395 102589209 548527072 174219442 646099872 584810739 704895251 348793330 163192051 932675183 457244437 841932470 878516358 889375159 304112899 887608909 784372367 479034488 335109645 577758773 779381617 782367957 588949303 880765813 131884458 778680354 473946878 101872561 901424344 137304041 393518508 764726090 92409601 942045579 938945531 591025824 526856317 496357133 939819154 690048367 281548667 249579942 384497189 12581376 991471452 688610087 900190285 775843818 20160926 87816281 206118942 799542543 870184238 795068244 680308355 854585047 426264950 6771584 808973960 180205645 144075624 202492467 944931734 89001577 144538045 736393616 532543752 523910713 85267101 324879257 66475432 366815767 426975550 450972620 379397143 418447002 992099058 132103779 46807171 12259983 72436411 252926113 811802525 942620648 900510708 344627231 649722047 179292009 351398815 458696006 359497653 347990790 513704824 304429386 289508718 510759220 40823002 674568822 34669932 126090102 999448078 953661715 345422220 278939980 257150686 577335714 697386981 249249743 709439492 596710503 114026078 781875903 849636615 925828602 577012902 602663675 122972185 79251300 781955683 326887351 537947305 141453336 674878140 51652128 298399073 816903210 414927699 191738426 491472031 302113983 170344879 343436460 255775697 515767099 622376439 512926383 93102812 172279771 614692477 655058656 768990274 728718554 289450910 471143240 507063508 718980163 73806914 630035692 798231463 708278949 956923042 188695119 849732284 484317533 92863599 647708 153737094 507791297 192386134 645209124 809905279 362731012 841161936 65680976 878498110 316054726 431123710 824117274 488334497 45816186 331692281 109841122 627051092 473659542 433500713 134114599 192639704 359823979 616666642 990871166 68102927 426106035 32082637 770351562 910423567 124946235 770999269 64160661 632737531 963385402 561886136 442642810 326116414 255564423 360840137 57130875 571619149 644480198 733764500 59953645 542812735 65456780 22311118 169863826 391632673 455811830 156494776 584272377 815635808 773161417 427659894 736255086 199267451 459742530 506606647 962207370 584688764 130122268 878884382 69942647 93507669 293286869 512585456 272140434 548851292 725941944 329271309 120470440 370422141 63035808 32940436 913234875 981008940 55251553 935615053 225157964 363579734 92109828 809430340 31731894 865271245 89606586 767986979 917055047 401865467 127109978 879262416 986554231 257232245 610663149 56496877 203256265 903950018 421598684 475396699 452801309 56979 804668007 425788100 370479119 720220166 458728535 136230345 553745457 366496439 71845397 778903421 582592524 16471577 440850112 614324417 734259173 382973049 234827748 651314219 784838516 214454077 383092987 623909098 471686321 993756135 532922326 674942585 750222504 954521009 2855635 55540164 954577987 807523641 481328263 177573457 380260159 940056797 166320153 786521967 159069587 90681902 417941739 741662111 107153478 858791851 208502879 841412650 94281251 295846978 345243220 879119766 510301054 580852558 503028863 981987374 427125045 35951188 509446311 177347548 842988548 512301945 232887712 650082886 172341938 714215974 680172694 405118448 506789123 846492847 191640414 518375061 937174748 609582153 112553523 44328225 320890355 321056402 738257226 415171605 616903379 936016797 146807723 127204433 516869355 649836585 961708158 943994399 538304125 323670820 973858298 233809024 688489117 59262361 736408262 860831054 773478335 416580955 118465853 132783809 115590153 310106266 651158869 52764900 772204770 763712392 949609476 93095124 937285145 540383053 360783081 406704875 476399850 507590803 386425659 845785556 9943739 200650169 642296306 400764215 524320988 616154603 634573239 65326456 675416964 223497852 926157509 301411650 640078806 44623361 286711810 755668959 207245979 937870678 660950210 979450748 554099421 610559686 925062224 343900917 3459090 138361656 750605792 479858939 498468810 137031450 178160846 508412548 337681618 820457151 909176763 714518958 289128106 396266353 779845413 964545069 619764204 558519274 118473070 112359361 455658986 405184879 720544671 662904964 195571908 381494881 494872064 602187681 844570918 272450639 946088597 848030007 263328646 696694388 180405298 761797455 686242190 358566143 122726354 23923807 179023294 31903116 590959116 468151399 280685820 370804529 285212819 752966375 929323802 256202240 865325736 237499139 661387118 438386758 900404103 709475377 819881638 247792518 311663057 516968907 372759508 110268006 364998914 636088153 806962393 545404211 397885607 345720934 903970353 520611960 222161093 935509998 405031428 813120208 256177748 538233599 36441088 541390566 291199974 965764889 797592805 9042061 55780380 311496274 447428818 956184482 20971651 119826808 56493351 185151059 636795714 429252858 295419064 854310979 65341010 954897809 252231541 315742968 300618742 8718246 688871279 522779834 944228243 93902706 188416394 200405991 484652657 224857481 594312908 775852630 43138722 244422065 637411042 98919101 555918338 84839859 55103582 429406340 57183018 964113284 467073751 546495084 245882493 762492814 400806062 163739854 569906974 653037603 479482821 870525716 661755848 20870451 245821901 458500442 114773157 434238294 658906432 451942165 659095775 105735692 80311146 702234496 350157756 717722187 801153596 906076093 655078397 708773529 187998785 712261415 525403164 655072535 111272850 771285656 270081700 512078911 935025509 839988674 17632865 267024681 563030741 531905064 287895131 661368993 990405506 255184639 95607287 501828289 707126803 607219413 607563980 787437948 161970260 957721735 505160134 815640207 716314180 12754883 376930087 904312964 725016297 902333250 411901850 836289146 673618905 534499901 200884408 461160765 227004926 71033625 728185445 790035666 602938688 16080575 303921011 593344193 271265214 252044649 95172482 978392016 859264061 555252813 618346316 873750672 512974548 123506449 689390878 81805079 136261331 66320964 986118042 713793979 821170565 250536243 402599476 347305821 785036143 456000236 808466585 12041069 527033860 536652029 654593086 129972547 405248955 958514096 575833092 676514168 63075096 523521925 507422536 922339156 78774737 125768851 648606179 444265636 101791651 190513408 526070714 90569334 109350723 364705107 656879664 930521287 615241349 911995492 277827107 252793844 367995727 86293691 117351264 895029586 475462071 624460701 877518484 880711026 435491149 453351575 409741545 498566244 976873499 769680432 273421752 908164588 747965634 922027930 352430223 702273637 112541338 878500937 645359322 221892060 95722395 154755337 4929699 710963744 66750828 282756805 816273939 287262906 221566848 933625202 34808843 549545270 410602254 912327327 282772647 846093402 218195253 692514192 344659646 47585104 314710975 618081397 955749691 62676609 392625678 160696265 764950245 505167015 39197201 262825918 579575427 134919596 417581254 584505125 698399691 484332082 867261929 367189981 771594987 941345128 153331534 806403830 490890398 563933787 571247508 773663044 410027189 789442760 318693587 607203186 837027863 633404562 77800934 792777553 548597522 470426611 953473818 166064118 975593626 845187370 428890035 407685404 832623317 846471288 992190528 383539359 183319721 711968808 750729339 954914708 653313936 904060872 613834889 996720685 320511011 37598748 622900080 730538199 827041507 941593667 190257736 664069370 427514580 268058669 309363274 976112101 738485279 115353443 142176218 566595256 813057165 423582604 974280659 498196833 270053891 966471186 881736192 453373612 530956346 484981882 260804671 36786633 241559106 727155911 33507317 562070116 764754658 656407396 145124666 591796164 450517414 335382401 108381885 730548345 603441069 270261511 559176797 194442699 385614953 553869366 761037955 51188469 977451969 735318613 549385302 100022212 554306151 283637845 553395823 85262496 768619726 666716845 122049128 862695183 393872755 8072796 277281650 11143764 516996543 422406315 602939927 967513957 610305067 563838164 550578653 66262487 834099674 109755450 260705186 72230978 663624815 21743140 123419447 493593136 609578104 672804748 593615347 16400606 956442592 147011169 101663101 577578669 666244365 76228580 440273852 60117119 936817727 717555501 71260882 453814270 992478168 526717160 273844578 602783234 90555323 824423230 669045721 777171348 786695031 929750906 849402326 302836198 804010397 972821772 796429333 413588500 645626519 390044679 429989106 454585462 389572199 384168558 32164130 55816563 312913490 324954333 968450033 102247568 42509834 892227266 556061837 887504353 271460777 682422766 342803938 214532452 359362348 11849658 991703799 146057378 794116915 693622476 448893575 450643663 666444247 97839259 864232163 164587117 487883937 146737620 619172578 729972487 383422529 503853060 638305401 696336018 828807392 459271785 798583586 723833577 204015402 207161774 611337929 475476179 889584540 954141867 542524982 101463239 818507876 386745132 247520616 465141143 80367608 548930543 915784805 599328206 646769801 632533319 763915323 134653738 631787290 235604252 717142576 15209819 739457311 355447977 564062188 420781055 814719761 215162125 144614631 18735163 422323899 608468912 346727693 164424790 415127130 889252674 265888028 86151357 128514157 365924995 551292499 208881764 914855537 319593656 808209970 561625338 804643326 424641644 548795427 436430616 512762247 118454354 304156786 104735910 473902330 868218973 525516964 141138443 83381098 670131594 12389957 358221348 131116857 211634001 522646137 546243986 100886674 641050516 632395343 81917182 6975510 36204193 290798946 921831047 355797848 951525267 335972736 12957526 228683262 737284514 449388141 741445508 855738867 753544926 846181417 182157549 474280250 371698380 323295991 557661347 894346326 188202299 915882694 25463182 399836299 291045182 571707168 353239324 932095697 56618862 435156505 791587559 92823054 725955450 565934957 448620902 529997068 901907692 461578427 758680329 491708557 763482919 500125837 347447423 369544196 198823605 529604971 843824445 570521985 705417313 254002144 317384662 893619611 22401189 342847843 293455909 313446371 767071362 646695232 98058419 823690223 81851737 889645977 916513277 660323538 308097285 217650530 42836958 62521328 679228956 801517286 554229884 295228226 154159474 901677307 664772421 352983079 283798629 508596865 923505063 989215942 762599008 93406076 735351904 785000197 436253918 28807813 950962919 55841632 528019396 49021337 879531854 462387484 791183666 796045130 975227374 99280950 13695659 18064331 14318630 545440966 819581616 568548513 840669191 973741090 322742171 357957963 179240520 606540800 866554828 102745582 448273093 481670187 48668009 36141348 119186735 484921926 64949160 70149653 540763557 445484908 971687342 272811763 760388743 615387359 68856892 735616116 567184660 935068903 606196798 581503289 333026220 278294766 2568154 26211763 104552207 325310324 384169725 283792726 931851123 103240904 239054659 232640567 437427443 287722667 268781915 556614177 772644592 186247426 479280182 165924501 484248685 303483875 438736263 244637428 771387585 360109506 832769895 191088596 147694760 438966693 772591885 333237332 717261458 775160038 359449094 821813664 100470361 596135170 105606389 884837836 699376074 197177399 969994754 136803516 484900065 91293020 545934044 110061008 277540446 877730577 275985508 761789130 33730803 567238122 858942909 805118387 927347628 691712804 996206983 927558739 983195848 621315219 260796070 552973657 248991608 472761515 227303672 201978320 68896685 185426412 86816155 620789110 382603810 909327261 610108977 867503874 620280 8559372 977564881 130677077 886289949 106066741 892466207 920020751 673304862 603925467 725139138 453168841 148154622 573862472 380727580 131350469 195177690 494040001 684324125 444169297 966801516 911627796 646147616 35698200 97054207 585480123 509003661 332174368 347323735 119112637 199678241 347944014 127672008 29759474 478621091 13961956 135826214 223603649 786499059 809131075 827529115 364154548 262299916 975683737 938017019 495543847 959550557 133194708 989583847 496391034 429880356 956385362 260535181 928544323 844599913 210105740 366540797 206119925 542280107 713864531 325232561 741958348 61808545 305420921 771717821 392945987 171899228 907544034 469065987 958398286 569191460 149111453 322552833 831491375 124795189 113086203 179551573 936862098 98797262 169135420 433253131 528677617 978037133 693788311 309738292 675153398 903894050 676279088 881273322 298690509 390143619 59022235 40648856 304468515 364443155 664883028 549930853 536342382 424943413 18996839 494740668 994134872 168108291 669809852 678142599 145419832 782896055 857694171 82281929 881693316 879345942 368051411 262887285 857383075 914356073 572625576 385052824 670766475 248904663 266326145 969456983 491564633 325348379 862622190 796033147 689791533 380021569 198480351 78650267 804964981 217477189 573390934 651616204 238101832 95717137 182275154 383521663 878613191 892485677 318319943 760306507 771831618 538887705 23193791 481731044 453243777 448335718 866783867 124010251 697240380 985626364 945983585 41321365 163491094 808605774 837354511 853282627 41143694 35834862 931932893 846108674 105828402 357840178 350241230 343930233 453557314 385032735 579968247 184686857 277518411 898288189 944993363 901866381 289692245 820703505 236113776 742936022 121555574 102897643 719462624 818795953 941040358 517962561 860117317 104531451 179084686 549988180 810330429 220228380 438339393 594779673 66337053 396684146 952619850 269094634 740614379 258693516 654127369 173098977 443380372 784162131 71387166 240890086 686028511 213595762 914109942 922142287 956531783 35665515 877556281 528510759 706977819 671112990 46473319 419611488 775644440 78074356 969599667 438491221 298302735 260455411 33270893 217156140 657139556 838407095 486250773 250270286 97100610 992894493 423369263 392997333 777056624 347272780 486403770 315601486 560868541 400513711 90260124 369916676 288695577 820332756 750943786 995673395 491445745 649933456 415284882 119606537 728007811 237400900 558097757 26310546 350372662 443885001 243466685 7512218 282292095 582233809 110298855 231909056 575128302 386184469 477422740 204701277 733457248 963826509 372819114 146842141 216856571 463079238 369275168 505552147 135928345 120218953 501225542 627374090 770152408 769026775 599496978 350676570 6427675 10111086 376987115 209316688 453996086 472970151 69345257 736288181 55203960 179644112 820713588 482848613 565828580 298136328 687549889 151802180 114479188 60369002 151160672 331335759 375964591 520435839 836887905 511892936 640654791 190629798 991783377 263323550 959656573 591280354 614000119 818600599 601391439 843503586 27917286 55387524 316473736 97262543 644192056 224194047 129423006 317421996 707042659 695251585 615558323 247108899 699570116 730037510 159994253 850730787 61373268 535958843 371166625 750777525 900368130 864337767 941407322 892151506 127661316 901063894 335948211 594177787 572180844 789856001 290197724 600098130 697759877 606671459 549877024 194468284 830865506 679300029 511890279 390424516 227067965 127448601 637533415 926638081 710002463 797527667 777368867 623892082 186002861 1051844 227185958 86370991 865389610 168593280 831038848 845567278 922173525 19503411 292261416 494354369 809359411 582459139 946968850 507119287 41646949 496845873 701587571 725028806 28662253 65994201 115453322 255730217 45959154 752986736 182368297 755961616 403030754 812253516 232370049 589033614 813305359 459556007 675404604 531211320 480665638 358959804 229294949 402839162 378463214 374072716 749709882 187822624 956531854 696678731 547458263 850695155 46040955 101562185 575723960 74703207 167556385 543693633 330433424 213515538 149196720 365318072 969477153 552227473 177571587 54363554 141261087 843393297 366435912 669182042 227120969 847101549 28141845 456415917 102457062 406605058 830488633 852166944 446944034 639536838 401362026 994402296 342748344 447402981 95964480 918472304 374622539 263520864 314682288 705055962 477036402 463879008 70374034 299029906 16106480 100461972 205909811 9883918 943855269 572345722 679065960 23492589 419447270 707207804 479908505 521904332 966329214 162913489 226587627 413273247 654966679 627949652 260191894 997715022 75352632 356156373 768703677 302491523 472193588 83385965 7547484 949229989 547264972 930437869 100776247 415887803 883416193 306686057 425771721 679787813 879031779 104837680 703280401 150995400 664561835 35705257 525416083 630891048 198618746 752003709 896680646 853585424 379953361 156872539 703816797 307822344 365545263 472520474 610313866 837738851 408422790 470377702 639485191 955687761 253331922 740261437 224091915 136748114 899463846 649863635 669052278 631011976 754701314 372332678 782007375 271779501 408037935 159939810 902670548 459173032 911943518 651867546 165274807 144413230 808740084 869091603 452235574 26801699 194128428 915065791 864540549 602551217 237959844 504025739 410755329 491291766 96803528 634847244 480556231 996267373 284710878 2124861 479795700 891928544 374457538 114319426 163708044 635011824 274259235 918894943 94184855 186202753 570762488 259459661 330615982 232018924 128551264 635367907 258820622 175196043 550433698 123361170 777747260 788393541 479903260 188502588 132201658 429223139 823349831 465274241 278006863 960577061 467399101 757802562 852505604 841856638 872121988 868729999 329384814 146381222 787624941 423569668 185100326 210903781 535545681 515716308 295439056 516613296 3600566 554259677 691809338 554034263 530137198 469556597 194944156 862556809 510575537 179662165 291779948 186441719 644936405 569786810 147018779 112335505 180105724 852040734 806708495 52227711 720770732 136093308 51125284 360912025 412179327 236225610 424332157 947725007 751941917 719771212 464338302 755542482 126547240 8663992 162093097 656684437 478220588 209553604 371757597 988796124 389215768 663537544 27754195 34152173 85840706 174772973 146487677 265946429 26813707 805712523 170690491 600100790 941805830 221815774 813529166 206501509 458041383 237861322 154226515 62499651 957632533 471081169 818042133 84179772 479745160 832651581 593380560 957965747 42205184 965138157 799278223 431420951 481192052 827032417 318089475 419549109 854321741 317093504 685495537 733651799 122806026 856186027 186268941 917128208 78001801 999798106 123629716 388559535 90175780 130372582 451059186 47808312 601453750 121617670 984504436 81198909 954269250 430401347 891681008 996474433 248055855 543475582 280411735 581764259 223024350 598501210 1313367 77346090 915594713 539325256 810997889 890917090 248027634 997266829 808045297 178545786 849581286 784191364 567105321 939757065 914563946 18164506 840081729 516017695 139782175 677102516 449732956 94051424 107503862 341413963 943042208 208076069 884889544 75970294 789840327 107913893 526987855 643670045 37776334 295098919 182995300 701290574 186016009 431022934 551073754 846577657 609568719 400655040 630769021 29190391 192928456 397849318 47354896 33010184 913867012 39653422 710112699 216116319 133704845 670132913 557530281 929263404 730725333 294936176 857750050 373082011 255366420 384737904 16752055 145659106 679836823 52263707 846949679 718369183 483286640 398023433 564946839 945371710 651194824 48232211 974562101 844123279 446081528 21916996 877133463 212464892 61570418 439762513 428581210 47791614 962411777 838627843 829571370 693137109 133564018 539837771 66219119 241446790 924575674 935487526 387105895 456928848 987751232 86571925 27814382 323554223 484595357 592761221 268925932 135790180 493509783 96004384 832429811 939591311 117921380 562079625 4572554 32008149 1842137 285670115 932316114 816770266 124297957 614403835 362423726 110378327 6757957 281159197 204341468 931333631 216646722 591447362 240778830 56914305 678019286 268593212 380468527 15130995 713870784 649394458 3437526 207380566 745398842 835867336 999488228 715836573 250463312 4060781 600361073 104821801 142247248 385193538 921592066 266545204 852113725 284015791 229439882 858871681 565174987 433781349 642721663 634338060 25228710 883500493 691252364 555764348 4610056 71720890 423411694 718480839 573631700 426849219 778377756 171546893 115232907 777865984 887383465 365696218 634443116 340260889 470518018 776690363 577970778 244626435 895751919 430084502 528642226 125191800 141472535 946333564 558973149 784194197 580671624 436718210 520211041 124440339 844998909 524821096 196161229 268410602 95818286 769792928 547776173 874196042 941339820 663009079 504578377 681239636 881221648 991537844 874016876 204256018 620744559 451987653 448882452 516496477 734588507 977524677 494204628 876061041 776374593 53177776 660255237 209562568 342412338 32982630 334002906 39927598 557803725 530164134 308338200 506138363 152473413 856114372 232850756 946329584 371639802 737429132 480085571 105377801 581483327 354102446 309633818 202227885 658606451 758516270 571240713 393194957 588557298 65445341 121772349 364931890 971139468 782027585 574494457 166068157 815010214 908497363 205995755 225330291 291177848 514333954 731468653 296167613 222964677 964319408 242497196 447120830 554264891 722582767 552498630 135748217 929201564 862132448 190492454 587808014 620648717 761733166 833519322 61722366 679694858 955291670 426654256 650834326 589835607 853665064 816902482 257362172 614678778 22898236 482692462 905856626 389748541 66677466 54540590 465229569 883513225 297037785 912350398 290294467 872136903 464849028 278559036 801338467 179497827 469051489 241662832 800146543 83301006 75182154 861868908 762995864 882990175 141039515 266346541 472825781 994704579 935765374 730187953 461899708 811179962 65396766 220272685 53444854 132074232 274813274 518674423 868103808 571851059 431024820 158398275 296504313 748390199 436957310 97842779 927888025 758525150 192021963 580550919 841826155 119720468 294936179 457338370 2710642 435975693 576201262 328052775 283196623 511966636 910757079 745096331 175662949 976153844 965369015 229107802 960744427 92698641 747782224 681364587 664549699 31323396 839762861 961054011 779713594 129236522