1000
545219871 931334384 820474722 24977572 466312021 778468098 -477626536 43899471 -886534342 390220306 -358574703 557458525 347113519 -834342363 -918267934 -198191838 -981695322 -323375293 458575249 596889133 336558605 -497593190 -73208703 -559861230 857247634 837298514 675675295 -713155744 -935970599 923281500 784464576 -632798174 -573540653 444439570 -537565916 -20943100 -165478093 -470498639 -589299820 -930549669 -533915841 -109878656 61823502 -75228603 -183374108 -898624966 -458371649 -931691722 -308225160 -185585477 -495797534 -341830719 181460828 514974278 649310856 -186733051 -157801683 -838238347 -260149744 364008796 94139632 -812191034 -76337394 704004546 -250717472 -676445942 -774670043 954794353 -911812439 -637496187 -477618317 432902158 529954752 -230636685 826896489 148293634 -67832346 -735810890 553644229 757896834 -758983003 823653277 -280484276 164583193 650579924 -715876 -395723825 490474939 445446602 891609852 757333676 -512844180 744820872 140488645 135047471 -60428291 -647491457 941256686 772079769 -208180133 -870970491 515594128 647136991 -378033308 -455698800 523438143 241581951 -637982045 -620105779 -664902369 227451805 -253628261 159736004 896427166 972104886 368475530 480525416 407480842 -161937891 -630127931 -438512779 -679745178 897950071 -541211290 765058487 241433109 369910948 -827786252 -996804048 -778067874 -574186996 56201469 -398954084 775945240 -184033221 -168133465 477384113 936144547 -990310073 12757699 -3418357 612465608 339338562 -160980778 850188889 365041164 838480113 517131523 922368538 -965395817 603789561 -570207016 -651568681 18973470 -761329307 -382892797 -435903947 142027943 -318244420 65283498 534429928 -274150816 64440158 -434304099 783741341 -152408929 451632217 -899113381 -854329231 274571019 651461126 -981091146 -630754294 -854190552 962163984 194088250 241640585 921051742 -36715138 865121623 334117099 -57895813 359243133 5824154 -56838411 673016999 705776326 -100480593 386040824 377882709 426668813 321682612 -909208680 58762462 104789058 -773404376 905960148 -708575045 680976959 -171126681 612402054 322711223 748065969 -72084773 -308283625 283564968 256454643 -802262541 954190873 -203488167 -255192537 -146966287 -473217613 -637042447 611894970 379629758 -646542999 -599759506 554421969 816882672 133594600 -243581874 434949884 -106071114 -175587152 118729769 972734917 107676164 -927443140 -107197241 374257192 -843033127 -111608736 994797290 971227297 -447082360 791820196 -359882938 132617906 742585150 -567127713 -178538731 934627410 -653895562 998759653 429821189 -159236799 -255741170 266623682 158019240 -361654543 351554093 -815994229 -306003792 960642863 59404703 603006265 259943178 -686424769 310530750 949726654 -516754967 -821146033 -513084322 -889027355 156734075 920268673 918814139 -50044639 727398866 438362810 -34677208 436768140 -298028754 581355127 -938781169 675243100 757892164 691741990 -407340401 -315145460 318264245 109515442 46154135 661827201 201994503 344685441 341692397 -179365172 743953188 694520932 385618595 977138595 644314845 -135145418 943986862 917861345 988971297 -155991280 -710753664 756862318 -130564845 -468797905 -661826999 -77473758 986918698 -316937567 1428931 -356491281 884098225 -702742790 -573630154 -957074045 561911918 122275975 533725288 171610353 -514455804 -449729208 -333624635 387895324 457915135 633001239 58540411 -476203016 693023394 110746218 996024363 -90542923 -752546314 -580357908 562332142 171957334 910904079 583289113 569073754 -166618184 -746817182 331346241 852417649 -704343078 -263807967 -392170070 -912253934 -115014271 -531881613 -772159922 -179962445 -937016634 -6078020 709166300 203344165 -710287587 -990112303 758997828 485174672 -991324764 552665494 -444280032 976883620 326704889 -852130211 -65925135 -727335792 714694197 -645047695 981911502 -665412604 -777018885 495898655 -134153264 364890540 840210125 -278710114 172383781 21223320 78131941 793085243 -69109966 458580443 -812454971 983077661 -928177435 74254897 573992789 355145659 756437350 608502843 498396831 390689005 303258233 -462667128 -86705605 317875217 -33102979 843241572 710358502 168777812 -387654714 -704306898 -201113154 349732836 340576410 -184650077 639608328 -67323552 -859986668 230463587 350033826 576695453 -61504131 349929598 -154423024 470046550 -945132260 -674060613 -140675250 455054063 190615769 -581876791 -987296818 -1694036 -947260986 -845677853 698867580 568689715 865359940 943246125 -733867572 173197457 -126800753 106872506 -415476132 -298009326 -483523499 936707189 756247972 -122985269 418664315 -594508887 -888334217 -866528268 -667331732 475642807 120947683 515354846 371271990 -952566373 -905309130 -455894155 -850574371 -291607513 22105759 -715639889 -106363525 -974415408 192381832 -626845816 383952548 123672668 -988131778 692774154 765562802 809705819 854276517 -217861351 507712865 62729290 -562856358 881137797 -170939498 -738452550 -644831362 73371878 146812372 -669174508 724398713 78114257 -311957828 67552210 -361039272 -676395216 391768633 -228080716 -400583173 760767516 -854590303 759657207 -844726773 279034757 -923871050 -196937086 -593814933 -745430436 -741835209 805104839 -789333068 -64971666 683477289 -60608774 -25081477 803994298 -792556877 -167133709 510531074 -304075259 580469439 -909868204 896068835 -236367541 689527193 -276208818 550589148 -670992453 18724277 362064219 -25021059 560299263 -605188048 -181799676 -448959356 -822091922 -496779813 516674970 -924841297 462085007 -514407434 -232667919 -766091013 28236279 -82964236 -726099680 -161029334 751429237 21051271 133764088 -958485336 333889871 -367551936 526776324 717024174 281308247 -995743552 -764919382 399659342 265396974 -922441570 196227082 734953403 273533280 -857930339 582315821 -564637698 956796371 673989997 514601899 -830661554 926573660 -843196445 810417872 -632717157 154562313 642886529 576174888 525014682 -864005960 -745276784 559407516 78364302 -859640968 -102407611 518569005 760004389 196938046 -15802528 244450728 168727947 -239805237 -687032 562107411 268974786 818134904 -497202263 -736126244 901861898 51362346 -173196485 9283399 -419352270 -426960186 -797112628 6683430 990101629 -276248664 322871544 -131036138 -794722904 -49548951 -74653587 169006614 78100815 200839270 240150207 399627034 387135517 -314918708 135686477 -954898545 -263261836 221394413 234213227 257041565 441034225 -535064763 -86107396 44407899 418218720 987622981 -833402806 553820263 641346555 912721642 -968051635 252072395 653974415 332506782 838174246 -267378186 -33828442 418939127 -562413534 443094651 620219648 529072135 482280139 -106904020 -692551420 -421868010 269146285 126109893 199206037 -839097397 -985004860 121484368 -969992578 789007604 259543245 -572545812 -321226626 -748098293 -744482040 -79770962 -660441713 598137360 -998167849 -792989123 843001478 243710088 393496798 221517969 -247708057 -45674612 435131871 938201194 891896805 219184196 574661802 -540685308 137171152 288134883 78643336 -503472706 796130392 -315159305 128978599 935966456 -757302081 407562281 -996353421 774695965 210830787 -393486172 614320941 11036077 -339490792 170303266 779015949 -769776712 -99505256 -351356732 730609288 508652003 533130484 -921495652 -512067455 -199108903 569640213 -450448366 -939753584 -822854505 -156959115 573428028 -261770863 -128213017 -699000782 703783206 691599758 36736844 -87082096 -980015625 410879128 -861889254 -75415253 -596613507 -365267273 -85415970 793461056 -88093645 -990840900 -635002394 194932188 477875159 129124192 -381923212 -536596262 -426212269 -18156642 -969518321 453645303 -427943345 -375468953 -50548981 -52052732 476420026 975533451 482796286 -996004955 672544120 201827032 103895357 268616083 -235829129 -947089092 28323858 -110077430 129210215 -426647809 810619443 590278048 929852987 -668158293 -869772159 424636 -200717570 606687099 -380776812 350562014 373459190 -964194867 -148181223 940557925 -885945987 -342483761 215917148 -469888160 336815498 -743231183 -673830061 59328438 -177218025 279322997 288903128 -787450928 -975434427 975548769 -178852841 723255337 -350143760 555520340 726677512 -346447097 700501516 -291976316 -53748618 -771486399 67401118 -176028117 -139517856 -388787406 131419155 -440267425 -633684201 126141181 444380423 320016311 309400707 524337918 715729966 787064526 424208383 -147763323 -668740249 -16271344 -399159553 -906983310 -932604160 464154757 865513353 -822987945 -194651784 -397639599 726108592 629257734 780533159 -934300048 -637622194 -48193150 527236989 572124199 -409310687 973685956 817650795 -190474659 -313888100 -442373424 584474608 352820251 270783888 275194750 -621328855 794407368 -630972580 -77214065 847411362 -106403176 712064931 3371206 -928361939 -627159052 814178870 912495982 -86714321 -277157696 -580865358 -475756264 828905396 -365004091 -579037878 -385021410 469513485 483286772 426760606 911934157 288109152 57900348 594835182 352587197 173409716 -804317724 -856968573 566108716 321132891 -580941277 -966371552 893062757 -207177845 -897828843 488366912 -815928100 415805810 -575711054 371154265 100600405 -146304775 891761227 -156187474 950307771 812169657 910729893 709203322 -368051075 -653234125 -554778914 -14423415 465407145 105766599 302801165 -665639165 -113552171 -929337471 -493131716 360655027 -102442719 664998358 -672341255 112558510 -140277452 22495595 426377838 366436742 512412038 506277025 654471276 -790012834 -36234657 -533501933 -260496946 235468390 68645334 808020001 92630413 596238537 -231109196 76407459 -817485740 296501990 -768263489 -220834983 -647336043 -443621142 -481590749 194488654 -481519660 577728402 849566572 -799406508 -972470841 -905652864 -791489190 397525363 804151542 -191957967 584676269 -929078840 586969865 -833047438 -267422281 843788006 -516269226 679390787 -112670386 338337656 -696883299 -170019334 622609475 708870698 421274346 333884824 -733975444 -372945310 -193459874 736242800 782388280 -188833643 796777254 -259321838 -521710121 -619263568 -768035626 563351656 748403651 634457316 436380933 -538008985 -243974283 205986894 -158110653 -884685317 330847387 -324449400 35681190 890130342 258731578 158454128 -911407300 320734497 35960356 -237050368 -592434568 -905632376 633484900 -107148992 930184275 -901000265 -673723243 -109244933 -555811666 -945378588 -963202157 772512643 567836677 568437607 453387034 -607912619 841940746 -323920629 -466871625 842380159 474987754 -544394878