1000 0
235018501 594193672 789178933 -371312207 -198750797 -857378559 18730911 666211134 -986612145 179589549 -942660851 -970342025 452746322 -131752710 188621870 393023355 45280589 666690810 622080032 -840715432 325756849 -99879876 506428721 -435877056 707921559 -524176464 -335858135 80888563 177139749 207545027 -617886079 911306607 747257512 -258251145 -433235649 -445933152 644780752 192137739 -586482378 -121972149 427518367 -868459702 874863282 -990404482 729295343 140783825 -17589365 185111161 -380996398 -127679501 675233921 -421322078 -654425578 889393245 898946106 398338083 33081028 811819544 52358714 -806927303 931810796 484905788 -4567848 -367912759 -337955132 -688118005 493636997 145588052 458506946 -233891603 -937818789 -170785134 188973022 957740822 235438565 613255700 925659574 -132238806 687500319 944676361 755977181 443733225 714974748 -775510545 -967873733 -863823844 -255305220 722255083 812891945 52535838 -543782784 -508979493 -361777146 42879880 -366763689 -509662531 299551820 -854102722 596857203 -492810012 777389223 114653537 -907935606 455824964 -187038288 55250829 169856446 -361041248 -655587603 -313526417 -237097633 -251165781 -557866494 36449994 -521450159 601188467 68532456 -213709052 560383055 -314568641 268529362 984412426 -399741795 -540190167 847226654 -645564880 485608567 -311119476 163004232 283514259 681206618 -366264768 -4112097 -459794309 614831043 -788301233 49051455 212727084 -473457793 -976380286 -378978026 678448683 -976961164 558054046 852739281 870746628 310109767 23744625 -935056873 518546587 -871387403 914669486 -927745808 863556365 125754277 -84775798 -799067643 -564986928 763750591 -157191501 783166787 -885696779 -761122085 790880916 852200428 -166967436 849692863 664130752 745998431 99691885 912389262 -504330465 -37467833 888320766 -104024123 -914041581 769652099 850987576 -928338655 -420743814 140202915 348123493 -828499922 28774726 -810389874 -775087279 -425320701 383561468 -306126644 -139785183 549087673 994366250 129345575 8495255 71807974 -509065620 -24558497 -693300061 863083416 -283004486 -355008843 -989312440 79858715 63828161 -751061012 953438772 -364057802 542285673 -423399358 653833876 -744818867 -390996131 445301148 -222093397 -524279835 -854604780 -49902466 650282071 995108105 -715873204 986139486 713693155 716270363 606142345 26397144 -726553293 233204749 -357600905 -919867366 -882761571 173267275 -642226030 662366066 535817000 780812578 236355104 275365590 -583691042 899961428 -212058790 -356114647 -40887143 -695538304 -526516305 384762826 193723358 -172673289 799413468 -863332035 -671604394 -847172145 698334991 821998268 -230619939 898382364 119405761 235566057 -985185682 980137916 239565470 892246763 752580852 -605231035 -432746730 91308927 -382705870 -359977977 865906516 -58848019 -633723253 842339542 182095072 30212752 872808983 488637382 563180042 -630852528 -180743864 884024339 -251447899 24112263 -502745719 818322501 40787883 256643094 137409179 226693118 -226314240 -258810835 -84960699 950782620 919389064 -483187443 296216411 553775183 -209087750 702116654 -411493278 335041859 -757243830 232728505 -141868646 208466560 -297663979 2886193 837247280 247042575 -845302954 991759586 -991560290 562097223 -540522819 -891899206 883827758 -680647046 942421920 -645530011 854031162 665144772 773450284 522766284 -14411903 817723448 744875857 -966108727 -285408109 -762248214 -701503903 181993264 424753328 -736850407 464889717 -224581847 -289118292 -78639571 -657536343 -663541055 -9304661 -364876363 180287891 -952119130 955294192 207411401 -812558647 775806167 -655941696 -86111934 723604202 -221503589 -549860777 166597106 919027448 -648273966 942613414 -671369636 422575210 238231358 -558308249 -769734658 723712820 243258013 725421336 -176764314 53293613 -437617930 -745336100 -238397842 255822616 -822007203 938001187 -223688928 234105961 -978597209 -925521753 924374534 614853277 -870921075 886566501 -678408550 747283064 506117990 681561309 -738858802 -143643352 -344568658 -986836884 721565039 935561046 403010477 842262751 254804707 332180775 187979666 576269805 411366662 -825669374 -146841039 -408592315 262474839 814649566 -522378189 -935147684 -778751232 709801930 -714917774 230599375 -822600017 482113728 -274665222 -897113315 359264353 728546539 166438486 596117212 -411661387 121873048 519734231 -144904084 -855242198 -194396400 842202426 629202491 320686999 -715252865 358748609 -576759936 -415388774 -922554580 -63043822 619001746 816921676 159869657 -4855364 -243561541 999956068 -207598252 64598614 650283501 955772748 490871113 172916783 993092803 822804523 730560948 364552461 -115520876 402747908 759134798 394912186 -37914119 654263718 -641629774 -806723114 -307917254 44052563 712404939 553622097 773807945 725407399 414203818 -203946698 -332624128 544910384 -112585897 143425340 -880576196 608946191 -818790563 606583371 -803199991 586333744 -648417678 513155005 -808370730 -416375525 -902986414 -742368097 662117857 824203273 -742205766 577371726 483758735 218305667 712664525 489163216 -181751964 379976005 195063093 44096393 92756183 -46380259 -88873450 -587632987 -865534215 -931961553 -700985339 62269973 328374618 -131402761 -225894520 0 106994482 382802619 -980300375 -747285374 -510941572 618484685 -564224797 661984085 -940219245 -86036897 94972568 744637216 -487797522 741751481 927616184 344522318 -922515380 410787627 -399228833 -979556335 -440044123 415140872 -240548686 -666707089 399328652 268387495 258641893 318414985 -553743537 -283318958 -210412114 -439249371 -342091477 -15437369 -347008627 513945533 321174400 -905747214 964139285 -923114304 -277217569 -51204131 -664446470 -744611489 -971722024 645233696 649979592 196675012 471604294 -871755052 -272414302 383994295 987341232 145072687 709033758 492049996 -519664785 213946300 614972064 -708466082 781393010 -671187904 673973701 -682323852 933143545 89450398 870014873 81533532 812376868 -335923343 608481451 -358927175 -172454819 918910160 -715379610 662840147 522052844 -870378138 59479481 662250753 -714006307 17776600 630345918 458673313 973314642 -638518269 -512640666 -35135861 138982644 -149243904 -606115925 -267284864 -942301206 -542773659 -901053773 -66005540 -422711721 110623301 950581981 -886241247 686798658 350989895 732117912 -480790092 -721927284 -112973344 704821551 721290177 -805707614 -441483481 -911809629 -478429185 86807496 -285455483 703878186 584946907 -698631968 -412900278 -947053619 274080979 585237953 -42929193 253312063 558274977 -439712135 963688736 673997480 110308764 140180810 750579459 -104892555 -988429171 199410467 -755480798 -904355944 297914251 255872814 116653833 14900353 -576996128 253102771 -947820055 -620977490 978561476 -808244183 462018574 474313269 -712885324 -264631949 -703063513 147239314 721408598 147725388 -615582374 -81900332 874830042 -981507642 355151535 927958640 497714023 618912260 -759877913 -634418008 -382471866 693597978 436210541 -753978732 284906930 -470656950 -779967741 -699409993 456397440 66574955 499582763 430669835 -61762635 765071385 -262729193 278543985 641148226 -908954268 -756442973 -652956951 -838065946 -18902983 -41910955 129055557 58839675 641324784 -35427960 702117912 493222599 917208474 -809736381 626029904 -936957563 578227324 -826538537 -922827151 0 -230031046 -127069632 -331758604 343748557 724778895 -811201640 -541568971 -757222548 -130885411 -465255668 653819400 390756336 -343125099 -382500197 -1276214 826581116 -469177195 -981412728 454800083 -748693997 406155273 -95074384 878812557 -44622184 116240690 -628548969 378562026 957583483 -130817351 -344606273 766229775 -137266521 -505570886 368023535 -233122262 423966256 220109122 -702725459 -909237697 967124126 -730951394 -503470535 410297666 625886310 617794395 -869992168 -158020045 -873337195 -323933607 13252866 998044279 -168770178 -364483111 26967760 420913153 -584619143 -262837588 -883664140 -295287366 1687496 -893962401 -434967514 -307081006 -825998287 -645628027 456836012 -973029704 -987797085 -786632829 -859602770 983304667 400608544 446205837 955124892 148179021 -817445405 146086813 -411179716 924900480 504852820 -155801745 -748421874 251750909 293267896 -725231040 874895369 476607961 -657772521 -693445437 -345081605 -500496014 114162952 825714626 -735647965 -476813763 301455336 -947902532 -336204950 -607490478 797435773 -23416658 -364838980 869269274 -982602675 913383139 513341616 -536791495 767635602 10201686 778325987 -254559389 -384445052 -367364374 638397584 -3729462 -168824737 384227374 345321299 320220085 -61930128 486906189 -450257449 684319502 -715542876 540230570 -259879923 22834449 950419907 105549767 131142408 703020954 831792830 614073381 -520880791 -391007908 -445294618 583635407 -920157475 -638941435 871494000 -195636693 -138466710 595862835 -277408929 911646796 508373442 -906419579 -57570796 860792443 296430043 -259484776 -274830971 -768530336 -291636607 508028623 -424619531 977855869 -659668935 -260287173 115871002 750560597 -898668522 -669224540 -605806566 -217692368 999344983 85604596 -644745106 803534402 536438649 -388286952 -85472108 -691134324 844019225 -252898937 18313992 -997573814 778567027 -613083709 -598669459 508815836 135742119 123540490 235779884 -177802893 659496874 783681320 372756628 -345163794 580859794 -547291260 115658364 557737287 -5827538 -771213872 -435241967 -447392899 166478220 929220779 530783368 464356676 400458511 -436581888 -922998096 -220717012 326436629 803391552 175564670 475144270 774377068 628459598 632600482 501847068 -907248583 636618663 268065567 -468620654 150687119 -620332862 -209327550 520797235 -740480536 -56309551 871822407 886893144 -222971824 -171505289 -383508279 -360704501 -178904881 779764269 -95571235 556593400 803507791 -772417225 -603701176 33865493 -475239455 -929152794 66613557 -801911115 584259426 508574478 182992803 -622479639 -8365297 -603698018 214337293 -301076242 -682610826 -5656194 726164207 491318467 -890084355 -326213184 279305623 93304925 714185806 -677628966 -998838273 645995001 -623391626 -148903478 401435757 818537478 -109968815 679077860 -982615520 -468637280 543948302 -84083889 891877912 -446678380 914173006 946266060 117149530 965993141 459262155 559949422 -468800683 -901361972 -138026723 369517191 237209918 821578095 -412276176 -812252209 -3749350 -252231321 -105521627 743169700 661652351 540474144 525543956 -36060613 -760563555 -920377446 833472517 0