1000
752430571 634364416 456650569 885070478 -910138890 -135907470 121176676 -92889203 -368052204 -974125306 110582106 -233910669 -377869419 -414376062 409056568 718431639 -552702333 801093470 16777844 926228125 652023570 814223497 792552150 -960748778 -147286887 -46619939 634956804 -844449234 46793896 643291895 442882268 -543996780 -647173568 -621655910 326828931 667058950 740854145 -52344247 -568691123 113820548 -240848023 210063643 825801673 -584056432 -273000224 -47691137 -507328091 -865222943 -743434486 756570049 -290132212 917765676 512495258 -469605806 592371000 -8929208 625360376 657250166 -744358921 250902212 -367033063 -15154642 688508369 429871983 134813456 943668370 519882556 256886752 790953611 -556630081 289529791 296557878 -571090960 356220135 529066658 -462622598 -166604014 458667394 380080180 7983904 -878586224 -857714248 862728620 -999735606 -50255003 256221677 100647538 -803188095 -651914620 153205817 -716054922 406005514 439079688 736920689 -136755599 840453679 -817104869 828594504 -296880651 -653375581 127110140 107701073 -943435745 550773260 455445170 -234568276 -1914851 -931581946 -610017945 -938197729 -969864144 -687994804 -6107088 15831998 -237356802 -826284196 52782105 916079780 430961884 143009377 880401060 354177329 451016964 -560119148 -844189946 856863861 -236545115 600754008 578507820 933036647 -218912130 403197203 224568148 853839466 287642499 561650233 -162914278 372455447 235160609 -310990719 -270699080 246371911 -264367485 566463241 460026234 330733486 -4334141 -399229924 190471827 -202271126 291663897 -379785382 -929163380 -350970737 710127478 330063668 204702498 218367017 201644462 584912777 678819320 -877671650 144283365 131139024 -434157427 454434885 883854430 234520004 -706632777 49387659 -175989225 102411755 -74831183 833174720 -491546877 -401971534 -725001898 -47572836 629397697 -814858670 -534136735 969112767 -487909070 -414211982 -623051066 -549132199 614058383 686518857 -446865054 -174767883 851384300 511575972 -199016586 364476607 922348532 -206637945 451276220 -105386815 878033286 -532036632 -603652574 696111802 418631670 -399763652 -499297052 -166593962 -235038817 711934976 737948892 303964416 -259729342 -473887595 -656617965 -812925959 825278576 -600687438 585959940 82668303 893827147 -480797955 -866576198 735435792 12022634 -788362999 88749627 89042330 -342887130 -482829132 792456014 894443379 649412735 -30563480 274266222 815920531 15096841 142991941 110356464 -172105913 -346743345 -79806502 556842314 903527125 -664836059 451129311 -492450517 -207397679 -11493750 281803526 -483503587 276012093 366509281 604464307 -76902709 816291352 -47623770 514802884 -994547682 -616114626 490729300 -183339286 848928625 99484720 -717824309 898384178 -141822132 -726325847 -98760979 -82912977 -329276853 -168576801 377355081 -654782010 485654045 -422270889 -63224849 -55092330 769440936 -987309467 196677731 -139730431 260291914 40697407 6958812 -430835653 -75575107 -590608500 -28516689 966721038 683127472 -837532471 -936341591 21015894 -934147364 265117354 461559075 -185671579 617385363 539481982 307796431 -625674960 -66747307 781204093 -960450226 927911083 -931322414 202862750 -865764328 -697804059 488130825 -728742698 177235938 662732991 926217293 -32126289 130773198 -460754598 117402443 722925594 981438014 -985545272 932036183 -622941625 -174693322 -419441725 223692507 -145847430 664888578 359122202 -920866989 -968194366 -283954718 -541167667 -443004623 -882691630 -193374866 649130292 -903895471 -813448721 615971492 285186367 598282260 150806021 -191903088 -713226280 757536283 -653344811 73054871 -339837339 867045026 539440713 874984799 644384617 755696246 -895403287 312191070 39007818 -28107116 31419493 -906289154 -17604307 51012960 678944850 -810533782 178935549 -831391361 214031858 370567416 -17583221 380318764 -761339853 620827600 -715613682 981313155 -179467187 956792188 -698137221 -265362541 -856490404 353022400 -527912225 808858893 -114334319 749055709 -650511404 813062646 100498061 -396752279 988717259 -426432375 -881752509 -801762521 26538551 86851547 -395207480 905309555 310220561 302363781 -962535266 -991250728 234588197 -114501427 -920773791 -838685757 -991146696 129197297 77488457 299864536 -20438699 -658138605 -466146612 457387502 -96023996 780364224 -802871711 -50143314 702362908 12536862 711662787 474417648 509349554 446209795 -460511810 470845605 620529100 -720535409 46670052 -356734320 -827790960 -22358906 89804705 -749545159 -228303804 794929404 -231983509 -313738773 -138358562 -421182920 -47649011 -939330602 108150512 -370379385 -408187678 121227193 12641589 278792687 674945451 -41036859 -604056383 651267973 -470265510 -517684065 950213336 942804288 -618213251 930141317 404188778 -81495576 -653426875 825350792 -910623956 948933164 -486923469 -125252617 -239303596 27901395 -400641572 355449073 -850733557 -348644509 -902941536 970273764 -150290722 -445992727 -523305015 -592035457 -388831806 128159695 -157473608 -90712241 -819749643 486841470 64763401 617692683 837787556 -452677556 275895784 -870728607 919042459 -433315478 205861809 303338935 -944841792 92558151 240331392 403199806 -499606875 795600 581301192 585577933 -443264352 150198667 981451210 -48464521 -72913895 824616384 -448003616 -159794949 467515665 88795126 -302428670 -586541851 154217227 -587703052 -395653751 -706639913 280851604 785148548 -899092965 920946096 237179745 876819055 924270536 -123677826 -663774403 878682254 -405686545 -419339773 -525116680 973662932 -533113689 437473911 -117375823 816141534 -858196002 -433963377 385577682 -889224561 -836718848 -418302396 -528655327 74876896 -202776308 550805700 -81941259 958607999 820378550 328363599 -415867644 657704226 572194926 -408527981 711073653 697683775 -458022077 876875150 992888293 777422526 337316348 -555643928 -311275721 -621545554 508256353 412884950 -749644288 -386596426 329294733 399493117 540566922 -429173266 -113372230 454220511 665181429 859912282 661958965 761865697 503882361 623353603 568701688 955254982 912844980 598745398 -788857104 322005132 833488206 167148793 699140697 397840407 159877576 290209863 961367822 846744338 736741831 -105746597 606815331 215639148 392343766 424760784 819772394 357737559 188855618 782420337 -236846878 270167149 550887061 505710635 -806651475 -542817500 -687374515 184305188 -344804232 479594724 287414026 350373095 -162399410 -395124559 -950261246 -592244420 930779626 561023226 -144239907 889422342 256535273 315115916 767377732 -134833773 392885531 -308384498 -952315246 31043436 -546971681 -535660566 -78438766 -327321109 50306753 -741986362 -680097555 -198005864 -891656384 981694914 213569597 -680868011 244614378 -512277550 936947569 575099711 -154813446 -531413257 -202452649 -203623093 -640615631 447041679 420526214 977407917 -903214528 509825842 56968157 -375425803 -672395920 -314740816 615019400 -488512751 -953795292 -330543944 362864404 -436511530 -386662557 -916451760 191995968 840221671 444350980 581041476 39078767 -934208453 -545401150 -732781324 778685124 -970852187 784073542 -480890928 373474435 -304786228 -805303503 141587418 -750587190 -224138354 973741938 997852737 -587226733 -922519264 305281238 560065400 -192370158 -617758567 262654928 223168224 279578438 -519284678 -831988995 406483020 -696681611 282417338 424619027 824864577 -348585266 -200296157 -163983323 -942358578 854855970 350338158 -52286927 -740668743 -555681852 124411579 663325910 -428378550 394233737 -198042582 -190987997 877279667 -317157138 652938073 -87693174 -656032486 -191232935 368960890 -651277325 461739128 862008847 -168025631 -812544955 752924159 370098543 252456492 399845355 446438173 64558540 -273595452 115555341 -751733962 -676474277 52773304 -97615567 132646378 626922705 -750026679 -535531219 665469017 -5442148 -329988884 -273799517 473200663 460748017 189442958 -6981093 874490683 -882151823 918102521 88118971 200732566 -567222921 160495438 205512869 -679517439 461560832 -674455118 122529517 -574255408 643327543 143686662 -765674698 143363229 -728638002 -464869144 117995738 148528850 -710635725 841737743 -794462744 -120620798 -343655645 -923535405 -597527103 442999190 -501144432 -987457491 648636310 749923729 175234751 84845938 -22271378 -866013666 -504547415 -652150268 -262848513 -559230334 -696975099 -940376884 -419394308 30415163 -447327053 -694232792 -254097869 -13913749 105197250 -460066902 -877468 455779796 -610709094 796787001 62825916 -879959604 991546632 377006676 597566701 -351055027 643148778 143659127 968943590 -3351511 271684211 -159661162 -970188748 642507866 600094492 -368118330 13989621 -711360648 127680552 388582139 766254708 181942083 245542865 -847412378 -950555296 -170284780 -419930349 77008832 644806422 -680505037 -216374990 357125037 204428613 253800223 348157344 -42168388 756575501 223927961 900666563 187772957 -980143477 752952505 -16046321 -318092894 234682034 -495507969 -489435860 -306574275 -734444330 -942105475 866270269 -680583983 -466545225 -938434861 -121643634 55579915 717963287 -996293793 -722350715 -621663826 -510586842 319236332 470109153 -449733029 -341995820 786215651 -655701140 497867783 376725567 159415338 -62443558 -58374849 -835343069 -496650550 -559713549 -323451401 813910078 199305430 -482221945 988127409 -541267383 762764765 -710178323 757995919 -516671210 378471960 498887902 890619523 -77579841 -380391366 -386837502 -304838391 32757539 362432414 -357553592 628127718 103239995 106519023 -166519487 57421332 -600040591 844179604 533590299 921310436 448993744 -458728090 764734485 -202437311 -65808156 -591983905 -638455355 -404311180 -680126477 -683839733 516764463 975600919 993838996 -832480193 484806911 429936102 122531607 475884888 -19223367 679941561 -231800219 918493680 -988632899 129345230 -134852887 -424422913 -88442819 908287807 -532083428 826339741 -848235304 -803424366 69238957 432533221 -383814696 503638127 758329673 179061749 213136645 608631148 947971596 8828691 -48323292 -789599484 -803033724 606716650 -407695857 -733033049 -53535651 940947435 773557423 -340682771 80794399 -992891424 -795881331 637152271 192686976 -721546701 -153143562 -582474683 -337590528 988330369 905079253 -724746155 441310450 -812849873 97291225 372673934 595847889 563109577 179956039 -866206301 387318656 -664692562 493463562 896216570 -347626079 -684548361 119661722 -584459710 -930374921 988391464 -808491301 711832675 861836989 87282334 705548129