1000 262143
224485016991701037 288836471541711053 342664574046288584 370246615337682648 659925277673912729 865408506556463036 596258280375576686 228401269311026832 860926136188419236 494735617378227994 990608743062229077 839823749572584400 83059001564237830 377470241132549848 889198089821355988 829598613094288264 498035755781319871 58929557710708073 241632085596071254 351104498198499136 167417833778909280 869533855186751116 740649907302710286 901507513952529122 520350675622788681 710732106917248342 436306509014569766 576743921198948240 729721936043436564 306329044013307906 841485491098109100 345199766446123972 701254931633807271 598019352683953814 216130532032402132 906068000447106462 954910354324852405 920143393570884334 462740531057951480 975540788309727808 608682678238910813 102379399594059415 164644310353376341 796328009653499413 899106610512079553 837637653096493277 774255570123055934 317323849982086947 139211079520460334 154617042796214503 161926586895020507 743310862906437536 735590261102037807 587356044977267358 800107287256179951 736021858005581786 727370344750750792 684451861133260659 503389335897784755 683331546585704184 720982841600995575 355366203986557771 678625563641089582 354631169306967555 864833857501926465 144897590446629193 223522379861349090 5117234559298675 742312290783426506 521479161232059708 371867047595047978 367997462958802354 290485356252201453 524254178188123571 268673094561949827 288644279113133091 705291460683607146 631239101680601331 736647808409326385 18306755954393769 184821464824692634 11688688754864316 768146825587313280 760919203275813293 74567239959718314 186556328722878957 697042314954437819 174832008901561180 435010805159452986 51784742548251376 355963137711435500 490906216422343516 761959801091988716 799938618075416066 813856178723667558 279748265965796488 323696470206760159 414186406541433986 466349014154068470 900311239499497264 815547911940139527 833171360042557752 796995270484317784 767909514213441036 818748826051751226 389971900704109630 405605964153306827 759727159367226921 130802649174484808 310281212283824751 289093072513048012 665945269913788860 763151931688287265 948574093251923699 773302519581634464 503957118573762266 754191482381676506 771611054845679915 721844514205130902 776743318539543837 723392445094740427 907946118499650930 625897189751765754 950845987860801531 192546176081927507 96333795325251816 209877797051238544 793159700310229624 116431630172574299 986047882250929107 980148658858748584 635367673421645992 622800800713327133 234632239888312096 100306714012078315 434205466330794591 179180735414717961 394612441408799389 113300824803432355 475270531235633574 606059339840552162 920293644224437764 445197862660446803 235019703776128893 408562576217560449 56346636228204034 3502266922280515 889343883667240468 973492587938623866 805540773462518863 570503186109042624 737998535648328978 407205661004845999 400746954442032737 452066928906869711 260150666892696313 481392453904755266 662679678422716961 840211830955699425 386096316497512818 670025192786794542 631634345172320871 158845089945385769 805927624639839339 548049015082993856 114274577842981061 771241241811160985 340492183577338121 913289789936434444 98655557239826346 821940822972344087 229624491988883662 694608924781773632 682422779315763079 294609125973800159 510321579643489954 190609168406051001 559539624693069472 46605517336202113 54131845992160183 610998169701563633 823509937503006013 880839554613941764 897416421825096244 394222436971386876 110660601620588276 655223585563837756 540205816780165929 386999010909886788 891121682421406455 247042271387517170 765516836352234912 736077495821088710 970650074064575249 600233435078273805 80658127887802254 129807916748279459 894158909750529276 320697766353239395 78730852299489518 337937376789200708 419084256577515925 311672013947146124 441809622476780147 21544144860541241 82392853463344054 789323302172410843 956879942025482363 364202017583472329 816373029580905785 856236356262118459 983886868996165421 387896163838914717 408169795358301981 174430935514306296 33960948111455877 184231717814352535 604274298232601967 195813113616918852 704028783278302830 547216425002685450 727595313496548753 376062841316256926 889200193534883905 273125033335023506 504746394003389583 374718913987810905 151556559217129681 338606389756430457 268322861453767363 194406911735085272 176126551873773071 877626101045198763 386280268683407347 735138360589481773 329893953280777993 434836228914812240 79580004442573541 802872243081769169 954821012996603461 581917483236328638 80321135268988852 434095480201858174 683350616469278336 325541420816391249 533441758467241270 825088736733690694 262338661733877889 394606686400130717 691315138087909847 248023738814046794 659807846706708935 768803103666200507 732652795359561576 871162499944315875 739278923054276059 497878861423118253 98995307448896097 976679262268671296 975783676163015004 437482937975376337 537632553231394214 840998015117695878 264281100924537153 757389390558246171 971964967573888559 312512246437785990 729085896012816710 222932342364777655 368484011301174972 478710352215106426 494080096018179906 209366622949300768 466540315237979661 407651437814275324 317936124691369696 45444587915574571 940865699264363156 788712159931267618 823417240697690724 557637172062763078 248219210350324384 737438927503196599 159435110629436127 270158786878511784 218098863292770694 824534295862204863 693869164925145258 341402743210895753 357940278996816170 343334133525972444 520751206452883975 796363486714919827 939858845522702347 806555508887907217 738482791725588103 767836531891227760 364654272753623056 94970819438237553 378696394641149541 381547218979131997 722396502848486622 588291466993371214 450632684739903103 25442216374761770 751446695657266345 829246763927467029 749201590951948743 933696477896489878 990430483121577405 524822135571473491 904175013141287928 325169630159014172 599822120906154997 158262756292266554 129252561296914126 377152189927232791 563081799588985932 434613844588740322 231619663527958091 642492878441608262 429273613581514115 122173089487630504 198373826855418261 808837522965318024 355962124754181403 530739834710624284 759262519791190217 148192893046150877 30351726846094314 42958002630240766 181231886559161106 219700673624676686 934068504159063628 32147896246551876 633089165296669712 296424687632307598 706181070808011513 923501829057614121 204919457232385413 191321902263590030 417008840919551308 670097125107450641 39019278212446089 384544666422796702 124884389980071762 339353468538965115 491547050631934942 56970155663962976 515645945215647187 217510850661040577 425386629779146624 774209521583679187 106005066299686706 262038357556631565 195690077346122051 252948678944245990 826022511628671076 703521302045058026 822010923040799049 265753721099908217 77789153193304087 426529795583976487 482668478414668329 154334321889773055 410793385318284143 685191567710793627 17223987005555102 421996474918332098 608428688804673933 855482115318723560 955129174888175536 430551490775348052 925615477344611812 212543634618807070 438069920811377465 128186050877719566 118972833848088974 662251439800426157 741709886036224820 272757925720099443 321998141459493835 245003560572272940 318738549736928427 534373760257341670 977312024342097318 963833787628466624 351379536552924707 201804770078977494 33406063641991836 404978422639858229 253205713865413959 468584730889580790 935073608355017680 918214636954366567 836906287892079264 795392405073176636 152594152537926453 118682231489792557 606330190681394488 319290933446581189 418429813156063775 89069701948838996 875364264167895173 800306165464256832 65159772266672621 71767947015701151 574438169745580971 515028763287789358 169114041984958266 618211020433860813 334966733224004940 879514394972934810 573038016346389421 319480079113004080 166988328982178000 671720886722283702 912453256474249238 487581447686085154 710855675641689791 89665062401706691 548816362334092486 850010850612979377 610362402403242643 900905500824744640 947949332111139222 837859764111969350 213544784060701562 631850966375112402 629615227042787617 910887733332901773 884945206829044026 587157364830464090 771621077689004579 24479826852562747 40343633266225202 575091059565797770 131795179430639355 908040543982758245 921662668997599239 173723253660506599 493019424009776164 263516300751223029 827841317625201515 45180426821988860 441235830145424521 862541809662579735 930573452054610779 306357995314074770 675273262781583373 448932039517043286 347247653586456544 93448898750814299 174185096323581866 106920363531396791 981102618250122105 352386243800216916 894116437118012688 3334226171793203 735552250104386718 576210164134034108 239977017729590003 6704873894193398 784648597203064432 740150560509601821 591476174105030444 394088542646851348 974976527601535074 308661605961905852 453757537669631618 380279708896924918 172693176756832485 630468398622195809 88283045288644875 850762871329169119 142721855590136919 193644932038769462 160186441770606598 299567702013221439 999348155363328842 412534495111328008 824957455331845223 238656230144657473 556201214555046851 435443137806946541 1 395857577736486369 631360071133708632 183577096034779906 293077199251446594 475818738043757230 795238814222402418 148946719147319476 103794555143604771 78933606962574944 346382074399038049 250760509076251124 604644684992235351 307491781638699818 742034537531334167 941124424503757259 707665469871269540 26975968522700044 890726860933266890 131460891107838621 774521628512267390 107430014074186852 688876219054791864 422382608788226676 963350094043656573 493691570339258367 81190452996518964 994725681610587305 680460778939102026 477551341209495957 112315930686917856 759115151608413549 294226840363659316 994207166949958007 884198666177786265 641578433307289070 174733766507236471 573139501574185425 940736714928309741 213714333536297158 315092982647120400 770451332243185740 171659563639960505 465119987137018529 739044635593684491 246984978931898481 5973163796616083 506538705381305679 702838794563116531 476948945952382619 957927749937904848 321132529821328169 489158239071399489 869151007850017112 692538758018417450 60764497319933248 564533822302270639 815362279453335414 595843524606711394 586891446935063134 499141393824189174 735069529646700737 229200221974494039 891050407325538498 784855343034671886 659237987909622832 160812124229191461 341296158548753021 538363727019050747 862041219403148388 921420903642169452 422665716486562503 797776488269270014 375480440389263779 836625309727848879 520390468660425508 226355739990158556 671086939119785822 865781847485350254 233908661853121162 34297617138233604 124071035979368932 996076018967979715 654564790464757106 202069082690777616 785344541167007970 462039448875055058 521256606992806367 498303949845638390 375953151738639807 855638753656872917 571590040553150982 907672817689745682 12879673880793900 951706018840869033 669858097378050439 533007524902384545 683468527227469893 630762295229406858 661471784829033866 283930874456344889 344191868030396944 646810214596202924 507963284176707400 772921039181800143 937009789714375063 920239220434419592 588477082567688014 503900944904976320 280429286692074970 430104841336382523 703192395911624893 483199067262057098 283936699192916751 380590322963304607 480300697509596183 571398293506616555 511267227390166978 874883443730388642 430261640458620305 525805106228972766 315175258341676268 269624738091679116 478262993398268882 212612482604540687 837992717428005711 862511610024961530 283667117174547903 112441492420893427 409217254270333293 722965219936786763 805345385517903311 432969223572876438 675672976404705049 464522375761289704 273088292618132388 99055533497506167 26254703644965148 490398919402628900 555317999638259835 426697565763972316 810708985467502227 480375855411754286 847077920770207288 353750079918489544 550513172522901464 8558926233564984 556480356365842141 182019242103423783 894840064341873841 497530652000625214 941769267521596772 958697201423142629 229710257531849425 458541061940828367 293749996470106281 893649999981501264 279312156165407084 913507355445679057 661910888966027550 618557076841452223 170415743643506152 443277696197784418 635942374626155768 541688947586106177 944575405690347258 329340483225760507 764680406560653499 321334476126841279 442068813889976083 543047931707437470 487387958049842612 316336993283818762 251002113469011099 392364480128493437 878095304625046075 295490227159542534 217147778098742698 439894329060532325 790900342214282094 377099804635599741 486133496539260789 954040480915531028 115817446565960467 943518299604899944 555044913825762586 655515298734845103 487252850758018053 424176853018565348 852134915690806594 280752460606210236 649296772275324234 653008360663283220 430761180433041804 835548511361328723 583116765118497236 616719785106085629 962826579097412568 197511345591763026 989433705567520338 368156034470955889 473265795546122841 637740528658769318 939258805665862480 172463277554797698 422392151152628870 727554867331625664 755151647235367348 822686764788315008 436286961202920797 901965670345999928 905445320043943398 559306589239368324 520307659751634724 370552339306523112 674803099069695985 230935909370165046 614658736872446478 533510427944140792 544232373163215116 544363876464690820 940447726294170724 2781492606120074 784599179227681016 496521539617851406 767896653906693987 981510806990794923 574151208508824770 57748048032471170 881063471414454847 768537293639884115 323989010201558604 942482082785979321 433003563614003087 732847669436255613 591563501964613974 267683821024286701 52048334472989507 570943443716464618 369073949404987856 821006853560854823 505918540319791037 748045592635552865 81941090213172803 441213204553436702 554263954530725437 438912662937064364 786863956039017755 185331068250491517 710372260759823940 545034694902290217 774380619712340087 532611423184741373 907132169640001967 266571866445111291 857496404903631421 357504525124720016 486805451534747069 60466150804502221 679960592581009484 113137859249483057 123363600699947837 510935845674104313 710875709147650696 244363791781609540 241785498897571736 697771857130732178 363952150703963678 502488302434191683 135409862576478225 126453115989285733 643250773515701422 984784050715583625 38542173131199774 228928938100209465 199949824210960349 162741667151046373 915727120969113479 37901213202681568 676040294392775474 801063845973864524 890362456088488397 156871087860037288 945922862222319004 175384848251717314 500812170548152997 605892647822261621 30464603552955053 390451865016297285 708026679038904248 808077880154982014 716560604824813308 451046975914843193 348101637504085250 523561243560269171 378377753750715755 514313288255077308 698308682089408779 324183796711673205 29120897518892208 640302461595257533 355976491448145503 869855289498444556 162902834205641691 428025477422435564 46251197682859717 489358296081941017 509425166490543997 527000146656323701 395566109753260695 289139852343991694 98844395552950751 970825663518171700 929260414427246049 101219646966163397 984652925678096469 751621012720364975 373771496100150314 399760907931379346 115818929784446327 97332966520602051 792337007310124379 297187077732939711 318008452071941461 655945384736541048 974904608682210875 605575584903488744 284074369022408362 357076667184111094 823019177924684015 309303346425210793 215199082492205346 196153492612077614 61244845284183379 108316172644517981 119567552868541123 107378336785340431 208295764357504112 343909647949633684 21106034497951903 145948937261132930 515384646317481166 452384506755926899 174620095572882410 643612779368041255 870917929193022790 876414461659846376 817190761388203427 444583131252772745 472918813148520895 924179813694556500 78627250257799006 21807934457351196 375653464619375557 489793536313975552 220519667374667277 990722943292751547 308974384729135550 493967883969037947 663859562440934609 395038460283105733 861593892195841757 9563001071613953 455613941231298266 772298576557862635 820589699894340915 351279704705684306 23538552401952808 73355504937620113 727645738532304934 710204290650790621 526697599380242731 98318328617596693 361909379900686793 74666777339264781 926667805826601829 937166067369900662 373037576686754870 264237033572797408 769814871883095785 768719916993400275 746690727323600050 503137961046747846 681531343495900241 795758333731316350 302420508917312127 632309331970968354 288028820137048622 546169050969011841 686868889497203236 950618730281489668 484418057072799946 996645162427968892 386120031905977994 239587226306337398 248626674569760250 984616530815994072 296098374450937791 94150345708966836 530784452432983012 610688063529939397 234108368816646556 404565741207978582 423671609863407438 377140511475829702 40334491564480775 210878838625491740 669533151390533037 374247054659366252 537379865223713758 819927567804787316 716526402090711250 615864452658614606 459673006020880121 329194374228620008 930701209151942904 407932690870026532 441020572952637123 307387931780365737 966413846386120202 430175220225406343 689640438640230147 543894685488997399 274920302033723077 405443709976262236 575897934911103320 448887097176337238 995512352678180300 773471849397714123 939431669254846298 268107578228985290 102501780557564647 538913350328187079 145858574190677085 328695860702540188 125458677685496955 991789885214446301 935190861472315502 40785435310671882 783299261004375019 683816739873646629 281365397560821799 250148711625666789 387667060444864220 353994943076119977 940323532866880255 589164983851880920 514852459231838359 534342427363021895 542984792472980898 798704331941786743 995864762781127355 230950475203865466 901412698374350852 913036329846804860 592848942923063374 134783202531585134 301758474671081859 609801805877670960 271080571138382602 827251642116248310 985992335423224640 492496580100126398 602750271900901480 637249137242070694 935851490385831065 621339555850395073 933991083992661889 272180955440322582 824275188655753720 617230761995064289 672349477799682957 944554706445947087 892869836060972283 891157647417899730 358685828110509774 379720742688148056 333357943414949753 364218719874949100 213205725042933484 567946001783033029 5255280298551439 802550083086075240 469276989277758297 120897998295324211 482871021304757722 245051944945010720 355062703522635105 515886281987344869 448379620836321764 744815475486991570 152877890057477319 680155138851186294 517366854562671931 702332943749519813 194522640253016739 984510335274350618 348482638836683280 29535160536266487 958562840373160382 941933093373193755 11286909762303867 955944945631879386 37322055631717201 969857298850000443 28219659204580689 725832386965766852 922469468651898002 6266249981681636 142390363745936866 266943967980782370 534680497266430257 222109860554506276 347987542743870716 638709638280722630