2 1000 516
-282910971 -239186128 -51279111 -268733297 694917613 -811199563 239415545 995663570 83599862 235860688 -848249953 622537369 540509482 104646397 51932387 -368020014 -24797117 629700219 713640323 -9803357 416952238 680547685 -96820427 -998236112 -84969378 731269452 -413643969 454079288 -545200875 -394328973 553203506 888725646 444127102 349015190 -998839180 -77620457 442889498 583003062 845079003 559201125 -827779607 549110722 925979406 -413417230 -95061754 765041767 987089826 94047809 -185848693 721995007 -829701943 -246306386 -217595176 45061040 -547485216 -755200100 -804108926 997034303 -998984310 -415646832 -462062365 160950177 329010654 -147848109 462363529 -166292404 -431530466 115169758 -155624106 -865758811 -323286914 169314276 447863475 -753953200 600784763 371519081 881266403 -368356959 106218817 778026820 453388105 -544013984 349704117 85033839 -442192248 -528377783 949464313 952194695 780147826 -606481516 894515662 -866661287 -327012077 -795740103 -195254795 -129943837 244023121 168580364 130523687 20352102 -727009664 966768364 514793952 660788053 -298515223 -61203170 422694610 62105311 124793882 506221596 -838708900 623692023 707650713 -705242911 666921875 63333240 210990065 448390689 635502794 312299334 404787221 754197615 -956980592 -371703940 452866650 -929482426 -222796931 -971221008 576241671 633765760 174398445 -226134086 -820143316 -866240518 -22062305 909288445 893933873 332672071 960234181 54811267 -337605836 -273627693 -865379785 694900242 800006447 719594265 4592460 -776882295 -966522636 -25127227 -598250147 -132451157 -421953163 132129285 -498489942 -659306328 -939694385 929602737 988131934 -800720491 386007352 873187308 811192309 639732630 974187071 -636718377 -7345318 -575282997 -815722668 603095913 930637025 693594320 -926462864 -330930748 459963835 207921479 81707149 -150871444 -287597136 -272718836 967557219 -144039100 -963314161 -950650315 288450020 -694907814 -854757231 -87705410 672481223 664617059 988914805 -986495303 808209465 -855609764 -762343178 -983743082 746507702 -470982982 198466916 213156640 -732029510 -720017895 -538703957 994701450 961762007 -964194362 828740165 919642700 -797642107 91208251 -576585217 177035221 389540104 -778954673 -307145229 236411122 -253546586 295186797 567968645 -239330083 728296940 406418002 -625501145 539420384 923274193 -549996288 -802762746 -15046226 87718274 -786341 -463986980 204952695 -580223826 -712540232 42764657 125111435 -404059000 77631566 -358825129 -857146017 789085602 -610741856 473239164 -406496702 -215555175 -246869290 332449048 670355179 169747317 -693425500 -209485641 538157807 848535262 -12782225 709597500 -24541598 -878117280 643130255 44682087 -544067200 -87179740 465444540 -28478797 -818418579 58576905 998479762 430317851 654202507 783727093 724509813 -699600857 721134383 566532330 -255541916 13034432 -298892053 -995752425 -855121162 881045303 938709068 536094680 335788084 170197553 -528499 149911439 -957483028 586002580 -993808020 -201483199 674057732 643087863 -513219297 -321453027 499219918 418713838 163045034 -245134517 -723758222 613402699 -363275242 -618426497 -280356210 960266001 -774290673 356929932 -957604242 -838797070 -653280410 940865272 19712726 738111808 -55905271 -282821661 -196687904 673402290 499490629 -510464366 730327909 176002905 86869127 -135977928 -878139742 -122593615 -956181086 565431413 455158639 -690649990 -305369815 693504264 -246109288 -479119127 515920925 -948618761 444225001 892310003 800642732 480465002 -108803321 870046832 -357993039 -9787467 541789760 344062264 178009166 192607711 -105135210 -532507430 667954872 59338316 -730887570 -287192959 988598232 178064025 283775612 78355189 -474756430 -688690336 205767495 680403631 17151968 998717627 -337803136 -532982278 462633784 -634440584 126173081 583660869 -278865171 -473140621 80348031 -729621049 136243535 675009610 -944816303 -299595759 -13316641 91202492 638472045 215922381 -808968925 -434390286 610233988 -956189794 -941506862 -667729692 -779221817 -775491919 883823570 317122931 741857948 -882610467 -568471352 -7406233 -441849965 817892475 -603222427 -712164071 -617038838 -153682229 -122726156 -975236363 -467775309 -76144238 -718885544 -72731903 -794023846 -870292663 679589064 10456443 -828662786 -420560603 -363466811 -712929787 983682755 252053936 -270569396 -865284158 -216415866 868834554 -302261330 -175986792 249064035 -670576747 -931398711 -925416391 418264112 463326067 606817043 -512470130 739918848 733491690 -526629297 -546825144 -931074439 -910228050 273127528 83882408 30336312 -651595661 730375030 185964398 -990170575 -381797445 -428857308 -708308329 906181029 -957331006 -429016719 814322006 619392044 -54679452 884914213 829615110 722854728 489567335 -130418179 -229209495 307506338 -939819267 -692406113 -370698453 -303480981 -770826742 861808018 -687195063 -840457888 -252651163 704526186 760752165 -459742593 -158917719 -732049984 334971082 -557356985 -992340500 990158756 366624496 -16956668 929881318 -468300923 -927258255 -597854447 896361196 146642770 263449460 -583715050 643067140 743403490 -615025003 380038383 -447087174 -762728796 324130744 -434413143 98001989 -378453145 174780231 557300955 -920320022 152969665 -141985304 -692542945 -784794295 137932582 -480360650 32684145 338611235 -468183006 567268125 864252676 633095959 -395642970 -330518730 109852996 532961164 -859390743 -839099460 -801127058 162643628 610237900 726938468 -759866884 -565127804 560302640 266686758 721157908 -167480462 625424484 147479634 239746753 -94066649 192335965 639975360 386317500 178387504 -142620904 732913577 882086927 820971224 -473682876 482851427 -669903523 332229894 236924376 -114447349 100919613 -337097388 -701153428 -443312403 364241273 -164176882 -264537880 -943206884 35479205 -812365405 91593303 445845814 319336462 -869744613 914403656 633519446 470545852 -845894518 56814106 -501047670 -474997610 508985515 314793100 -405339367 414471695 -532970146 172859852 -227542016 117549065 457412016 -117437338 -338751771 902035081 -243519269 -448137013 924466460 -884716200 835752573 518894463 905909142 -183604189 915084612 791105581 753645043 456994255 -81203634 -147520725 396167085 749310217 278628006 577295002 853635663 -17060050 -391287684 -276848770 902105134 732524663 167997084 737650354 106296283 697895117 125887202 8609989 -556080109 762594720 -744683906 311871327 75407290 -793466863 870047886 112234121 314449929 -628548242 413368683 -770592241 283105543 -13257186 627064402 -971583123 -733849478 -701937889 -406364650 -965026074 -124349787 -957986715 730917255 -624957390 463603123 -460560663 -377014370 -776228568 -178070639 642871324 777785882 -105216828 745459915 -547771947 -876856282 94863437 852077475 672569051 -156403315 475775054 -412603469 100349004 -519332177 712900458 -69050508 720852977 -750781653 819022629 -9079040 307727416 638845441 8582023 -793656553 -129185182 -158791274 -328039416 -759286014 -785425916 872390296 872244881 -123263526 -341575183 -926731066 -306114164 726006302 815371656 -806542282 -162361037 -935698765 112046371 -747801508 -799896888 -4272143 890227835 220599398 -48230986 293448385 734108906 -781088482 164592210 210490809 704971959 985961779 -627570205 788805450 -782592153 -630802349 -572859777 -305907523 -354265830 345221792 -140606166 -267363104 -281043481 696974962 -812225893 517974873 751919409 37802256 70982103 -47002077 -817345362 -384677079 551315166 736702637 113289493 -252540374 -722226553 356445792 -466150098 343499766 234233738 471969900 -180048278 977337682 -590736997 -955102441 683798035 -337693131 821988414 -972386457 637078488 -17427704 -72402112 760853466 974789970 457568950 465791775 270005427 857550558 -683028008 -698386919 639710406 -226396305 112688000 -731368800 542476079 -994572972 441000375 605466056 -615031276 617105686 -602072646 661557489 -254837364 130614584 302333776 -37763422 -294429698 -158497706 312853566 41170524 921795183 333038270 809961167 465231665 829967013 -347034075 -173434839 -434513781 437116135 417425162 -992660692 -189272369 -357527493 652660030 -177446448 747246150 491406013 -925935021 -362923977 -466818822 148054959 342418392 -185856841 -83266402 -575940995 609544480 324214735 -348322846 -97863182 300212352 723704258 -425816795 939792648 329554439 -427081168 894178509 504871980 262931001 -119458797 -991543737 -592072396 -27899942 -121655648 295487621 193789917 -93889521 -35316537 106520980 397968070 -114846439 -785330583 678890066 -961590999 464443267 288031746 644234711 -914326838 -752292057 491233239 245758479 -173637347 3384453 864972880 -841546454 -338754327 -453105965 847541232 -161071586 263597742 -159075465 726564894 251557895 402751658 144097052 -188614214 -692329454 -625765314 153198566 -518071941 823585959 -842987336 -501502473 647979170 948014620 -329987048 584210496 650400823 -286012358 -289764075 287902227 -4224129 -304307320 873465048 -907354573 400267439 -483083961 -423845645 867753182 -359657717 -560320371 -956739339 129728492 -119587513 -869811413 932137698 905599069 -147350215 342507434 -530741553 -2720323 758174478 106140070 -91409824 -413000475 -74305230 -531142119 -156147952 129522732 -618651218 -414945233 772282519 813424542 -903712297 -122361220 -350800834 -208385085 658988702 -18243868 383999912 637289967 -209476905 18807648 85652304 108380581 395326162 79448422 -985682916 139393957 -699897533 -528202859 -628184546 -260517818 136860076 -626325703 -771722482 462075188 820234925 -432847439 147227612 241221091 557517979 573936731 115702354 736728307 160544866 619803378 281535087 144021833 203535616 384367176 -958449015 -942014026 -480350993 -964069464 -750257264 719622276 -92016907 -331865777 47067440 -555523908 -23125903 931969044 91555780 74654484 -118139049 -343790213 -904315221 977295881 -410128372 970520074 -480941788 204030840 228829556 -99248049 -777006135 -971797604 822305586 170366008 -499697605 -335922161 -73656849 705032728 -438790813 -67079401 -127248881 -206789765 -192906680 -188620566 884053138 473207522 -323389850 -816678598 -772458294 922470875 -918817449 855201555 -561680086 613729865 934255529 240836709 -160394825 489753846 -303187370 357215701 -96357832 -687828560 182877821 -74617410 509060257 -749481418 -856364726 384156737 950887319 -230030873 407362274 -618461380 -590959806 312601634 -526011650 608075322 72531235 -501461070 335675062 556517511 -975613966 -86540247 786331172 211693040 486098552 -65233451
733703883 -451537829 552133221 -240366635 -77152114 -472874381 280422199 860423486 -236766373 -481783347 -770696898 -487250287 -580811651 184261890 -332795525 -826559493 -399111538 -955284206 -510922238 106076570 -974723407 869262280 790127401 496723386 306862802 688871071 283029756 -761617904 57681758 -132197924 -635974991 803179854 -887650597 815602516 -830718997 484203322 -595612596 -91491845 -352852721 78881188 -515830277 227304329 -398942539 -153385028 891655119 507456466 154807354 969695126 -27077706 940012857 -509498081 514664174 -300713524 784045354 440521828 -801685685 425983014 729976662 189249625 -611380548 62278798 -11519319 331007700 402201385 994060607 -750750202 637566040 -178898176 6813847 591170225 -309207243 -60765755 -976790957 -325511327 83090562 775502691 366665466 -748223751 385028349 -965511303 246824364 -75573463 -481690969 -907002229 171557612 324178768 912150911 823149091 -8513750 888598261 -127349028 -700090353 -187556210 922963795 901123728 726356350 -342455341 295556737 -320861448 -619502769 340863725 -35249061 -813403738 -319616672 314298164 -200344375 -759708266 -44681416 450238878 368859689 -966983192 -870195723 188040536 -730728091 340207881 -576656666 572225164 -851869402 625878406 -278649317 -172307798 879931291 423916916 -98726118 -785272396 -770438684 329822580 -19949919 -987133483 -534336805 -687665723 -761816741 394401703 -845326465 478699187 -158425602 -327378891 -333597362 407487187 143186338 -194534501 619778437 791927916 -995713997 -699605428 -47294734 518158258 -590866707 270241165 904003820 -606977715 103354603 923339325 -193946330 20784742 351262457 -104507508 -147187414 -81458981 -542183101 -961730559 628437750 623390116 -306871889 219190830 44341997 180905997 -302322969 337551613 413564709 363181541 -477080253 -876273150 272619444 -393823132 -37861642 -380538476 -160863312 535089034 -690449801 979918251 339408902 268561085 -92145734 -2557989 -845709855 -686875939 -490934384 -71041587 -78362010 -619297591 300942905 351509788 -302878970 966090893 175112485 627589536 915350473 -663883609 -236097320 730564840 997814040 -706553846 30209129 431552302 344343441 708660267 -472444252 -440613386 984798115 33444281 263408404 -213461313 155487147 -355840042 -309287038 533309992 855830433 -666687414 -237604054 701617345 796799689 326352418 -536529949 415082491 176348548 2513549 -47896709 -759237696 -927340323 -420820830 935964064 291454860 937524412 -307698913 -850322594 -374164380 442808062 991643000 485205716 913920284 -427635956 -204090129 871132563 334118518 489566825 -798120496 29264230 -232787161 157803951 61335103 125815669 -832854781 -581698220 666990660 -821042120 -829375172 874732791 -175142348 -537447289 861066457 -260912423 -382769565 -606332633 -970488414 467138345 724477356 -780917624 574883529 -646230958 -981959123 507376654 -142832504 -935860381 523718764 415884714 -512277561 -312033901 992606195 -577281427 646436833 310664871 218359050 -933083044 -151551054 508635173 -129838204 -266426769 449949828 106743332 396613967 -377652471 -567042824 414861410 494600379 982459347 -727567398 717035636 -67115461 992924038 233925802 662348142 -977071863 478236835 -275932421 -492085573 -12394254 -544816191 -91241227 -321342711 417250378 43156998 -553283645 603989938 382935774 -110024507 -968940191 -40989940 -366684280 313574471 -169994763 -273805026 -841127533 -136157016 -712769015 -704430179 47212740 -521540043 -487684252 -197022184 -897851753 -155406071 843262142 -990361098 -219620954 -919703903 -358235853 664211844 -57805010 364489281 -245423794 -270525849 588952536 -720548104 -451280492 -417720425 324335274 -723195480 -670823674 -72856299 45835132 935735785 -11223091 621393073 -157275991 891709817 690163269 -728175106 -934561336 150030272 -720689897 480964804 325967718 727002679 946673961 47974166 57277283 -994731161 272803075 -214722784 933362517 172062006 -273106853 -91918203 -971044971 -758081732 -289663215 -497987408 -176371481 839086106 430159929 -181466268 152903843 973925374 -412263038 466699574 -741309952 -328207300 -860219102 -304238842 312491999 -839562176 375139401 -557512716 -748624213 -137388992 -747632512 130131844 -315584972 756136307 -762709666 -690272794 6815823 843008722 -713083029 804755827 -457522878 -1777881 -743515372 -335752512 -790270755 531081874 710753243 609335940 305494122 781517248 319734673 527241277 -830907598 -970377299 -174159610 789060951 483025672 -484898380 -301871979 -84196220 984227106 -321881473 -218920687 -438728198 841624646 128588567 256514345 408089216 -701694687 876159441 702071289 337494958 -391572034 530333558 -436409462 -282253262 582451086 -426802620 892416402 -476970756 -352030811 -809519770 611727104 408773788 -189995135 -793324287 -253920297 -473746370 771078818 -495056488 -106973303 -575161969 -349040004 -17623593 637860122 -94131308 911726732 -460047590 -335736821 408422188 805272895 -454124602 -430872319 -538245030 -451453166 -700719800 -465277117 -395952733 562296247 389704731 646353850 379232221 111584731 265033954 -542930603 580467678 -119576828 509060334 -948750069 272785532 -581543888 922661761 -37708374 -993670603 330023418 -881772789 -97505189 -815784467 -746456539 -761799382 934573572 -695425835 -727817656 -91159758 -857144929 680745675 -595002230 294663787 970679985 -954439838 -343596762 -107803053 -305655787 344780179 -344250919 171970963 562188518 -194583157 -360444435 -86048283 -712343311 -628350199 746319890 -818227812 917612255 683403981 -345675148 -733292836 774069773 770993213 -57549401 621238834 -113413923 809019545 553804579 381521298 -537868759 293070308 -992543100 176302982 -395838848 -412260537 -298126512 -608628158 96265224 -867984581 -328561496 199937093 -611914370 340968172 -578995355 -985051170 -742285703 -150216786 -387140328 48404248 -510160848 96042963 355126443 -332787155 268478639 400713415 -717698746 765270432 171911336 -137181284 150147417 -677700288 715874064 134920819 -958232265 385268530 231018498 -499500195 -810517389 -722493409 -136958081 -240494659 776963824 109696290 988997360 -2003204 448135841 576782448 -763451576 -792900225 -248956947 -6209068 -384761741 768845802 480366221 881017421 427912259 -859299787 766533099 -654790552 904146275 249046994 -912882929 57829435 806707628 391713094 284155736 891909995 -923322863 371487495 -96674444 -322039651 -629538837 586609611 642642594 -593858190 -77346029 -616527768 171642609 -916651101 855084854 531250868 -528922903 -40057455 787382489 511453968 788027985 -66378906 849686745 -242026563 -677385983 -616399341 94211234 -804682215 768949792 -457016384 -975094039 -685656498 -996316779 689163861 979416140 -994203927 665784761 249191132 589846907 417790536 233913000 33703757 912323970 338905690 -276525530 -363989652 -897094747 -170177821 935090255 -851859224 -226549432 -226380208 -450709134 -727891432 962206593 382667327 -359021733 -305506042 -553006571 193019444 706493372 719462747 506602071 542942451 170525183 629739638 -282346857 829727182 476400079 -34194084 -307064646 614996487 -811341245 601589019 461953358 -444300245 855528269 -609913779 464066767 525816351 -591157687 570865591 68171567 -761455427 457421711 740372227 797034151 310918064 973978576 -866860347 859753052 789348654 549659614 -221279158 562588945 -266028441 294428352 370179400 755670705 43236946 -86755340 218736285 -537428959 -553235851 -208705539 524682364 -880360430 -111143449 -693729437 -227794194 -256658879 -733611542 -410014100 -881192758 945777062 155412829 905912750 688849591 904962756 -970277139 -344117052 861695752 463558604 690323096 914354590 -312602440 63666947 179096156 850138057 -947740255 138300912 193924988 -26424939 964178518 -601642774 -454255346 -764855979 504921370 -291355929 520025543 -221738803 325163016 176095479 -787479269 -501663997 639658772 -525462666 -57628552 331524423 695465230 -398779415 515648113 -662169070 -389885271 661452168 -985393891 -361109527 -883555218 751445025 -324779402 -997538747 81777801 -99001589 199787058 207729026 807173601 -491925537 -114977714 -789454378 750013765 -960235994 -150045196 8106310 351783758 -902803047 -320919670 -220256841 313140512 -19518969 852863536 -852719659 -734848837 859009211 -249025697 635973727 -495703785 -796237555 934728088 581572891 339342285 688610795 -34806321 29991304 643129194 786357924 -872538473 -271546703 473003805 880380146 237342696 -908732386 -172404094 -998692065 867346758 975880225 552119049 -752788009 377722810 -108518091 -477869062 538469913 337219853 -671248465 -949986443 -344790072 -864199798 186409648 -232067477 -692509561 762233433 -829622037 -545510475 444992600 68084779 -335506099 -996894048 -718596272 -874177346 -415361336 -224173783 127680214 -965368592 -299219414 -425612806 -652266706 -179245766 38147437 732235079 -456636183 -139368635 -363831416 -627867794 98714752 -436998805 231801663 -760709812 839533999 -804751576 -461883894 -710428252 614822296 -535837201 -319517632 643311309 -661382493 -254171983 -406001458 589470316 -550946341 294936885 -702789894 -887396097 -491922748 238989527 51325972 579115442 394152347 -885698182 -259635711 838426546 -603076714 -401853247 -818123776 -745611492 -736823657 -858565579 614875421 -974140541 298657729 956141469 -113020985 -378867327 696641643 720710862 291104118 279253540 380385657 -77342218 353286734 192699702 82208781 452832142 17564525 895384439 -949259689 -823726510 -837782737 965381697 699512571 352365468 -291486758 935035260 -810649326 192461941 952538191 -752999027 115412023 247330455 456895387 829373885 -595884182 -746217088 -762246675 455808495 435703485 -443344966 891448673 323521592 246099714 51250394 -148628223 -467557805 -41672002 -997247962 651693391 -43928297 -2791384 -184545888 -536744703 179193936 710927181 875403859 -901789600 984382220 437306549 -609670669 -374471508 564649989 -400043536 37507825 -881266411 -931072136 267146252 -67983207 522219089 -734858701 -178138684 129984695 -66707773 703104604 590518600 -725525795 326606391 -722309748 312570055 9488105 451220473 -175226013 -240365877 501693853 -77407601 -341564146 -499564899 -887349508 -421096687 -793140856 -334186223 -948036461 -736546884 -487637180 211131330 297576278 908377519 41048468 387436971 916560039 -379894874 -539025649 -19694381 133285308 706961341 158815727 -541204727 -146950196 -691383783 512733704 144397286 513981276 -729377589 93889757 785195836 17004374 474535979 -329424020 -453035802 -509271404 -395188598 -612273831 725648377 -576712232 131709537 -68016591