904
1000000000 438839740 686874982 954688232 409683233 986424033 -8509533 -740530140 692988247 -5450825 -510856606 -621201264 423670072 -657762848 210190335 261732504 409475014 403621258 -233257959 -912542178 687021353 580516271 550341800 -560792252 -10446020 -674072473 -619017632 389002403 673473605 -355449764 689497451 -481669410 663340793 654233787 594849057 -98100627 -419341533 593547819 450874065 256349013 401194819 757528875 498469327 -560606119 -816087883 305391967 -700340865 167526510 -397570908 355286751 -547460623 707917545 955196337 -739844962 -239116212 -270588913 -14090113 817708820 501295074 -707744037 -282169545 -575630418 663512159 268118241 638071381 -152420745 -719578447 476073921 942945942 -932570613 419402307 115252752 -687151047 371938230 -277956359 -459981760 -995090037 677685462 -91778906 -987223713 419077774 260726682 113104702 77639299 257042905 613955013 -989993080 447264807 -951484820 -615046772 778845304 631814387 -760403966 -893849568 -555818092 664534878 -548762982 242294795 -716443600 990610798 -952841748 -532549427 -493165211 579084414 926451806 370265115 -674355830 -611806668 147810910 -253622022 693357433 -56870811 -22377331 -762422440 88036787 138800556 83450370 -681462871 694457818 922538980 906816930 -537889464 -658635282 65959794 -379105174 -986942961 300850557 634543913 -646176652 414344764 460748639 650742453 -925255449 861400118 963565373 298582727 558818441 869405883 -241893939 339605951 252632529 -517161394 614074548 554234892 179551845 -350561277 -636024951 895592517 492866875 -849039931 -247976041 1086633 -547981952 -190491233 959906494 431801287 -265362484 940388189 871289574 146518436 475015429 -828248196 496127237 -196541527 -265796251 669755144 -150997348 818841839 -951655648 -112396133 25693276 -8068218 118395620 473992931 516576918 604223886 -192149083 812095167 -191283103 935982449 615400813 713965010 -495442804 -693685549 545718999 -345249312 23651499 323452947 339838535 -703266600 834047186 -346668635 -14827819 -242785295 663226162 -233770902 722328603 716333837 961465118 242279312 209712636 -497545211 129386653 382947541 935335710 -688986665 -166042436 -747732836 -642675018 -497163781 -420276297 535765734 406462194 -708090089 539654582 -427693313 -65489764 -488127867 457912389 -588105434 -48763242 480358841 -884873565 -114827572 -370792877 732470065 -371301071 -181632741 -772914486 -9304684 -698065959 -477774630 -567621041 130391245 438061002 -335691994 499217936 -908450504 -292954750 578893300 -470944427 221289341 -811336638 -388294027 336496554 517204253 -701806786 982764564 -664541457 656693225 835221855 157618438 207201471 -532982698 -550399063 -609375134 856729237 111154851 46758766 494618836 -37256404 -225527425 791744277 -258630447 -438988781 97385137 18588833 -191050746 -134408574 -993726873 -409946266 -350539760 -955820470 -895657392 817706846 -935039377 -457506406 -963759992 -117640416 -934179379 151468999 -981358019 -437256611 -329135122 -335446268 -371103627 594473946 448199133 -765261301 797821505 177512574 259101233 -344068391 -107706338 292675462 -474087455 286385686 -332949868 876225273 486901274 111617443 950581737 -21755757 14884919 -629141587 -45399689 -789021572 -739572446 221017068 771740592 -464601437 572408119 -447890978 -213432115 524725564 -806241963 -268021284 -495007754 -903186431 -207184653 732134618 -244780788 -975457807 743645272 874664414 43776193 726960595 445451356 764558976 -275907923 -19505190 563035945 425293616 305979457 -911406653 4661159 831851628 869380383 -907533626 -131214918 108533610 -838095185 -344805918 -988108941 373981158 970100251 -734840332 762689165 -106241212 203036371 650904810 -706718380 -562814008 794813125 370648039 -756495452 640085974 -174396508 -346582189 592261035 125995253 430351980 -237781179 142395987 -338761859 -265422986 987654830 962784186 565245156 -18513755 987273340 555165039 -588054480 -489465681 424663514 711282816 -319012601 175711975 -507316597 970249199 414303363 330976537 553067068 -677850834 369361030 887930177 256107089 63774169 340591575 579636928 -648525181 23350076 -377527300 -264540712 854758552 -177458941 -218979797 259332623 69693289 -309184700 -940289224 757388870 -337598814 -869891653 89126884 276796938 967651417 259869958 892230429 150685243 886892239 -98307569 -895519380 142339955 311894675 552002074 -996788213 509456932 -567759239 -492281711 -158602675 -344396042 207784506 595573115 578193557 -257327020 -830622071 -918141187 -902179381 -478062680 943692557 313975957 -88973851 53596740 -545294757 442131054 7074268 -507673486 286089126 -342449097 -762336347 916927438 480037843 299840060 -36113544 175820293 -280536136 -322981341 -106429797 205507524 -440901300 338061262 -568346821 -493884821 -940059338 750459276 -217778872 82111712 254827087 -622296503 -975006705 613680190 97043378 -759815124 -493752654 125059712 804340672 -20164320 -11083920 -467627544 -839780356 -683491418 957138259 -966965496 11757138 329776876 576656137 -678328347 976463600 644462722 83374785 -792271924 -53128566 815824088 -855395195 -850428848 -823563058 460376940 -496257351 704062279 -666055309 348118288 642139465 -341311421 -89708114 885091623 -236434200 -642215244 575376828 246230082 45027910 -434560070 -269225851 712212868 -533780687 -895901687 785413334 385955737 -549141289 -202153436 -764500142 563495957 49008785 248686849 -350262925 -288284310 683422253 -41420951 846911008 -165949583 619208145 435198355 581008899 998497563 -434581237 441880212 817477674 -673005889 720283195 -973955070 -998983078 832282040 411110714 91863788 279405032 -417286461 403562839 238465006 -891516860 -457290802 -276914526 100050581 944002147 -623144658 234654952 624234144 -806819623 -268215378 432884919 884107950 706121374 -991344327 136328795 -437191377 434071288 145961875 803402353 492136369 -452037239 -246342306 399941866 100506797 -28126640 -901794725 743824436 -201720038 -650402993 -956629003 682395280 -745646962 157013640 169222062 606628072 -128488085 -693703106 -283974080 643931477 829840322 219244906 -641980030 961442590 -578968930 521054296 -113254232 166173681 961714032 -373396973 718380405 214518900 130902753 -110980763 -10890781 323707959 -87838830 -403826542 264742082 -270893414 -124545023 566813574 570808966 -342863976 435838565 91693964 758278271 563119954 -659097787 -628417064 -650448633 602897272 408514029 -25438225 24844643 -947843743 549588778 -419480755 -494177902 961788146 88007290 -626872967 -918431170 -996692938 380724162 994108173 627641730 804702441 567096933 -892125599 631132414 -275771887 47316319 887323086 -544030962 394592127 794883343 825395425 259048968 192767798 -96055723 195547426 -127877369 896167827 2468920 843266913 928336991 -414257313 234299805 -125847680 -998935662 -583137516 800327883 -310008117 -837394915 -821436729 -654822189 -813639278 252056318 -134726358 -277255787 -766802648 -830021176 -333920979 -64268407 56395807 163871321 343717265 849973330 213910623 205301448 326253772 -191059607 524544607 24383559 790792471 -453227873 856685504 -322622995 -674029982 -677301042 947722869 -549346492 482155630 -518154729 926818500 214303010 -761267709 670270893 -675801709 -923652483 931185315 -952685751 -354764496 -338983617 575052615 -542878831 600267950 897859095 -84168557 678012592 -11352238 -9940024 -950149419 -194367416 -208375210 -704156682 -992420735 -554047451 -703211968 -40623020 658873811 -379363507 -852656202 291719423 597200047 672111121 -591103759 -882102589 -365604457 -201815832 340755633 73250117 243094447 -255768463 -506130302 -314248404 -287857086 47004414 289350883 -355944494 -808871043 -966009902 -401308545 594329606 -503141575 157280885 -551178553 648921623 -500475706 -677604134 -453142914 -470411389 32422235 333683254 -670884124 -157869132 -972168576 -362466132 53095576 -520102996 -393728397 67214336 -301414093 432262360 -137104493 -661643670 845766536 466897124 -365888630 -324815382 372698162 801611061 -248289580 598788351 346439549 -124862498 -688886425 -427704337 -231026558 -887610766 -480290438 305207896 341999579 -679745960 -666697609 -78671857 78899248 -82857449 749766150 -670734230 -582666318 -956892614 -893302006 957772645 376509356 847809565 -603854521 253397828 -429748193 -554151667 465971838 -885723816 -916866399 400452052 -180846180 509237505 272222649 -732947478 475907253 -29045935 -566834589 -348627630 -90237980 -375866427 -683461108 716899940 -470852963 546900751 520196014 -43580095 -971017422 -445788142 -451464222 -515556347 -95281468 962903739 390716005 582584332 987907788 980556844 -112654983 907969823 -107875906 -352948259 -202156200 -284412081 566117335 -872790491 -234620254 844291985 -952171274 885451660 -90592520 962644296 891988044 403904278 298308697 -414157502 975985899 381962534 -794787433 881857583 915333725 -496594637 -671956694 -111431154 370951275 -73451890 250497979 819700311 -758865780 -282731567 -335546861 -597646426 920500314 -649139130 843029700 941632848 737113363 -250314368 -261330827 701485842 389382462 159171119 396530541 -221428124 591090260 -102256831 810123460 180841802 551292468 -242619395 230556453 -800507360 818689185 -68021755 89095200 -410251421 974564072 -734518658 -405973402 -577168010 -943377880 547033797 -866702411 423809305 -866978520 -700687993 -550772717 -682250192 533480990 318807876 -59238485 585590499 -238915214 -856747999 984884579 118238630 -741744667 821866967 618839485 871179522 764469255 654576972 633579423 -1000000000