956483800 383829676 827527971 827527971
1000
714843894 552495417795521886 243262629764912131 791517097480841830 791517098752767767 130332872942155143 791517097628007710 901329471687682419 973289471552472274 235244062471963867 791517099135897771 359255921275899835 836380860538248273 984257309880198383 269991655 351909799902074286 930861234827054116 827648448583497072 791517097945980125 919010706828101660 317629792975517546 348988135738112870 535866949621589972 792559545582224154 817309132684931087 413509702996176594 857595253247717052 769504222725675478 917113040117872953 968712264081222903 974307972881563095 791517098781413140 791517099116739925 791517098635860607 653699368791926894 800353816125654355 796814907552872670 791517098308369801 791517098986448985 826600761492197253 791517098575064494 747235574705576386 922453293608029715 931547377007400368 502023810797790277 791517098715879999 728709863358350886 115543399309329787 791753026938522091 791517098971924476 973729089309249162 851360267635097835 971579648150273268 265795902989472957 414098333281179072 930204122014998115 975058133922583183 402712886483358784 840796854879667473 3749873307447210 207326562754930672 994109111929392350 791517099135897771 791517097480841830 977799980962143748 791517098308369801 866992045487237864 791517098899157381 782295232073678116 499237151739913144 791517097480841830 791517097480841830 993703700180265535 791517099103796141 933078661767434607 825372890384330931 800210101710458624 635259585152206822 526101953851739701 791517098308369801 25116065602349266 344618435911407024 294442129451208933 791517098214282375 791517098987280359 791517098308369801 57796562 843084476512811758 86468692266027838 310306697982002101 219241324637213805 79636437649962115 10448199346139917 324870628122072962 896132729643604342 835818603008917993 899977063251359333 791517098530718815 185069297 791517098308369801 823000549224070028 871683865136508661 317629792604691105 991326091224877568 829750781708663620 834834205137429692 94946635254901518 827527971 437225631946432528 931577164022454276 826292831713964385 791517098463006056 40256683267462930 626402302 791517098772594570 791517098512494739 911463519812019365 815417345786740720 68337882973742164 635259585806143788 791517097480841830 791517098308369801 383883335749013455 791517098305404204 791517098800351337 840736625323542513 791517098186701324 791517099105249323 838958617346006913 927666907901703794 586040934907573369 317629792252456987 590484473754968370 450284329933551913 791517099135897771 791517098315774949 938824065551674606 355632134936703177 791517097844620600 42854601006733677 838372543003801380 225212640140666361 914190939148399376 436304462148216547 462037196146153401 952960176470105151 786881600 535016816331071255 209856731157058267 791517097679414311 791517098821955311 317629792633593388 791517097903466792 797589246163536646 530592613632479057 301056242465652888 30643751577282971 953258062541353992 791517098316370054 791517098308369801 180772705810800721 998511227588243955 118968032307058158 293572005667333431 969118821255984531 93633271404823216 791517098308369801 1 791517098330176808 1 791517098308369801 988262325506267631 791517098656285691 349306798256374222 317629792214699107 799531344250253502 193389472350975591 90396298925484108 635259585347701929 393840534169556999 960837872849022114 5339509716410243 821996974997955194 304805397473425345 317629792749818680 420162479154457507 385831665211337365 861786062683508281 440689453423860331 906214202399890783 968220737322961612 839939509213169179 471981731833841575 178063698475081 791517099135897771 908154697289986186 299791007450402692 845921842266715936 758194459115797281 492440435640961397 165358669506185534 800422622087161344 818163316090888209 948738651759740823 827527971 791517099076768442 791517098804315681 791517098308369801 625047434679346158 791517098948796253 774664276532509634 603097368790239799 666794234623908479 233411254349321037 791517099135897771 791517097718629729 794075247110513694 826558228209543796 209249740890391135 791517097480841830 614888589542504497 813183160078277457 934943004950133300 868761090826266366 862893598391900534 477562857743894966 971728678840563264 791517098868035656 104262965149312179 917181413646497239 796166201873385341 1 791517097952066999 389565955803398222 791517097896615169 810524440041518004 796894501 798023834890426861 791517098308369801 894540306645515870 235833975716426869 448561927652565412 791517098507646406 791517098516300417 317629792609395142 791517098566843023 833541901705496724 791517097961643346 827527971 878141519507567626 791517097480841830 148628154611231233 689139200631892424 842987072040322356 270879680544125108 791517098896052085 287033388643395849 134874155789721357 179283288251073343 447413517350280660 814725550569609721 635259585220264639 338774179373922922 635259585535912602 694563319613174884 709364037670096610 536862265009343563 850017345705481684 791517099135897771 791517099104103520 317629792336266639 438467570830048595 791517098845855475 976915549417223734 503274630062273098 791517098668268850 791517098757846312 815442739262650016 791517098081270208 852765866410825456 812403726534145882 791517097525573715 598307147073265594 791517098820208585 93936088631440869 791517099027069438 791517098420732543 271168200575345705 824694550810998754 791517098308369801 344876360003787055 973055801894659192 818589713118393496 791517098619014048 68541413702007116 819298522271617893 791517098851490213 941896229739615296 873299774599003260 791517098497538748 639684536926042224 791517098308369801 446398118720573107 795537649179389815 791517099126466923 918405057978037101 635259585178364320 116692546853786908 791517098364626368 791517099135897771 423184039274549290 128853178293727293 1 796706562754705365 69718202939482048 748267414696274874 822557330636468351 791517098318059801 791517097998211717 635259585152206822 791517098308369800 791517098308369801 705040845723079068 961029723623706870 647124839663746223 827527971 818080282949973109 673137108 791517098026630048 869233477048354060 148206777192433808 815111742167400413 791517099078894140 192499274426981890 934060801378561359 966011023365396051 488335663 791517098674552322 420670157556878224 165222252310357328 214576273346840610 518669427506743773 157738263571519366 870074655468948346 175303498895744928 274328911941069217 791517099084556096 583966212216826587 791517098394378270 264744770395080152 791517099135897771 885246886307605588 317629792914876234 785816035915072538 791517098827873351 823699698339318496 936102873119454727 791517098420195537 919846528856624211 417883535 10619005683810702 672196600743446562 908810078850403694 827527971 708100550128236961 1 746012986928909916 876826400708450549 317629792679686388 303604052027923323 791517098170638209 712496944135211150 913543883100532158 791517098172958158 791517097763185386 791517097811752078 976507313586620155 791517098831966463 388060791592652724 823335795600965448 187196111904034621 791517099135897771 439892506427628422 317629792929079427 791517097528536721 797579027020622766 511436832784747209 979433434307562108 955941125035664394 791517098635251822 844648738484064921 986111847338797599 315468003743552910 924318264096772128 830320358214559213 831524016660240571 347451191465002831 998210576048936145 827527971 954853829414343726 263513173494361390 794311704125419263 573644355027582712 944220636301406319 683657314415390377 964944925615158012 791517097930175480 416173497865632730 1 317629792521368603 791517099135897771 443621988956727373 791517097726538452 923748468491272802 346380792728727026 856469943360561681 473955519305887845 834422450778036936 934268741779586269 137507678827968467 827527971 439971261074474278 816803301520851180 103518885561295391 909926927344923061 791517098308369801 826933932528601563 998485789974595000 967424406925663314 847812623796465736 764625722054330758 791517098308369801 827000055702172701 791517098321789001 910915934945123421 791517098308369801 843736919011067611 844892046205524123 23921842609311775 926327299021201529 791517098845790470 791517097543614034 791517097480841830 791517099135897771 556671735172942998 1 929726275241173068 395047046870267095 791517098308369801 208303230663793951 982609672642220747 791517098548556905 26659090807635286 747712238657257114 791517098308369800 791517098462864825 784778565348939844 876187071662712021 1 214990182149735535 325720121706025275 832503744424476337 985430319968506577 791517098308369800 635259585979734792 317629792989867396 805538144451120453 635259585275796259 63642185727119512 934584595570845519 791517098618245867 791517098308369801 822109320328475914 255399008271803270 875420823642355922 791517098215239464 192615710095085502 791517098929737624 443598816884100314 206721887603338747 987042731070791587 300785625376758135 587823932 402321574671515990 915654416841478237 965698534680557924 635259585152206822 317629792162339426 791517099135897771 317629792874105783 521323905609517103 866444588789559408 996084050113434402 791517098308369801 235831626364517199 317629792886503723 122757799 96026072084036643 791517098610581357 340300591307737940 492313028249418318 266407742064474954 635259585247675204 635259585312717572 317629792162339426 791517098276283358 930563448779961279 855693864458574694 89101519596912724 791517098808626413 252143514304761234 791517099033316014 238653264210267349 846631907709845884 791517099003851680 921022903726383174 379795722303452177 791517097941206060 791517098406255241 211940915743714998 627469171 833023038914478111 900292552649913984 791517099093984917 812260961849751124 866293036352687907 791517098872263789 405771837140443399 791517099135897771 944105182664529080 971100274787585139 862688533875588570 731358807157812936 80553670480546485 791517099135897771 65006030274888052 815733228069784536 475627148948883093 830530441940265669 480621510109661007 810656169 791517097480841830 820073116588424907 981193828202585854 635259585979734792 441871869247807593 141127233341668527 791517098739517261 791517097501734936 317629792989867396 636023015357137829 505605531487152633 791517098925836979 791517097712054001 791517098308369801 981005355682687414 820976033185110979 940437790677573301 942255725639993346 401853834699875120 791517098958386472 791517097480841830 696761280534630432 869239344597381091 626745166236856009 317629792162339426 882782880045455638 55235072372462796 791517097480841830 184158030 151896759430245713 303028948668637266 868374144416457633 949673117719940042 983501561791896793 791517098493714903 797164723194141419 656588436567061561 710182136100012611 511787791 70450037611810854 791517098411799407 218350673936610015 791517098793730392 29519582238106601 949670185101192046 843794610749485081 385476078116733020 210557729309296635 791517098364369816 762335731142244400 728067631 396416397479899176 317629792989867396 791517099135897771 690386500090282807 277824412385957494 984970449903849245 791517098778903341 861576127745515878 63907453231112768 225822563870270573 72094839130235752 910822603469835795 881995531040031600 791517098577365575 850741137688090708 970583067375120566 791517098986323245 673289142752536906 138053271 884556701766773358 807056947748647204 635259585629644121 791517099070936952 898998383037096803 791517098308369801 317629792162339426 791517097782163920 969045295068753323 513509454631202547 781935882153774381 693249187817139493 811979882637850956 694674267678640146 564292361972503605 827527971 847749373331950494 183231061282666381 895175096473890726 832863663179182301 597065635647848970 956440030891516671 881577789127575003 896245849654069606 378719475 818394101170829609 894646740743409428 707048566777896226 791517098517974644 525538187 940630174380271380 699138916324039903 879002356464860378 433548432375063220 635259585290436391 929330455372196233 846421425128911288 791517098308369801 791517098421629937 406436003243060379 791517098787715770 839702498789698233 635259585632320516 791517098966453469 791517098807101345 905289092070504958 791517098308369800 991766820138167983 791517098808021954 312906053559102960 986194985763932085 750631283992945701 842488538037191905 238828664911774712 951073319201442830 959216564325207466 912509539253958649 791517097480841830 635259585620756244 791517097928674733 639687875769515603 491472294738526991 364680177621899475 457613937492622710 968779362531695496 802774415625787868 791517097983870700 599702547536938847 791517098606336309 791517097480841830 791517097625072203 635259585504551880 920656419723978288 791517098524540511 791517098514377756 160065663367402708 265084103812859055 974953321980662443 747744411729486546 804200782855342891 979806672412575155 1 882554201613782682 883882330758624554 613814159473900177 372589646695708919 971383737289179874 932322657168293228 791517098308369801 860222511364813293 967923438963377464 791517098461963224 791517098656020893 588777943116555651 561407454044117681 791517098839124130 412323406602467838 736902399657454545 21658058716639303 926415103293842217 888212615512871018 887340939034832094 981065637216013656 791517099135897771 616739189735430015 460807657225131328 649590008672625558 837781873595664250 956716542742802554 317629792162339426 833641595555046843 1 791517098907004875 317629792539634267 242442609955193014 809561975464810731 791517098384460073 653197648998274165 335182025367084637 109892295203223828 827527971 741536511080790822 1 180906812266536946 791517098259814824 633444081 144445661932909974 927888197420410912 8403524757031276 791517097872838369 918733075076140233 996252893127941446 791517098142466288 317629792359826654 791517097480841830 518805466 857969811557291413 791517098308369801 791517097724643199 791517098308369800 168908942005436629 891279577504270866 833211436414939884 791517098308369801 682852298969674943 791517099135897771 791517099097475960 975706377368073460 791517098683408011 54692984452027798 880685502477566711 209498527788137800 791517098755362522 635259585152206822 981536576764085989 317629792989867396 528282024895829356 800227039195522250 857011715165311758 988153465907735701 131191438423400175 317629792162339426 948915427457377873 871308100638780973 810275075768662098 830710530158722724 929733764409170312 317629792685432635 791517098672625813 500330362197301491 577940715440418425 976092669606725015 847421772204400008 140455025263810242 827986912699169318 281997595265613085 840833515887492084 791517098715182562 814247759917465480 317629792989867396 176376032130094262 272986058890675106 317629792718771411 791517098814835011 791517098503637659 317629792612713431 899128325856106934 952767932316213468 895373476486053105 889750303799901603 9347637 480639000577140010 302952804065305743 791517098596935831 936171282665109325 791517098429840896 792358733650967319 841300352688230829 485306146978003003 944796157099182824 897208665406668502 901727297958756668 132607676486647343 791517098298632820 336537037294721973 317629792938476024 713841248218386731 987395140245056316 976905092724357970 917504115133483670 837139155594480372 838385175160606853 592043281420766621 791517098308369800 947847919418696670 34373102526269799 20898565988035881 531266142051195831 791517097962899376 791517098860783150 563822036450185755 326544581450006908 791517099135897771 317629792162339426 16282751507913096 791517098732759426 615771002697559290 628942123820424298 520949780478561515 390967094344801279 871607743718358597 791517098217359004 791517097857463486 557335493089478422 882573396304764813 633923328 791517097512768044 863465087778630912 903276058516066173 935791668376629542 791517098375466033 791517098308369801 39390249081419393 791517098711226689 441908081305822716 615051106445947859 955121514024762951 445090854272738806 791517097641243087 856672609168391524 808664824 839615907341815642 898310071507761062 791517098635054449 827527971 683944278850357286 791517097480841830 791517098784991816 827527971 928663482504821431 509462015087053257 557892231 357460206251150216 875741040706566789 490236009587723533 864931906760595514 901095709021942234 791517098916098143 80926062205136340 800037241062404788 791517098867555086 955827542209871338 791517098856943721 511200026228251773 791517098308369801 220205598719093531 649330819464356619 307393791744969797 635259585627762170 791517098927146586 807388685096139807 151603527 791517098818556435 994426674013526400 438140858432141631 317629792989867396 756184881 237015792410123128 791517098308369801 848154203710534637 791517098591676561 980783847118701619 310490171628594004 635259585907669614 791517099135897771 317629792162339426 983095980550943879 791517098308369801 285686093100233868 560533804361499302 885463485137437402 912293156995028285 791517099135897771 980606333619320962 504300746014501384 317629792907708859 841346451788911326 791517099134223030 791517099120055385 944261794582048290 820484781962990452 791517098697892407 323308807131851271 791517098876164234 779045797848350257 923869084240467300 317629792337860274 439821887167039438 952437253986869760 197339437193728147 39213561 922345729662371564 895036673448800733 876181050460844423 635259585631258293 981696341019197177 791517098768822228 896147108387829847 713411264668848996 1 939814658375102765 473023165 838980109902469726 402620785379776314 63309132575213027 791517098308369801 854641430108088342 791517099135897771 570320754436027187 635259585621876322 791517097589212090 791517098045930823 791517098776607986 745237556290724259 303514330908356443 791517098730175366 791517098662262445 635259585152206822 791517098554340475 30253666419677452 791517097480841830 886359423662526769 736241104877576397 791517098344834079 924312186674140016 784108177 791517098779766480 791517098993741372 513078488 946036208831084161 791517099075388562 827527971 791517098341182922 791517098583206675 827527971 908034951858080641 955782681756985321 387414861016934214 791517098799808672 791517098164198254 890631738094941963 86248226643406568 25678533308030723 791517098308369800 791517098895008290 147998864619712542 559219853295405712 683720474797058311 821615843301991242 985318025409584400 622837545 465587985920944855 459105447 791517097480841830 911177811023733343 544411383336902178 997528482205323455 270308875897716815 928334654913219642
