2 1000 239
454711710 -553060506 -687613541 -403309102 -999750803 925870870 292744451 449795830 413217703 -805632104 465952601 567666210 -991407756 -619288143 557885092 -724685589 -935090222 988358799 -733579528 206083336 -416188303 -111057756 -243163229 -396019066 773876265 977154932 208641324 596286293 356607426 -338987538 216741147 -992071805 61969011 295379472 758260493 -742909682 555154683 -680782630 -140087271 -466654715 -188681275 221010298 -544999582 845476283 -500292570 200363757 63691421 845967719 -555498095 -28551146 -27282742 965497230 856950987 140760860 -996278479 -175362747 504927911 -759182469 119489272 577556986 967202653 -16364278 632391901 -429989515 -284422448 -833543338 575465796 58432715 279664051 547222058 614266149 -750179912 86506946 -4567256 -380483646 74952192 948340803 -37074242 -814738006 269375514 -661241780 -669607086 -780282056 23477869 787253104 -450538932 244363575 619756584 -530627924 959649627 747637969 -967468314 -240995671 -489597980 -480113280 -112299654 485609819 487614509 956247889 -976669452 216921954 -95787585 795073903 -92222028 923564472 617258024 931873239 793239145 695059290 -26467655 -63913023 -417321317 889710832 954848082 -549197015 966587571 -875582760 -52752227 73149581 -499333716 697107474 812876363 747633238 282039785 981363976 920628008 57802460 -556574717 -176390931 659319836 -363463813 -384533201 68141341 249817348 719932822 558933833 -745535707 685893703 -928104010 -450447500 -471162495 872748096 830389937 -113929135 55835659 130817892 68518317 608107746 894525358 -797723433 -22800094 493173040 383376531 142431225 -177053141 -869349684 -678158894 -119999215 -270931651 622433224 -623487950 -112077949 854157157 -843780006 -163297609 -173781234 54649928 -589631396 -230224312 -68203691 -443736696 -588229102 7806864 -206734329 692179494 971416673 -32916372 -858168121 647288473 -121983009 718195882 -719503946 564233397 -288140203 859079869 998887459 205274454 -975063098 261048740 373807962 -610947615 -405639758 -496231752 -110895674 572957588 33913301 -727185502 -997592565 956701290 330718018 -660354467 -859133360 -313796007 -227031158 890282306 398235624 -242871178 -712060418 -669626993 95500871 950096887 -434590284 739941868 249358254 -861458357 503199055 646828425 -713372731 850343262 765811762 -554938667 280290705 -590104018 -364680308 -921782591 706147163 802458186 361827261 219395391 -284753147 -51905641 144030833 805575363 -507551265 151583502 -218255985 709792678 709119398 -9658526 -458502759 -380652935 -194931791 167137756 449861947 -372727629 -441637593 275850184 -260521863 -912334350 864903271 -275704359 267916708 712965734 451142969 297848926 -211085279 -557382881 747179167 -487586092 315592200 -633703956 781129093 -993202312 653030538 954055402 -744768979 71163783 417778406 -986806914 25668488 -715801430 -795016872 -841039635 936871095 -455034477 427976608 674813544 156161423 -908719726 462687707 -374386207 -30024820 -720131486 455382144 -916407992 -75025448 542788367 -488912834 -612863025 -817816264 492226734 638820982 570241048 92246809 -651106547 -57385385 -949343804 -916991176 836527082 -207528133 386446719 -721210665 -626153474 357439129 584264960 -981818602 -462158910 670688080 255711889 685350475 -597557403 -67895272 564089850 933898326 -625052080 -314435267 458754195 -19678863 -916826205 -79086976 862644731 181103157 -695661702 798930158 750090389 -969697992 -426413243 364283935 -518586507 -132079898 -50371240 816139913 -216552998 709134777 382040676 897787823 -805974767 -398883639 -652278066 -478686667 -495501534 -303328236 -551849521 -665345889 -22331701 236977675 602756989 -484887358 409127805 324719038 -718144375 20790290 496409196 341738636 -512765064 303262509 -639289755 536488459 339901068 -747040048 -33986181 -531192055 377288984 702904764 -67478072 -447781904 430024672 -828251383 925026594 177915881 -618232907 996448748 -288491596 514958125 -52393054 292732513 -568784808 787451299 20900284 -590970529 -495292979 -58092688 470700141 -243826218 858039107 -281357680 794166581 -827589915 -726360867 -504142454 -959896428 985826193 -802522723 -920021178 904268041 932708797 52787030 575967605 691088286 -88413106 -542505729 -39273456 497511623 722853558 -156124271 -407479067 756048973 -475605440 -609124338 793923586 -889681331 -212888844 -29011540 -884371033 794850605 530578636 -102630229 -927149769 -143607362 -869952851 293195165 -330332023 294829359 584198973 893473757 -643414710 589810947 808234731 362702636 816016117 -586785706 -764186313 114989932 -47336936 217130151 -559951244 886373293 -190452566 564044544 -84827514 184595727 -142911064 -638253652 -819642825 -121608511 -916081296 196760535 -298680712 -162381613 -431474879 587174427 831461344 931685112 -189276906 -128701354 427226171 -992059485 -821145989 -613652852 172127204 -691454822 -499213649 -359612873 -14044954 561467140 763020457 267730273 -129272604 325125737 -206389054 694173767 -413374314 -145931437 -417070894 312481974 -220266890 852021573 -617740271 -434936863 951925661 -320256165 -632167874 -934423748 -521952315 -343516877 -700948796 436126392 -723434729 745116520 215023076 -641948418 -355442641 -92309098 861192494 671243914 -116413701 568070048 -563052234 -332527212 70973514 501494615 -118989292 -480045714 611674522 -298061621 -303028509 183021114 887700793 374486634 434499237 -832497704 -531473455 -931887203 416740989 309837233 -865000900 396211246 -987548984 828474910 -89284553 -60162264 -544474585 975234168 -173224358 -627443039 606827889 -453065631 -996816317 804302840 12974810 -106918450 31643888 619252807 -495391061 -214016160 530497157 603987520 138979626 724317155 476621891 215288735 409977279 458063465 -403958399 551618121 -10273711 405964249 -169722082 -724300197 349702800 649140380 -115928782 -161877293 -648734918 601929407 987574104 -299772566 148984530 -718722310 752541961 501225054 -979563249 711682435 -819033057 -989139284 448435901 -999073080 180809841 -146990290 -686706268 -226806654 -484451087 -37865402 326560584 234067778 -257867963 52324721 386410300 -167793952 300371618 -684917711 -783939704 97701305 -994529611 -404181516 -589130362 -551452671 -284263082 716100864 -479216134 -267250900 -602648103 -143359361 -912823742 281536772 -281553591 758963581 400800497 -662049109 -617558558 -143325730 -727319415 -217898174 770016502 14323124 -953045425 281433570 509931165 163869809 690010101 754470175 560848274 -747938605 -211223555 -553341458 891439787 300573914 754138083 501552483 -699656079 -924716229 744637330 155542791 -154397363 930191600 -214485044 767032559 321717713 951476194 -581892577 -500703410 342952688 -918098168 -362024657 -662746203 -511277580 670112797 -538592840 530068410 -193747444 -799597648 -388174380 107858923 -683541023 448665550 -74294086 119971467 -692889517 199906590 357342212 481221128 -761219907 -13117408 946841948 -774511109 -873061639 -528342339 -802280878 -572076873 812700791 -776589757 563722972 781987988 392386115 483700022 833960559 375411461 524224906 575395429 725408464 378224570 76373527 -523016506 -575550312 -391689551 907880990 364968067 -132541440 -471361562 215284153 830183664 903343918 51691875 -10177359 996695703 13351482 806717012 -520184737 -800126710 -531294083 -819261218 110798799 399489859 -626505739 151614880 199375096 488371472 -20334906 -881259712 -225168224 109283384 -248042455 311536056 -163095660 977803529 -694519145 283032442 297159117 -352585056 -930887433 -45231846 -624966274 254329827 -58858661 880775810 549977345 878329339 566739338 -19174271 -463957443 247203983 271006604 -989214766 -219299714 815423743 -993266621 382454636 -392053275 -473743849 791993967 -802513012 -872869316 -397261271 360102765 620990131 294698353 -146266648 -930119881 689804880 717779490 -423394737 -546529804 -470252576 -260683378 678689790 666108867 274668179 -427459136 54449195 -925728420 631974879 860241337 258442473 175901518 82803789 -665875222 192419034 917544539 606243002 748173751 -204065375 43427275 -517221147 909069709 195744402 -814635495 270160383 -326086708 -321226054 818292076 -825019002 355502610 448884197 -65241577 554316687 -949677119 740911686 -738885457 -533747335 574557695 55296334 -937146611 143805883 -791202328 861223762 426395782 -307271041 289743288 -437016332 -622958680 -202561441 913663487 -883674028 347299396 -492478462 -755744909 736577755 744070777 160876367 64965995 -612983844 -137683988 -354557227 59955661 -269141805 825815121 577240265 -325357001 653675161 -436635962 -505395046 -224489178 464950683 382886229 164554851 171374386 842737586 781488660 -890679895 369466811 821130035 -892608031 180956663 -827015027 178772720 -859490197 -846793057 -110841505 755781929 -721142763 616330008 -708647143 639082050 845961451 -594655003 -191685479 415049245 79867598 -500218716 -699331017 635162082 -417865301 711998486 390033881 -582871196 27744522 -135435411 342558515 -780280932 -438418026 459445908 -551625037 -606103936 -503975850 -767043601 67137066 -395053312 -683577721 -593535693 -911810037 -417409563 588003599 -542764962 951518940 135272403 -479607022 308793261 -134206211 -851528695 -276342471 615539624 -7233048 -475631416 989002867 -221342221 -875136745 -560605530 240298229 847389171 -372280244 -670594023 92325090 34911448 901530744 -516463599 -888680403 855125760 642535768 -966339620 -829402850 -54634390 101342243 -810795223 953704506 917533403 -625162215 430905776 54895998 343857207 -737626014 319256024 433019096 713224748 -920261161 -224428390 183276056 -794807670 -274168494 -897113142 -203965472 -121110109 696580029 -871976462 -300152098 458114332 283330178 35712868 536096373 43219441 -42881614 -978561756 683289901 495552290 -734928327 -216242424 300250933 336428025 84737415 450319324 555486570 -38134835 684263053 415273765 604563482 413163034 478023534 -334722373 297742763 -339682968 460223836 -760685326 239274142 488776911 -29980401 -141368923 -986431047 640324901 -103577266 594154809 523413526 -888480557 434236905 823169296 -492580124 724553134 -582110417 -104022095 72125655 -76437037 -781674862 -154628796 197710069 -144117782 -38184986 -952309649 -553220484 -281031673 -559024562 -238322726 585010689 816343955 -588959312 -232698999 650770519 -397393112 292348123 605741828 462203646 271652560 -905126746 -487909010 353514802 -740680055 -670070155 -718816379 327334708 -502591491 -204030355 177816075 -797325579 -92107159 15452296 -121179230 615557275 366270646 348522302 -703457098 576730056 645764037 -30628744
51924107 -92265946 -482583665 610807337 -690198207 -436979880 -386945145 968286190 -381973143 895927959 842394959 -835500980 -919106912 621804358 335147069 997656265 398546635 678101316 576523450 -761815936 500300426 744005397 484434258 -225305918 -884919867 240070953 552433206 18575456 413390525 443401788 -544097754 267423336 -304634933 640474316 -39346316 -61183733 -825618837 -346550493 179039100 -696007831 -495404679 -277503333 862425347 650116717 389556551 720529619 568517292 -260305725 -462301485 -104092997 -31998309 -777252193 -900695163 -968021128 -625097285 -963744484 397708337 -580766601 -398373899 -49614330 474902640 -548732778 -356328358 513176452 -182980379 568290814 -229728195 408867193 646319661 -110229775 -59492780 161116699 -482684356 -775201264 960358001 28521127 -68263641 -451059257 -165067565 -184259937 338891174 -203686410 953747910 -707190008 -901079711 980453379 -984148260 51620036 -143885650 -332586343 179523477 -128508230 200456155 331605355 -791701509 -239985304 336772766 918295246 233857919 387415482 204192037 -982642035 109899359 126596420 247870994 168559488 178898109 -383974344 -818547935 25866837 -408104436 394808882 983750386 -761018597 -289765523 -75579588 807748630 669386010 -392808524 553137544 897646883 347700460 623429784 618621308 785744608 -720891144 462037914 -419231321 -387672096 -409508531 -689982448 560406124 15379295 164848283 251856950 -719241378 -294177022 197712245 383873417 818330415 -44668315 768982061 412934513 682184717 -131079107 -270342401 -907592345 567994271 -795007725 -51358536 -302651984 496105700 893391337 537222780 -669873854 -867227034 874305761 683094722 596440071 894810326 150049208 586350196 -352501383 945614233 -180602708 -793223399 -238710078 741448973 809859191 404818631 -429224419 -451369364 121414652 -916079609 -176884695 -577576441 485501871 -2054648 524887055 824291189 197915670 -322454509 -560556348 -275548677 120084197 928184260 281331881 867902628 -801783629 -776574563 80527668 -213076997 -99081942 -244828713 490785376 579107359 -268578724 7733505 -399151027 328229515 746228567 954934376 -34220676 93358099 -455326389 -354756180 -951333718 985617037 927418488 -183556788 644834966 -515822136 -942240435 202404340 -943748161 -262800000 -400159593 -11697306 -513319111 649923514 -194245222 436446090 815294654 -86860564 -641093766 -934676137 -70732882 462663293 777067614 759065992 537605063 479593221 -716627728 -266154135 78002524 313138504 -994970534 -595663311 58299450 -435763071 -989305353 964191403 664739759 -356911458 959124580 -97783024 485458711 -412393762 103586296 322085287 -187758935 -32958384 254748393 -495253242 -978684181 796150387 830993603 480302359 -56131006 -263436405 -261845202 -543518485 932247548 -864136521 -485514276 448474492 -9964419 957430617 962852353 850667447 -967537058 899508803 -59290426 595363015 224497308 -106832348 -175751193 65068467 -310862821 994765792 762292800 -834932256 -138954710 -838995005 -903628727 140601517 -311635559 292661101 -493801612 -716453795 387192156 -692344193 -892808384 -729373046 -537905097 460090111 3471779 53007571 -499088690 -583414079 -255545213 -260034544 876246325 659827780 608087207 -422955709 967941271 -267454059 -968930925 -579202999 -932889868 -194808787 851706906 515044930 535986458 -984340977 489748501 351342511 -514443536 29836858 -373053894 -525446821 402928125 -888693659 409676715 118806618 641264310 674177591 -598786846 -570403761 353565334 958671517 246074112 -672309734 280269724 -899340960 306128208 561256448 667357215 861389752 179682310 835816019 294840586 669970456 494294681 -937685883 221552636 228567343 392488540 875754960 73335436 657058818 134989228 -964415286 211534129 60368739 670705097 816859731 645735302 -182937058 -319315007 749563673 351867226 906190815 2565438 868714274 -87316921 596884012 119262887 565977391 774074145 357728392 82328884 374197285 976632149 224420324 674017313 -476690583 555934182 -79799583 650275730 -720153323 -860093715 -924988796 -800738062 -944653461 685128337 -822557198 -982360656 790061593 334294573 245190631 -517654983 397344419 -168980948 -347648769 390608870 966041747 -879834707 -643719544 304829887 -515281859 -319388659 -114105506 -943280410 196750501 -565105802 611314653 476482867 357098148 -565408192 930490276 -903610448 279847032 893241074 -902649076 -663212089 -787154966 556275796 111242856 -221112824 -108798542 -670265393 381049422 480793562 613614716 -520229136 750479244 -826058997 -328382446 -531529647 731313458 54312652 -820337115 -814485320 -780652185 862439421 -737783607 261289424 -224515761 153897746 -19335382 -222742547 632627389 114734791 -495823129 737622780 -561592963 660163411 583565983 -674867167 638236264 -916679854 691777253 475802659 429247881 -219660839 892366210 784880486 315965180 896072356 976083058 -316736251 216391322 -379163148 -433415649 -270435284 395536015 -772276714 252285071 -446653726 167065834 355577413 -295892016 87559232 -204535026 -771207095 636426664 -642712282 -882835054 228509665 -750379478 455187796 459383341 779030387 413469491 -736457911 458850828 -810904954 -667375220 585850905 -427485051 466204893 -960721410 950831332 -86413001 203292278 -995346764 536302803 97681587 823141665 -443435067 -766291811 -143918741 -51894022 292922471 -89540621 -949680564 -604376350 -705873378 251932459 906757147 -604541557 -573170055 -909104762 -973913914 -104883408 -333316731 -606301568 249148592 -125916120 660886998 452916926 -805569984 -166128445 -756004810 319156557 771281689 732091716 -130764751 686369795 -355630903 -905464912 -638979154 -364707080 363829711 856765660 400566279 -223994140 -376319083 -690509812 875055473 650128102 -775221364 959251115 -425903578 725000615 -189937520 275114513 641258050 -711184059 -423749048 -967645525 545557074 781541724 864050608 278184412 -254167315 394099126 -289162 -207874853 -598058635 -142392212 -806834977 -273564819 -940542176 371644043 150250427 -888793824 916994935 222316588 423291233 224276758 461949326 -912936336 -326512528 954667335 -696663236 313194684 871609784 -716425192 -952283296 657345732 -890968185 134319035 682755580 -584804630 -745854311 -414896869 -63134807 101912660 466942343 -275529937 -486530532 553329252 -581211665 371092501 -249677466 -235244302 -5436453 -932403297 -12087739 -173060036 -386480156 -358759550 -34520175 9947867 648198085 -15304640 52848987 -478268247 513605501 120137931 -382461773 406166707 491465669 -288329933 -351338155 -879426110 716903655 667078567 -759708919 -282327508 172536909 53525053 -58332902 -52124153 -652649045 432803616 -455719671 503227657 -385819740 502920251 543021260 -356842969 -810676547 747302218 732293641 -209793758 183640602 -164155915 677890464 69027799 -441944090 -744466997 170696363 -442224633 -466308810 446787203 795812465 304491756 799273146 665909140 562906995 872585229 -917065414 152715948 274928292 -274193703 984352916 -768607321 -651803259 91074214 -689031957 -414054768 829247142 -989213192 -485659891 550145927 470839577 -428178927 949884989 355961035 107898415 590702489 215697623 -690351464 -715389967 -114160754 -13664786 -924399408 564134087 -820461988 -37152913 71609208 -492389462 -534383668 -766117977 541935659 837823627 698961054 733751165 635708955 178951382 -826369908 -690210852 892153145 347351538 773786961 637163383 -158478746 371526399 862271618 -58634221 72796922 -482638386 302083351 -856458651 834224459 283865707 637921899 579196360 -357728745 -494918045 121078780 891845150 836456919 830980549 -21187827 -385556028 794638032 -617752099 -248892751 596758886 -980249975 655704669 103159540 -812385194 847844536 -791461120 -801933339 612285420 -638314345 930497020 458690295 244312064 942129884 -683159522 297701513 -797068855 -335639494 -630591346 772162407 792316469 -56332631 -813836908 -50286419 -377088448 -823639304 -755987719 -509019460 -664096306 -402705865 -590945655 -909841235 624792003 -168763375 226406071 570920998 -878646100 -420206863 -930631472 505038706 573129692 605372676 -366217834 48443945 -671247992 -660886414 344822924 970554445 -345279113 -284196108 -158285915 -481869011 948243824 693031532 -224333489 -71612148 827158768 336360217 -221012124 -120383351 -151976381 345069466 52116670 658016630 157100811 -756872482 296766688 -196603188 -696078024 758225772 358667396 -490939286 693407336 -282794626 473062071 687942742 -879448837 333267078 836209864 838467306 -82818126 -600473336 -298437657 428533081 73814390 654894118 344206612 508494261 518708451 -864142092 872133644 230053432 966908877 867480632 -549861305 24752806 -633719994 540623071 215379786 -836535450 -243934246 904863597 599972899 -899188178 -895634240 236146097 -752452800 571899150 682498248 -863340440 155480674 -986468893 597759486 380181076 106658805 -967371516 835080447 -421304055 -302350563 950797515 490665562 -763251129 912061786 -923780148 -62662462 -256299098 -176369225 -692835235 453663854 -344120064 -213179969 -839782613 -244522667 762767626 931710798 -758780284 -908855816 -704481770 -693619613 983720784 -627901336 -232018500 -137722988 -240564480 106539754 350566932 -376137800 631800455 -584458812 -419956056 250590855 512494443 -467626536 388578836 294938488 349550362 -62837303 -240811647 -884252032 375926378 274202908 647578155 948751544 72973289 611336835 -59966706 815315249 639302136 19966555 -283997146 442154217 -230349567 -655506809 -510462061 -924811104 -232007336 637830602 -903754275 -954305502 -215702853 -242769879 521681103 976083006 346960015 -552464669 -990358824 -617160582 -613705545 763454998 976199537 876352092 -128759211 82961456 -738425416 -431197053 127919375 772520569 610031414 -228992756 271409079 -94573088 -501074296 -326000808 767551193 -223275365 553670640 -563163956 204351582 670232376 -613191814 952132163 308462356 528105041 -981445572 -79227054 -719409619 -821094290 -159501796 -105428865 -18116789 -889735716 -182365919 713339679 -328919088 -173805349 -733971022 80989394 -723948466 -208346118 -126819357 -899489702 429994129 726763575 279143816 -708372614 -800173922 -671579951 -290371305 -449484402 -489612365 -491189243 771459876 727969355 893766553 -610925834 -135574480 -459390526 510145122 -609592236 -3337875 695348886 -551585731 521936955 999915659 672524653 -18745609 117890544 232612614 -600612185 202994802 642531409 124939285 -542444649 498991648 -920650734 215352705 -296656702 -807087047 -914314267 847937758 -398308807 370247013 -597105642 -132691050 795764197 66755756 -203887413