2 1000 215
-184017897 745263950 -160950502 -100286085 -544933959 -497220861 -299951146 1676238 -797520956 561230247 18354330 -578879751 254980579 -156231794 -136183906 -102095410 214293985 452676101 265725743 17155976 381790496 719586045 568741452 118581326 988726058 789226861 260364418 -958330882 552349208 -488845133 508090403 -715605923 -295553974 48079433 -306499600 308435940 -497078376 510390632 170745566 -340665050 528367581 427474184 -857417983 -61457289 773786249 688550903 494737858 -361022366 -571938724 534521739 952658477 -46536508 172479302 -384409984 -373551439 687374439 714416423 -857101049 650147990 259063073 22971558 287291985 -864441531 310058380 303861334 -517867428 302087119 6531340 -825990725 169994246 -209105666 792248992 55713268 780724809 404167542 -217855948 -931322003 -893420087 -51274325 832303755 856163293 -107635002 -146756754 370585096 459455878 424445006 -517651204 85563183 -371845960 -541546959 950908525 -770489052 843755066 783661236 -810738680 185649702 -285303773 -988482254 -601211087 -614508359 -140924935 -73676721 -831240083 -856764862 849179409 821302623 -665801603 -693849160 -369887688 -342663821 949233230 -742959757 -925952173 -379072535 440086483 -21419901 -443420183 223041354 44205261 -8832307 481208724 -105609393 843709034 -961172508 -172653688 -313034622 -228585288 637277260 -238790035 -931068616 -72777614 -504193954 465716743 231933813 -593529052 -691731860 -627267447 786657269 524680830 365586309 -942881532 774390668 -138142059 -162511469 34411894 -974005982 -852436370 -799506215 25230252 -510532964 189467272 -542871280 350381733 -771463833 672322374 -874471580 -354479906 870623047 -842180540 94008256 86999052 864652450 -843233609 10041013 877409767 -111167759 793371570 244325664 -255099981 -455504797 -661321854 364345886 265970464 305575526 -556351087 644450058 -916551736 288092461 -820001386 532524238 -506711081 337391425 395620051 -237188102 787873247 -305526556 406167429 853868339 -775672271 -120123076 647738917 -402969460 -858032101 559003292 -159210673 -924509419 -263290551 51331026 608100213 -969750210 -268630193 -47255650 122640602 -325628261 -374136775 417865737 383488516 368451815 101813604 -983952803 177121901 -220684063 381425603 -892476117 -308693619 -329243102 -317294867 -10373993 -943036472 -741057016 -149502604 974375153 -924995318 598386032 -269823098 -940788206 -245969075 -142450491 -351857999 170656008 -22785225 -750147194 384374779 118882174 866368296 465026822 -193855884 226709641 -337680926 282269909 -647802694 -573818631 -136635069 -500118199 423861388 -127120213 448545679 949336696 499747789 -607934910 -834871924 331416543 350981837 -296010693 -564211561 -371254329 265841641 -141927366 -238329822 544743579 -88768741 717430512 -50295894 -939208808 793904871 -663210272 -121013946 -386748040 -316505019 -709306459 621940502 -623048662 234612524 -157709060 -513625523 576696377 -921297342 939226031 -918875180 -539170975 423065008 -524674968 -729989446 768860755 -314310079 784571834 401409742 122081592 -554079898 240723191 -837757679 493228794 968181600 -413476520 225919428 -464565053 916601472 821067838 -990502004 -444222228 -315015723 -731335304 -648824262 -748524091 391650434 108295596 659221442 -950851296 700157473 606482038 -676851559 -265748935 839732693 -481523703 574457248 -917684864 -514929380 764483828 829307654 -300684588 -490635584 -516805198 -726220310 -779369786 -441838449 793594838 924073330 347165354 213573604 -612243846 938635760 314228236 -466620262 -319979694 86917544 -534070944 -87331012 125494695 656327902 424950086 193661440 168390048 -395330007 118353592 173620795 -764463446 18025026 608715683 464677478 691140381 -993180005 158263942 536924522 454658457 57100367 -885463009 675554606 -760166388 -664890060 -809085725 -84703534 648890177 607074713 246830119 254547183 90246555 355502066 -687186886 348337370 -916353093 305851331 10958003 110277836 150454674 -512423369 22206507 -78135255 302343902 -789425382 150405929 -768218875 511913983 -860379614 -101675653 -623399698 704130439 596491950 -957785460 -1774022 857401012 -54661086 -368668696 -804217385 116330916 56530741 -221299102 -744987659 -514469501 17269802 635415575 749551203 782625569 300207283 138828678 -353033802 411666113 -819293296 -623794520 -190446560 -816933739 -763544152 -75503324 391921262 998365294 -461486243 -741033264 137910071 944367390 880334781 877528312 -578887638 615556267 102146233 -358326305 144215297 833876516 -77100845 419182571 358702575 354392463 382000411 98345139 -24757779 620560166 628212778 -570632140 -628396942 -285311135 114917783 -976816265 902466489 -467664547 -385960342 -922362100 969842069 -241934712 -464061404 -303776717 -976771274 -963480973 -872144698 702292645 -940172350 873761350 600624027 -778071088 888944208 108308370 -672473100 482488538 -901744417 -459309799 -146950693 466140809 -23914645 -906341213 253437927 -545812453 748262426 673654520 396685617 746818696 -457242572 422180967 -93011026 131199097 -955539757 380931661 223864743 74409558 -211821457 269765726 824030545 140280161 874962493 -22410237 -99616340 -553581254 643530917 -602362267 -308742490 477820964 343397792 -38042860 880913089 79615865 -986850969 181369825 779798081 628823659 90730672 543051952 268225688 751903139 218752827 264221324 119794896 -641591516 -50754789 690888248 608279188 72658248 -185644965 88285802 -287458122 994574780 445645418 994407485 -467835263 -721759613 -848349327 -137868976 -576700456 -288332983 -676775484 -368915762 -512838233 633691735 604398494 -25652263 502689002 -817594742 -767771947 755606339 -659463039 -527803368 272141342 424128677 -844882864 315288551 -437955562 524372489 635814283 -884799946 68942519 -909478564 386736393 -277382016 221058850 -971089909 366677331 846915138 339521771 -706757540 743058865 692511869 690582511 -356313224 477543353 -331662391 876444023 -502830648 -453837042 729866178 989188206 223287695 -983758426 645737529 842184909 -869225031 -405002690 503121519 -891556565 581570465 -256296680 445648255 243913129 -425425293 854515438 407361437 -475955174 -209873990 841190168 -404921350 -758119301 -312826050 -538429403 -357574874 -186621322 -236217951 67969003 602539301 -900723236 -407565376 43757649 -888079521 -168868701 336981159 516820659 65710651 -222834711 422945698 -804518760 -202668031 52717127 -897128557 -963064994 -351083734 585948617 -947003992 912144955 499791345 856200595 -820613657 820009529 505954214 863623594 754101285 318853904 415442602 646048249 -499684475 -967305093 -648471550 49208424 586148349 672692520 -810620267 692990425 -860344507 128837377 863420930 -59964310 291934832 -857179640 234691460 -353091411 133420848 -900701370 145208655 -747209594 -537473240 -723455979 227635680 938766196 -363227086 754594299 567544877 -343116331 464244834 -868680829 -439744965 751834943 464344386 805295551 681657428 391530388 536665508 118473502 908218466 847388505 -610897650 -425234978 -995423447 -457022073 804875228 277211753 -374677154 -693742075 -883196056 -665738367 62036021 -265201930 -231952808 -955149608 350933744 119772985 666019121 837300076 5212978 405207265 -778557575 -149395158 776798586 315296020 -839762580 -322978983 -964709811 -188444899 -886180129 -316498578 -965773377 -576300537 757043524 604352764 -20924510 -396419707 -841825822 -686428594 798595288 -146327325 -746287217 213569383 -223169019 710524156 958572182 -505540125 -597934317 799057875 577978194 -230571390 -936625849 -409360607 -815869964 -955215795 43562964 -462634008 -475570179 -625691196 -680172378 -897843742 924135152 -55408886 537127351 -324205078 -915215417 -54252697 -367058044 603704937 416717172 -270379065 177846710 880561051 -45406980 154477750 69334714 -635633980 582872170 353081670 -286245241 -931139379 -407586553 796621267 -596649607 144801873 305816761 -929401733 456758158 -83109787 -795495251 -52421805 -166899119 66619305 -515932428 -213759126 -8570151 -905707528 -558714742 -106393900 -117802027 -427117815 684103639 -243383763 617915475 464436736 -649309163 219104321 -73147023 282826689 873612318 94598360 963705191 380225767 518397557 -281703815 862529481 355738044 592996528 185283156 219989850 -869833907 593768744 -497327504 313486321 -588586469 -356134214 -47305513 552183824 -328950149 853801181 -354103872 -43432672 -306401666 979483410 421364646 -704185716 212250243 -971378138 145591396 87157821 104415844 683397803 -980388963 831371320 259865745 -811648029 -444787208 93605751 787668604 -146091710 -887580956 737707407 918860636 -934887537 143232999 540988630 -18708264 -964198447 687594630 684677340 -782778858 863325329 60684804 -515419767 -624951057 693118737 -822936416 360302091 514348714 -855602125 -826253201 -268101988 -955322421 671981949 666245783 -672701865 414117428 895204757 69476856 -494689224 633329877 -766584756 888133176 912891793 -980272929 206439432 -969013795 938458045 373544388 679600918 488448662 -136776225 143273449 -114149614 -303730636 800346266 -809324218 552380111 -783800010 974937973 138909556 888967186 -396927512 -586372595 236528458 318577333 -726724998 665187755 -528256022 440752906 -452948524 -331794620 316227766 106206049 -598989965 -837312698 498015955 414416764 -410792612 -143277960 850339519 300981127 -331534225 594124888 643945173 921740607 -613603460 735393816 -691594046 868096192 -642779323 -97269647 -37561203 -845105945 -984574429 339301597 256987347 -469679197 -857701072 -551347362 893426590 498408097 -294707034 -447920307 -4643988 -401371155 427804588 -449184065 387330743 -894484404 -451587822 272900862 -444043333 768404110 -269699716 -553293069 687474782 -316454584 617595702 604536976 -362599068 264116525 368926508 204048161 -142530065 -168329058 -831299747 -945935133 -378556096 221984588 612985297 971347287 152120939 43831936 370004755 623732679 -461620037 -699678779 -79378381 -990982946 -876458623 820329719 276109709 667175887 108220730 -802133485 989407312 269198091 289718456 -537294133 -320262525 -119085204 -268569927 -517297301 652885277 -846480790 -643410848 653969175 -963936134 -150514019 759286127 -934521821 -613581464 554247710 -112659201 244547330 -514973811 -416403040 54147311 290223619 -127599168 454866129 -138119902 501089133 -610105784 145766206 956772776 -496950771 -810826209 -268117069 -75364267 845600746 17428140 -968668092 932367127 973054197 992486930 299381792 -146898743 -397591721 393480045 -701630691 -762410146 -369848885 435416749 922048944 -674648237 760879977 9841643 401999825
44038955 240274907 -277553167 -602658953 669467305 -828682362 -493095379 996790940 -10900470 -78635699 -204570843 390599855 -316539311 246453422 -222411534 776126124 -864068952 45246428 873916012 -418763627 -135369480 976896652 -87475652 -403482506 -762478458 -18231393 329582981 81754124 807788847 458953081 788132451 193420750 -848369222 -799961924 387187764 121114002 -925694299 -170780265 373989066 -177113150 835224607 -163462841 -390125741 191063238 -415314905 495234647 -17318988 -572862000 730925022 675907623 -622205802 -234415098 283962039 915751520 193400983 -967380129 226925480 -704051298 772838660 990786773 148781233 -816787206 44961635 445666777 -875465698 -949506866 408019856 -414616983 730940541 615219869 112985118 434274422 -461339310 -698598976 101873926 -840422656 551658339 845557515 243562504 150830962 16430386 -5593975 242467318 446782310 106287568 995905237 204754867 88627425 -192040330 264223545 620462370 -869028454 -467050742 790328974 718970836 884489007 649813668 -679009938 -795828287 198250058 659890834 -604213599 -493331548 608591930 -36846307 -123374802 -119150995 165043892 748509339 -207375148 -91677180 -416771632 -359729550 -410698000 243529545 -583897328 782099804 160388562 -65887869 -861864638 -981550060 -969763691 19603074 199181114 -305637934 27177707 -591537244 712399009 935103793 -880419742 -578597811 -245615133 107774414 600272146 -409273793 -954519949 55271601 62799666 261517685 -520017792 97505627 902957087 70256307 273054436 -674232655 892482312 -203130412 601172178 686752788 -284442822 -546641806 394378088 602636433 707344766 209167857 977986278 -968314366 -325266051 -79250864 113395323 913406737 -330402163 197909856 -445454215 -200215664 -441603986 -883677679 515497200 -340488033 968935247 131757319 249271587 138436716 682515057 -93789025 415021958 132038741 650885768 -240548228 922916955 -973991084 555244349 -288234426 -903506555 542572312 -655838866 -942644651 -279855920 -942280593 -683937831 -11811401 445008608 -919655157 -722727061 -188749291 690240027 -111026687 620859376 275168811 -60556713 806829507 545245311 -997676763 -232604380 -721504921 -786486489 -722253083 -669744909 -219669675 -340815629 583464509 14440837 -206518992 80171175 -823189086 339167046 -426337877 236347722 -742986745 373880037 -589059034 836694817 457644632 -286314765 -386798093 189219078 -417192800 163092861 323676590 -208356636 709789222 153148399 -930497246 -803484091 -413600029 282837880 -862009258 -398712967 862127146 -609362281 722948587 10953765 951827838 270887563 -171440707 -603839490 -666062415 -969597643 625350698 504625956 929644917 215572279 997030169 485888183 622396774 445926387 561257974 -378435019 -321363638 939463287 514874281 770808971 288765326 949514692 -678754390 -11051261 408361293 631812078 224893309 403441886 -565879598 371396213 150540971 139366873 559558349 -378101881 -111200039 -816628207 199229394 -73027039 579599661 64833465 -986318797 418626059 783262776 996278367 604512968 -845969381 -391655320 -403542211 -383081368 760250289 319487585 -604266289 -892640457 561382965 800359227 -323150795 999194783 -866632444 -222082386 -611861408 843061566 338165924 916587632 -622072727 -531094932 232926070 182840264 148796226 201749407 911548243 752262364 -938507919 -455823119 -417748758 337054811 -241466825 70887410 615596294 -631362851 -83935125 632801808 56022082 -370075132 707996745 570774131 -875168553 -439719380 137963541 339988329 -31161817 -211937813 -847246007 396707396 -347422491 562681389 90322209 -856554793 -401399061 -657715422 -653756952 -929452355 911345450 175021840 672591384 532368320 -746434433 147221801 -112571498 -91121889 -161511083 620793264 -500147737 801723211 -410001618 654047258 -449600311 -339602025 -311092015 96730396 -868861671 -853485941 828751801 793069917 470396330 -777576406 731483393 981929883 -835317181 -744478073 -383172911 489424070 -269112358 -477464901 -643173362 -665548830 452446892 -409487419 542127335 -596089158 143769406 919810160 726020672 498288483 464043535 493413013 -524767417 -855175272 -881670759 480710787 -577206165 -558224469 577727201 -238387438 -665484403 -694220585 -253302078 -347257370 104269953 -79225911 441656970 -715664077 -460440205 -724404100 -71844478 36095382 -949824689 607881862 689136332 833979716 938708040 -769299527 794658565 -136007331 -240004334 -846829234 787743240 7334732 -41369109 446852941 432038839 13411555 -515501017 -84283747 -872113584 -957243399 -776465723 -634655754 965905877 -478371893 -998144164 65501079 -459081360 -627991829 317483105 -615092951 812658747 717125843 -123275807 397933981 -226703422 36361621 -788252835 876300238 238747972 821972881 -821992209 -993636511 35909975 913292523 771934099 -320761933 -820273944 918604004 -747585750 -393174078 -533630116 -452299450 -551864330 186139489 -443961903 -926505968 -695987722 -149778701 55791999 654193413 192749642 -736969407 -376226933 -851084969 -144996883 326996835 373988669 195911020 -558274586 -246263819 72315325 354802867 -85828597 -948469629 -846376886 198990003 -661152666 164386570 -181418843 -117584558 284716420 124939990 700657646 -281286522 -650502579 104450748 -737887660 -659310394 844585592 417091742 -705994415 -499730445 -395749859 405328929 648480987 -957416793 -240992562 243615784 399131410 278882824 549790555 144168759 612462797 -249956123 542970425 494459653 535749039 -45770177 100083083 -427942275 -450588032 -279063177 871826388 -766424132 217549888 -714620369 -998635524 -952640104 111804707 -873069422 -388451689 641444266 650483474 -334215929 -114189660 776087119 -688989850 -632668531 962437996 -187557305 451738050 -954487737 -131514342 -802753986 -548924919 629380322 -45635361 -320809119 268555141 -478274988 -216440093 -407054732 -470765252 -832750077 495039066 542105 839700399 486113380 124436629 6299700 -390415257 908245481 -237639363 -216003722 -846365349 -213075340 -149445534 584517783 942982057 77148068 -259936523 -349683483 60928871 266490638 683420145 -274368700 -856708283 439415988 -448079936 -946740271 993568133 565425211 -524835795 889815548 -64941572 -126685525 -172120746 982710974 413182033 -230820485 -338015690 -212138341 99394152 205488259 -678607367 -598967425 366560228 573651674 758130670 -808123898 733867298 615391528 -220288779 -467912935 -618590706 -695848427 -607769476 231295211 -546547363 -388059256 -405884358 784261855 382636811 -36357413 -175973762 693272925 -512107868 423635782 92678623 -905294452 -251580430 -745954530 580840107 -371612499 111161875 -310458014 -86636424 330415627 -79702377 -697533301 -63643621 -882490682 -484270095 587917378 891992917 512099966 283445599 -734122206 741643114 -95699217 917280896 617172156 -529710129 632534187 -948034222 -980034624 -925550426 819371055 169532981 173732031 984115330 688215213 998543090 947924114 -964752941 -145932788 -117632171 -412290806 -871485010 715163450 758620049 649654995 185998339 -68623908 -905594908 -373999178 -834190426 -792163308 681109923 253038225 548880175 982895035 138003646 83336161 80779798 -850133937 907484463 405008786 449354215 827823689 114402557 -107431195 -178466487 -230770389 974958098 -243625476 590960783 -580735279 493795466 589612711 139249801 286129270 -223262225 -786603017 57275249 341316418 11709009 75609547 34563050 589150345 -481347379 -103332299 -384037133 -876472733 975751316 -311960691 -707111537 -234072605 650517501 433801662 -174279790 460872843 177358885 356234523 -618226895 386917087 -908754823 59734781 747134036 644432185 457568639 -491829469 707269096 359640649 -421784041 946586309 223744446 698040163 -112192040 -501114041 843428520 -791673888 -619330636 658433209 866289042 966748533 615184433 929302559 -337237547 77689609 -492719581 -747670724 -330866936 10711683 -830874825 -857245068 -575727126 -614336804 723950937 -222697676 -722780957 -811110615 58712093 -138813545 544076291 -878118781 -811912006 -346997421 -43326481 605858430 -764542699 799424160 826406629 452962043 107240385 291901513 -193365692 494184738 -259702837 720264140 -704812121 438482759 860839614 981822076 -587442021 -846177523 -75122978 587208983 -322169343 242846866 -849749212 220734235 -403078358 -916446319 -789333564 858185604 -926677977 -159723303 480928340 -756487228 895947211 11369813 969194640 467617191 -200114442 327131785 33167759 -334886880 331480673 -572387865 281138086 -439362265 204027501 576261464 -579983646 281486167 891660476 -156588637 -254520931 -872354400 402988268 -778696712 445094897 -684437817 -126794721 334340016 -251776353 147278588 522279772 906488903 -866196853 -65975837 72137148 -654407840 718803504 -357134964 -281563706 253513923 -461808051 -852562189 -892798644 739860853 -216921447 220574709 -549465358 814833072 964742803 505837277 736625835 822840261 -999123221 -422298554 584599658 -50585351 890454913 -172623743 22865779 -278557897 997715783 607532228 186819688 -65594266 -559979814 -188751351 -986937937 269056556 -763546375 255015221 -236155538 -976767586 464396181 -362043458 -198949528 502788096 -694086557 372363116 -363111770 458674846 629912492 -326059161 -166581527 -736219627 103153311 -908204814 -620730652 -5170094 556518474 -573994677 549102637 -443337129 -824592427 -184537946 -827516380 -725280860 315659056 -45610119 -132089544 -503562797 -751929943 -299106289 403231264 -774797615 130067988 -755968260 -677239459 821292291 -822743820 -738755263 439976486 605798791 -221120341 -293584074 -2476523 -824262550 514880455 757100861 -90953349 433364045 -806136999 208370231 489918357 317422102 685252430 -932552378 46989775 203624898 19207141 -449540580 118331028 -834542304 784510921 -100009691 -11346796 106811193 -111859553 491260462 734176565 -678603703 496169718 314579506 605707184 211662796 711970779 -399516730 -78462793 775176755 -443098025 -636025944 -237556319 -115490866 -233974777 983219374 -205551076 788213537 136562534 -754901039 -457524577 -959619625 443416084 -368162790 647425326 -965695553 -275075969 -687271894 -721131984 953088803 381441442 849664710 388800613 213955300 -808830124 -38361642 -455690119 -446511409 -434077359 -772439139 -689299896 214403923 -15915454 -204478489 697419772 284591065 649687457 326932740 425293562 -932603934 -539806412 258928763 347184718 321408663 52088781 -693465791 -482688683 763227315 -308079514 -78263213 -603029329 -863100934 -307228438 -788877311 902944435 -590043520 -845523048 -201175457 725070555 336409348 351238882 -347246995 -757745218 -277804223 -276776215 -316919187 49835959