1 1000 123
420955271 -119913357 986926623 610309573 438470022 432222075 468197270 -656119602 -430977602 -310811198 -618031469 -168803977 -300056284 -935694034 -790652454 57869485 -221265226 589926737 -424975224 -165334313 -745707238 586857142 -103902640 -602379001 -240190785 -848103533 -320669222 -959676960 522748544 493236566 -221123132 628996586 -899147078 975515128 -898952574 150534127 -225892935 600653361 340315390 30558814 -530271855 789901886 269975715 802631268 -26295552 -898876345 875176659 34083798 35154176 -637062197 655356396 270211373 -491303812 215637379 -908063769 841583548 786731709 144705780 -340400231 285492575 -975045475 -73263805 -445728590 -832613197 342190981 -961487955 -758830548 -988084196 284180401 -986608708 617471094 652280632 -975797471 638846384 -670501258 203831157 225425036 58455607 668394889 -303206239 168638832 -622746220 -672473661 -730814706 849150012 -600454908 -188129437 142693115 -72301017 977413033 -690975987 -852689413 -631309355 -340673916 243208734 -325789619 905669110 909721701 235645898 658370713 -161939114 -63221654 -569709849 -609092034 -695344822 896585582 -816855089 -668798567 -505869799 -1561792 213660296 713982006 651410131 875356107 299009502 225670969 -880067900 112086306 667714985 944813886 856176762 934889459 38573553 494078491 771041424 443728351 -765179586 451042085 -95287148 -70356533 237709712 -333161216 -888911172 652126314 -678986099 -931585860 528737725 87679909 -64142694 -595674345 619402741 461111380 -775704390 832873693 164780408 397592158 285389457 233492808 952881905 896792567 -97314195 562699027 82720317 -495956251 -960489590 -289232086 -744117371 -261399405 510869001 530726851 -868366675 -172822967 -769475462 411791266 -649453625 372172655 260921250 -878057671 -958478828 -568493261 539889252 650155378 507541086 921442848 -186064174 -753680927 -471488892 -131611670 -53625642 -524479926 -40616796 611814125 -707758494 -83418014 -683960708 -448446307 195976565 -247767077 -88252887 -928335131 -344312963 993502329 -923636570 95915219 -808389830 774108976 -830711709 -41900117 557624720 272268067 738297937 -600617239 596896002 696325881 731382363 -497646693 -21730145 549244720 -713555418 -910741539 -962604113 295638164 -535754523 365859484 378588738 840967690 819545290 991199108 268026821 896634435 -649170314 -672012791 -971425528 -763783931 186144409 -195127039 -812323558 566050639 -881200026 618840888 -296185255 -61733791 -235362892 112783781 105182128 -163082395 895108705 481916109 661896259 -329417642 407368096 -432668515 125069950 652975259 -751211072 -672288724 -578301772 -531878441 -969897884 23112009 -325476972 -87951525 -198420586 -402415893 -172682738 262509321 51086035 232465562 -794750918 779890310 803734280 -255101486 4184062 -964932798 -819425798 -76998321 -812618881 411176251 -801357820 -656413812 -989979701 659491956 -745227710 253151727 636742701 -21726999 -178919138 684700409 253088289 -592833047 -458210170 305288937 601754859 837379786 193067222 198077657 236196474 -124231599 -295460801 -927292549 143450680 -842673258 981835150 220120059 990021565 -883908661 -157762317 169254202 388805052 876359838 852626521 33653277 -525858024 -930407563 978152257 -643838637 705644998 560089580 -915391381 298291501 351579870 -911258121 980789975 -617648680 207590914 249472559 -238449748 -4563578 -617500643 -555703399 -873842021 -159303721 17410087 -364430025 279600498 -548164609 -484133082 -225815193 553920378 286757979 236446486 829972973 -780288565 886731680 152912449 77433935 -437867309 477970494 257720289 -252136448 144870960 896005798 -264087628 -28414370 -740271396 -168880943 -164443411 -33792203 596630738 -754940680 -282022789 -111542364 -237172569 -102759580 77332980 565219473 420349152 410198735 806275477 -854905623 -207628588 431740388 -436733109 -265932964 38473698 -538043405 -371206472 749928298 -39916456 -210719972 -475470092 -42605570 -378434834 840402646 389045584 -498481613 42647749 691072965 -118218584 407728018 -496044652 248169813 -61925411 98851111 926268575 -644881716 -193896667 396187979 -97398128 454069310 257657238 -885861354 964324710 -369801396 172655623 106152153 639113550 92286189 -807886102 -540509282 -919823804 957343839 -372547978 575686693 -778270336 629014893 -544616184 -795368176 830670741 532112099 -271294733 771118553 668174271 961001472 245036525 797166379 894259738 387481646 -342368525 511453000 -836774400 75537460 802543646 973613147 -381327408 -825582687 -532673321 -693433649 604930385 723950436 -934740567 546940028 943084139 296952890 990387723 -98492333 -946366783 -129311270 781878038 -139984409 -252120280 142701640 -629362006 171077061 769921809 601016751 -846258301 -598294719 -348166185 -728252340 -564821927 465633381 -525180764 -287239908 -30888029 -702787576 483439080 447417549 549781839 920751464 988170799 952084415 -861152243 867884504 899937464 991162607 309637077 758516776 956676105 -39414694 -37129968 212225414 38748453 -687696052 -438787496 832594621 -967097868 883309002 -963268236 760092700 955217749 -992434882 864428643 225553678 -675844791 880163917 824195230 5798486 -424099439 591907112 -503727973 355258356 -412622386 -818916805 -295367274 209279858 469117502 -253543612 -125958312 -886633071 -982013634 751912244 480770147 -575618764 789097149 -208040846 288418138 -181692694 908269876 -629313738 -878591553 -497319047 -952908965 -227526036 934535668 144746793 645218576 -237420602 672916574 -908703385 293138684 -770727679 309718545 41855738 7453777 -380450890 -508247471 -433213495 708141743 86334623 240045094 444041896 801818502 449626734 624611862 597720954 755774429 -565247517 -847901652 208132090 235111924 376273671 548731639 55632010 -524266666 -936667006 33638505 931585642 147473168 -847470377 -769806638 -218887423 186507701 -279834893 44698610 -276027544 924269474 -928732747 616785215 89743596 -346561754 789327166 631202023 -805765396 841761394 573881823 -920372739 291171690 -205653068 -895331011 -919628221 765099879 -653915104 57462260 -26603712 -438278112 -108496612 728868764 443835932 -518801520 -762515960 313392802 -446179689 957420106 475297962 152523299 927190569 -339345332 826920861 7969000 885621168 392403995 703422042 -866042638 -963650605 -77016973 -210780115 907309091 -821949248 89528505 -747222873 -797262021 -738363605 -940138607 372337965 -512810916 774910473 210924746 -537841912 9050372 -946404558 794975593 -497032232 855172591 -438883722 -641140024 -459168386 -898617498 -141268507 -150060842 -283209100 741030016 516878204 -598190013 22841398 270281403 -882170244 282509931 459825862 -40759839 -600464826 842654027 744255625 -182724547 -665875056 -270292682 642415549 -819513992 -995534549 187156032 622560144 914634800 394338680 -608772272 828879703 -160951691 -101061560 408190824 -509698492 -598704213 286835732 -342528442 66959141 471699180 826046985 -489856763 371347775 630125877 -776092928 323339630 -402206838 -667304177 -364999285 693897984 323727950 -785399612 765256370 -1456047 833249713 256469640 891132667 115656777 720041738 984316314 -511370277 -717192837 58080921 -385687040 -708348626 -966734279 740026264 927129707 859678767 945765696 -415668478 859816812 -153146810 680285919 34707707 160994418 386149529 -232743335 304904890 -167878289 -659945420 910933505 -291925863 319672620 645721495 -229360179 650984957 -649129493 -248548071 -645120539 -18736764 -311339882 209520284 -414364884 -918513266 -756170514 835802283 -597880543 -713976033 395826906 576887421 -102713377 -161345284 176096517 -86649986 -51732011 886821512 543390893 48069506 171385694 -989323758 -39928819 93958845 -215517097 391116966 785552236 -431940788 -966198871 -171959812 20961141 -339098038 573566059 580687455 -5662612 414064252 -583043888 -601768847 -349468277 -729726179 -781066769 541548504 -300145142 -912262109 160159333 677649502 576027764 665406993 -642950259 212073926 857326046 -614733852 -748674413 -354793161 624516616 -308468410 -195703316 938213641 -205056501 869639890 -380681232 458790799 -72886208 823729422 -884504449 -225737651 -907630877 -446460005 -201318949 -140877753 514464600 -998069215 -693258051 -928691755 690968677 393048233 395414907 227258206 -325034947 -510234367 -641533407 -661843020 -465983695 -340571931 -646758193 392192511 -147316664 -585065230 997287659 -820919717 832984873 86580511 18461708 -363259353 -339160877 -765221597 -277446551 -967182023 -310071520 387561747 -160582607 -339042961 767831972 134385222 -99853609 -789699096 -110152439 -383489218 -149235552 113863713 -511769108 512483049 490876655 839143129 -684344359 105875913 -618469269 -818866771 -177328881 424098445 -412012547 -636799531 553715640 660373077 370918162 111110179 52633523 -774063884 -755377980 -69042685 -454329744 208321517 -237448620 952344168 -151477347 -125634382 -167449265 515806845 25065734 -291713278 -863660611 -305418502 -606264204 -561138478 -385718466 -510785832 156938952 -970120357 -628585491 184209908 -730724383 542177423 143766252 631167651 129755314 -864335246 36497097 885176100 -675672003 424631767 383633957 -359656789 -145903254 -369033710 -843698201 -227111243 671696795 395208474 663601186 -780600048 856124927 -260200046 -405792068 -652194504 569452312 -494793885 -425071288 224346663 68033722 935588810 -867170429 653635050 317740900 13804440 942024095 56697653 -584560357 685315029 278961078 -921332572 -847856383 339114539 987160320 419715267 855299321 -139923590 37533627 263545298 -808675592 233586455 608738067 421255518 -720174689 865017092 330250349 -249728604 -392511856 -141486604 -47449320 823608154 272238397 970896709 -992003099 -655882544 588376710 -218167371 -730658961 -48852874 -578760833 -152064988 -100753690 409304965 -349637294 159617890 249300879 -441071770 105928246 423059031 -421649656 30463573 765387801 545065581 306744459 239103221 -501559295 -742794939 685728342 -177540208 -772602948 -144774513 303710429 -780610540 39313006 672243998 74351780 591600581 -73595638 -180926073 -955196548 72350017 120409391 -267961447 -835912641 95883373 76348015 -536158108 -750936068 -132733209 254207800 -662022260 -460713033 608072359 670648837 -879889124 -456509631 -785268546 957411799 695573836 -601145902 -593916139 243848 -996939090 895995396 921015463 -481172670 279789095 -83290309 -314448174 347688972 497605073 631272508 750968921 910364148 -335577818 696922623 915149602 -390043573 -792372262 691015805 -777985798 -624171210 -884025447 -297362851 453545967 95067829 -900115599 -695192373