175553649 105492555 285839188 482507605
1000
213319641705649756 254117911465833481 493468855017259403 650709061776313006 423529852753760509 940805438067809878 866560929827714465 847059705313322281 84705970118285004 502284574822043453 982666635682540022 139347892627599237 626147731631714357 809393338314861351 357142110265232752 923030115462409193 389724841701202083 559136783049705726 546167573755851108 950138473541076561 135606930393044586 931765676327162113 254117911526486736 158326112002915664 236065744088434679 592941793523578690 677647764113176786 169411941088615649 244635195352876427 508235822804525772 103060467337308294 813928254746967932 971503483258513968 571132089796656572 821384730879642535 559136783031766621 20717383197662525 144964704121297201 931765676031391161 360000439129681015 259344539896086535 240860629190738988 847059705174038045 14179611180659860 592941793940406660 508235823670500973 936934029809520248 29252879356090405 355962350239461262 84705970048824624 871334215990777618 27680474088290170 308548963180817940 695220162878930349 762353734959188152 931765676289327639 686622168941348702 933232259698809212 780151785183671893 815213872865612855 532910959625063888 820126531012413404 795208239017933815 338823882125328913 507150569353143858 270018768013949847 174949607 847059705712005908 571092051059081762 423529852635162977 308268657434848083 606145375063807744 762353734501693977 778463074815396788 287801967739702760 762353734476840302 747850545729107179 698417880704470800 592941794056064215 598836404921264278 84705970157307453 169411941436395386 711969671965643977 643842753304745152 220312900638537627 532727857082171023 734487781875292253 572983093899582551 169411941013263167 59742066852521004 469441831581717023 508235822761632826 9183106628956954 827732403365299715 349783856573363272 438709340704289856 951402499308700553 767240082060210978 50900959738518374 389724841830706888 762353734402917340 561095193119509012 762353734406500074 474897259196717995 914727713737354899 479015564140316887 847059705313322281 330632734048945043 886520958965205039 411978001590466750 254117911593996684 128394278563150074 559136782892421045 803293048322799235 677647764088389876 700305637185673934 92622791616368151 611604671157492710 677647764471885683 50900959575873171 169411941090225156 641650095440970954 813254694643702410 716469256896829953 338823881987120987 896169065198977302 854878275915016060 313499916515899689 297010284270270838 677647763812281976 268710964282410990 643842753400724948 167484345980395370 84705970048824624 677647764250657824 470163576026789283 728548724112370182 338823882577399123 592941793275939526 790981669971102717 169411941062664457 354348318105680184 935180074325387518 985183830595906576 847059705662896662 217901904 390277139492028471 931765675606385816 102867261337108969 995528682187849821 897960664905946594 84493755966531548 690506727508544830 221106443546727124 990489565281764216 240103172000590484 11915043825857338 169411941064363340 857944910899506161 853747746725569974 337688510367769588 189643002965578133 169411941443070762 338823882216069938 412472877775346860 423529852656661140 973130983489818937 305018871455709042 515376360856153097 168687304726151266 382982337631206821 220312900709688133 592941794027096925 862219053995352999 50900959843417054 381423512108046097 285921838295068141 762353735096322586 569479555998886632 897960665000611000 724314744979882593 592941793719325597 736925830406567638 84705970693944273 687983695844488858 987440143756082491 999527875820841457 677647763768150220 500243244126258766 508235822874689196 617743658961399956 169411941545172061 689453964347863575 137613736349487177 957462242822747040 899582430171337029 124545514483210539 254117912076504289 868216170431534805 302881208077286254 443268946051024359 822022721515165360 742035422044240507 84705970173682502 888841681824075541 897960665175034638 540338261382671079 423529852582189144 592941793236817992 569249021958042389 462595605 33461722913920940 403643330682905635 169411941062664457 55644657626575873 931765675922413537 933937126065427365 329898115126893890 23182602763383491 686955563839367537 220312900679116632 610885871322060569 664018600158319990 305018871321914729 629323344818854546 518802511973314568 592941794097711512 310116481076489544 828124620287191275 335509219374249206 508235823524607485 203975173743513310 305018871432303825 446677754651290754 982666635576963740 169411940977823107 508235823187993369 693915637465270965 667357517561864824 587467057195651488 744229619247721715 252729552896506574 412363885183375775 592941793560612940 986883949519677311 154471587644134582 254117911704460278 423529853139168745 254117911735647422 485054350310772806 304353375 395302099517644977 360020031081514663 847059705313322281 186886548427108817 677647763952046000 474430812320343790 847059704873754948 409941214148608033 400951679271839262 639992450744881280 847059705014403371 164741029804669834 645439651582901459 435409170591456941 220312900884747418 503487042205511179 423806210207333053 446426455759654798 324669222860446418 230744101647872463 125836127061681065 338823881866891183 508235822732625565 84705970531332229 832547665474542586 518285019624773966 762353735264497657 704753992151042546 728548723950616727 220312900715062741 897960665060956003 933090986720922083 969074430752733391 947192821053209178 983321247361450913 97315299918037167 71635942524267258 127091013451907889 643842753443191177 104506455517353872 168401059348498856 36102193671462101 878473570415117430 832741537164242722 160877084194422832 814300620588969650 169411941084941817 37575606925776094 338823881693718445 84705970462439877 847059705313322280 119636486447741334 508235822946231437 762353735264497657 868041866971766581 50900959861712358 951917521923853206 559136782816607045 20210773143670248 389724841747792105 762353734555929235 493842697278609234 61663361401507009 667829822543557100 389724841866046189 185598912227147247 516724802401271879 380160408662793267 769773373403453488 615318593728686066 762353734677962588 813254694462843791 50900959770125218 389724841844022802 609732781803095722 592941793236817992 728548723826530995 338823881642821308 468271552567538024 995416002186854172 253261156531525149 880339660857333251 559136782832351601 982666635706066483 369613205252600743 369867627886613960 956242430677813238 523260557536485643 508235823255683836 84705970654860832 677647764662228724 398813187322174730 84705970444668016 551038162335692734 931765676272865655 813254694643702410 592941794201833201 847059705313322281 259534186359621800 677647764279284946 931765675844654508 949178020475049487 573541756980227965 643842753295198767 107320467221527668 106233296697729422 63805504165520899 762353734781990052 132154382162683064 592941793394011605 592941793877076086 847059705778165589 508235823175505856 552182886928353692 905415839603390685 18060330480475566 305018871169869855 954070002429781784 338823881701350565 745189748866948253 55949361179133374 822546951862942763 386952474594788543 740079800529564762 621845904538088225 25814699476467593 983139264744861456 643842753570626746 921589193833953199 947264962001748856 254117912076504289 893963257294416991 813254694437273333 771893183973445610 172282842012110257 699405141599622210 169411940732957196 592304121801217302 588839089464370671 643842753368375954 1621174406993870 194351530218244521 508235823187993368 389724841827508350 338887288356274888 420219052901290075 947896390314734728 123175035295519103 15574577819800446 84705970531332228 559136782882531368 592941793261917898 931765676048912587 592941793843510991 389724841701202083 675987192615208099 423529852443366587 115353608238372261 824571882835985078 762353734354853093 642651301772659402 338823881642821308 319414443753578190 577903850399784022 338823882261014312 226797683372034263 559136782873359812 608537162791825491 886617498590609827 559136782988656877 725819530535597645 175421607647738314 677647764652343997 990072310886667931 808220967647535753 50900959838252635 314103668090375922 538314166105076328 124821665356229959 467740634899838515 913294940444426608 947737070697916372 788122433643007792 356408387334015473 383339815976112788 982666635420527679 958402885499626619 511654994151447434 976246560318606029 482507605 15132719778891561 220312900798168333 864052226784413411 56299831921127243 149099572461092241 590829267342932077 389724841804345587 400437331570854489 811014660715224878 572398277960543891 808929346126778067 254117911197571529 674726319139655726 531712210926456564 610695241086399341 681172584351523949 626039926752717102 74771299136907089 643842753581037954 262388787368228979 559104030630146743 728548723907148541 237165953089735090 338823882099460232 389724841725029662 628681767854077767 254117911111489080 728548724005263445 305018871455709042 380560058412089729 735732681880241359 389724841756568413 988353700672850626 559136782929175610 309260455401550987 508235822705485764 258511693878698990 51625136673821542 283083021444073206 278657926069216545 87791702201813019 569280493626383042 98657573412359092 28990756741528292 847059705307226865 547758446130808472 976668569817905399 758063075470151162 126435638615971264 875661299321586332 574317062943272378 499148687436330303 271295095472119624 817818759169792870 17344201142955101 931765675844654509 413021512212634792 172899934991447270 762353735080641745 371673632912068727 628847641536100256 847059705496961761 464799705190211265 197741982329048986 423529852457784655 677647763794825005 897960664889195451 906432681711187457 125937248738797951 508235823187993368 982666635479222473 559136782763866539 51586673853721726 963662503073613568 310627549 847533938395404135 805946243341373173 665044166818494887 929407430666693558 24512692964594341 762353735181934355 84705970482290927 607092623867905781 847059705795829885 464959396389669670 135606930107205399 401004808757717876 869650133676118424 171485403160144121 643842753581037954 691950087247928889 982974660358769582 84705970960645823 728548723994541857 726192632250084891 423529852177598396 847059705269613253 366021691311139852 592941793236817992 474430812518373498 338823881642821308 169411941062664456 169411941062664456 316901970931424134 75316895576276048 931765676247723801 635617197638260742 792623300418646217 690269104138422308 847059705795829885 169411941545172061 135606930393044586 35634848385441620 508235822995685292 389724841987041270 827269864136797456 986344324762407952 169411941158195803 135606930194542437 443254860095443493 508235822791603724 423529852220193945 508235823670500973 666656304217254080 982666635706366866 15702819656072556 323118526159668785 460705632194461586 216275247204025115 831660499939675355 599421217985028343 847059705795829885 931765675489262354 784840782654562383 870843404725727266 567857058974967841 338823881642821308 642623656967118836 423529852727759108 847059704998522372 796447133009504348 643842753489398273 474430812232534311 654009446072616471 440145236721427327 254117911593996684 723357206410898535 546159800911552452 686828693309082775 480195442894472817 868101869077749236 422464504332769835 888452981362200986 168974059752795389 667631019760145000 751578991591849242 171088055233086441 220312900819355737 565850238970815036 990191166015326967 220312900922674792 303524642583721064 750207617406932795 592941793236817992 847059705248103911 762353735187610386 680851200273825130 148777660858474768 762353734731826439 863527232494549605 36639855357198349 732555508759944212 818405816499347303 29891704632900515 762353734299482448 981384718313524899 367465894092236910 254117911646189694 326515398539423270 977843044382367736 677647764604662724 24365251668211675 728548723826530995 338823882125328912 941899206475881534 7618396531668270 743470269130861825 712666125009200835 129933260442753789 270820564732806406 160986701215451608 213649614453759712 169411941096987362 508235823187993368 135606930332534859 21416800648967461 350234535844041679 762353735036054006 603330205854043528 485608182731983744 957107399383439303 899969470804867427 712805867136918355 677647764032108557 982666635545147642 254117911300192632 97518318246992579 566156868306681474 588973025798716100 7063034856046018 721274558296550427 847059704838032879 662364790951040388 762353734781990053 283845452707658884 202582678144249732 423529852656661140 884877994931292536 508555441536278845 968643798198346393 28266277976859981 123571872386789705 345460951312394947 455814611174964150 312397201229587273 847059705313322281 777323905383243852 169411940914422461 888083929047418679 759165479413091257 84705970862087495 423529853038943295 254117911802055192 110013241379002815 900266818650761206 996613208011787356 241649124250832090 303691605367219438 728035930389542606 816974192581356955 423529852656661141 735244340772226918 220312900776663366 176517758083634406 351905471834905921 908059901763012810 600384313333925737 992223077591861791 592941793714421156 219461819454379340 643842753581037954 328932429419591227 248079160119775448 305052507543361198 371755856562167117 84705970123312755 817581757424213037 740301376224514261 436797613988414494 637564730252406287 897960665159430557 872562009332526352 135606930112315443 389724841701202083 677647764189044129 647332661115909927 11136748380852901 272800141887280674 508235823498902913 657177666424085351 620664099391995398 677647764427074821 423529853086931119 609295103274463136 592941794193057633 508235823509347746 256111883057658415 370569435499998793 668312371019774392 122741259511101288 768800948865503934 275519868379003924 59698584380750860 787831813522425032 338823882607836517 244659529633555460 428865448498428243 330517092568254977 982666635420527679 83612905953886966 95962612673162191 877180190927133546 319416263408900863 477482730383187306 337577934426539160 179007782555585574 769504072398890048 817111227870602255 847059704830814676 603504939040482818 384651633736750962 338823881642821308 420264724143544062 50900959705620205 115387779437389823 750099664129507466 768965660750861210 677647764059291462 982666635572968510 221947245838312409 829450027182472245 242106665365891761 613783742334828676 559136783049705726 84705970531332228 80255823493677762 728449112544016769 253873791933066825 406227995603937638 92426370671336730 238732687938214210 889296369082500082 389724841843356054 762353735098175905 700721463155744860 930393877774203219 393627677014313349 169411941062664457 389724841979524761 355584049902749022 906273937042890206 921073031323504449 835310312683832436 220312900901846912 677647764250657824 50900959575873171 423529852733531572 847059705372965539 604180731938033359 577054321297865171 963618541323214414 762353734713867485 99182005916555394 795858454913607753 577307177478235001 813254694615687951 784581148689865118 423529852174153536 254117911955328817 26221683273190605 471507365773870248 935066516451314816 233570163595024010 931065849160936480 638167466865243857 762353734557200552 968877161882281762 982666635522435361 501303800479544068 828796820890399835 288861240 218759730370884852 259848201908606013 129596602623276617 402944325593644888 254117912076504289 305018871169869855 957563246030725029 731796927237468359 680735448146908444 677647763768150220 858157600043760118 452987340010685265 897334129749273877 142825436772553126 338823882000316902 909395536669728048 884808112158924515 389724841701202083 135606930273451488 847059705758154957 847059705313322280 913472217676235280 144562706228024264 797509080619795612 559136782763866539 46219274170911861 762353734405426383 169411941266509859 316786737932881300 77969311072741437 159160106321797901 50900959672412832 577795232229017871 357374391702508743 906561393907250490 813254694485166558 977952772065896524 987903525242127897 931765676327162113 50900959861712358 931765676115498727 266123572580410468 583388888132067717 643842753512312248 649715472267470272 324827829171140859 778392167427796407 592941793894801740 135606930244164817 338823881695130581 943569933385119930 309483035 948711209144927898 132549759674065881 508235822749214755 910557185857595853 592941793667751397 948473705524253984 21908634182477476 673674457428241510 338823881642821308 389724841727184037 783233667071655398 935971115246849113 255368607755722617 455369960100985512 790154817634890382 592941793904813213 931765675844654509 867465956027098286 423529852656661141 542682774301113111 982666635562664074 72492163205858628 677647763921834761 84705970851987845 169411940696507141 254117911756408843 498809974015891059 159708460826124864 931765675844654508 605184292233359267 559136783049705726 494552813574824496 244852855549001619 749902014130101532 762353734574836417 489285657010171400 931765676045000624 893862956508535220 956124010498872458 322026156211990357 559136782868663256 789496881797778545 508235822900729865 254117911767009540 559136782763866539 50900959581878333 639281018947752086 968112188788373859 931765676278068022 371412009097646388 84705970048824624 486105512412771228 84705970331319905 284612857178204810 733358902573523872 681619537181397844 458607557713238545 914072641754092377 338823881642821308 592941793850283994 447868813932999181 423529852711091405 198490936 374413420539784229 608992010648368867 508235822705485764 592285411486989148 822657538918282475 756508146651824931 423529852837083974 116998750380506265 897960665175034638 762353735152968944 961303118086380368 865842214462089071 285651733396618138 338823882151062875 931311091971067603 599811928402314224 84705970531332229 419647092563693311 688884491356913679 497815627335544086 508235822734320608 847059705642631490 49531801786016431 976943253628885701 165427149343696541 299405782517180449 254117911111489080 904542521547170932 674977448914233266 242389514915434306 559136783049705726 826687543279331920 813254694357863223 423529853069921532 393454475455868680 745036555864742438 677647763943690246 777482807179262423 808891315321434538 480809753312168183 559136783010002803 184822183547308372 559136782801115337 614118890705785842 886323218366634050 398617342310381280 130606935400240798 559136782881331747 938509580418096829 169411940813604003 254117912076504289 798968207553496205 592941793986617506 762353735201970469 982666635480614097 822069073465231214 918356911613746368 847059704860645620 508235823393057789 663269761829975127 85429908369820795 982666635701403492 931017457300172911 10259934596031690 643842753511545919 747143282481901137 982666635420527679 15403164996940858 937011791146140044 691494724555770979 57697630696023603 993753387131697271 897960665135856291 944990941023476128 892576477453397876 84705970680598414 551673433778466153 508235823636015177 306779863708330178 423529852919423484 439346552035493870 308510918950402314 305018871169869855
