2 1000 529
-998579452 907515810 -780990279 -662113175 -565225463 -905908411 170299621 -128764677 142116887 179127622 -554730289 588572211 522424727 331413644 -829809492 -464516996 885683522 -635646041 934561336 -210936028 307124699 297433732 -930216078 -59482495 -979367394 -561752253 523563808 -492698003 -246183147 -139269421 -509008731 -612227670 -333720867 -666500255 33974012 -978822088 -956161742 192197490 984839124 667292403 434492303 357907522 -866057074 379632045 836778450 -164771354 944790085 954211208 706163828 369461678 179173490 903655722 459209632 -480974222 -999618559 -178035291 581429717 -40600210 -793684749 -988765253 -113014388 273151938 -844683078 551451565 -372126442 400538012 197997259 -552310788 573370156 654172412 -258377600 -48097337 761788491 976378699 -46706901 662858145 -972303949 918346373 -748519448 -749289054 60258638 835111708 -111955614 -150092714 -88510666 -136096345 -621685686 723270782 760796924 -610613267 -221766165 -589429574 887155366 -945187825 -53014771 -521262317 738413186 -569637372 -929092238 705917932 614928128 185301793 488393727 265975306 497844747 292862512 104380861 458588984 752760219 414270166 716483974 -830547168 44408117 -127688308 -245915058 751336359 965470342 5305967 176912384 668424683 -954881856 13408882 538912629 -854845154 -228112962 190614376 544387199 -634536878 416589588 -116868574 447455358 668927785 -38808315 -713012459 497027018 -639998641 -990643870 -816624910 -204349111 -749062669 554321601 -29506357 373036078 498242322 886562240 -815618856 -960413637 -262094469 514770665 120300195 -84637501 160876466 396209570 -323533648 986822851 -667115112 48869316 -603286280 -672362902 273816126 -433890038 512368771 110679398 -441166839 135885505 -960605825 -738843305 611449797 706325720 -285883561 -856332292 -411051329 -786519629 668250031 -834275104 -547435571 67185007 897952276 124548933 270736244 852077886 111904200 346843504 -988782508 -905519397 749834561 707071516 803533966 410155366 729142385 -955152487 -201325411 -462116634 -254414726 -339627033 -639260524 -164040016 -798117430 702886573 -560803143 -276996594 906739833 -324736726 -782407963 954957887 465930570 997555365 -727892684 109729145 146060526 -90998229 -6445753 712826095 -862767587 -4302406 512970149 60049703 -487725996 933584161 -183508036 -793869928 440193117 330844933 -136500419 366056007 -275727968 873536491 -494422014 168249583 -357425570 69918247 667342580 767484836 607510300 -961237432 -807412794 45870121 306715523 538593002 272857848 289872828 -627720221 901090787 598713151 710920884 -630623490 -39184931 283313258 41048036 215154497 -362284189 -121009895 562857373 484991214 -181061633 -165983527 -590708563 -534484415 -852835158 -834304506 861608785 -731442111 -651932094 479399288 -518255849 -977470582 -690187354 -409861360 616472659 70706748 798343683 -570970459 412949179 -830052120 -100229899 -909592608 395461476 -218313416 133450086 -241772595 -462284894 736097662 837702885 -192566840 -823046469 -863509610 -67932363 -682639025 -578467694 -368586834 140623061 -880739578 563235250 -800683001 -48963646 -435042915 659061880 -696882017 -809510105 655640393 435550790 -416090056 924756287 502974375 332122343 664118104 813861454 81745340 671870084 486541214 922789157 702521624 376379510 375072627 -43697303 -493207990 996930314 -895486070 31853856 591711715 -832658204 154332654 -421676559 -223176024 -99720488 312810671 -19454167 315260054 160114562 -841142950 -592307386 607524017 144482432 262354739 158875404 -191318004 597673675 914780510 -23083320 831018542 -600076356 879518628 -963787705 562391417 -74730669 645671218 -373934016 -541852652 478309100 857485340 -10807484 24713766 -442411917 -352011724 -312156233 -701542961 829747719 -300726185 -698212845 138549448 -691430269 84934339 -232192758 899359506 312999883 668775049 -660971665 -763765558 -154515941 -137190752 -923731007 268195853 505320249 -203404484 -587780114 25620862 -815984602 714717831 -716170666 251739922 -167635953 754514700 -186753314 195098742 -82210670 439513451 -550048316 547449694 -138019297 -392279336 800303998 347627401 226881987 -204835542 979761984 -540292630 109256908 -403862499 651220315 323317847 691111970 874220782 276834817 993910815 -292595365 724791333 76959644 -173557492 808097752 -23606419 -706510416 -823432840 -581131082 -326711918 845852387 -974217930 224300627 791026278 715816885 -536416903 412258806 -716127425 -78914967 755571779 -519915987 343878220 594746559 852166651 -490479086 739268262 -72486424 884207371 -369605879 480313269 -603492624 -105811712 321171682 -465293940 693026818 -378309068 258316990 -446635290 307047496 -551174907 482721905 733790575 -544565517 -399125254 478116078 508591774 9688199 -741783284 -423066333 -932812386 414880331 -434998030 474651628 448950999 -454509990 -883646940 -5821203 -17361053 140287592 14805778 -463496682 -692398118 -804767935 -385580054 -438118705 -334774241 158305722 -957995057 995468880 271331115 -826364720 619933718 -271736284 950584007 -510902507 -918370427 736798246 829987769 -21645053 865376455 -490578640 974507094 26269302 -535431041 573878741 -428544431 -218627872 725543234 822351800 97932206 841655012 903199628 727373085 369060478 -746269325 33054037 810706901 -500425498 -459552952 -8908253 770852574 234566846 621466309 842260781 -125668856 366443745 721749603 481216451 241937933 506801521 629828191 277878756 -406645598 -969466090 -667459359 950821113 307232206 750808803 -657494182 -753918395 188142200 -84972574 -906273940 -486208205 -588970356 -903890165 -568745546 247689207 379591160 -735306332 -888286448 260924990 -822568949 275456746 -606496925 -372755534 740693484 -907832758 -435671532 404051955 322940309 -485971478 -11389996 885022699 13039697 -997994650 -182562632 -686848061 -655310096 -41592347 675492922 333856976 -747993261 -963984321 600011986 -874575034 -323249250 180961609 -333507918 282213026 917931334 63701596 -564162648 547233102 -455130445 197787787 905321882 837134034 140309867 12145624 232553566 204701289 179341974 -598802340 -305735270 779371183 361064268 -247440262 -100453026 581028613 -232385872 144972289 -379799061 -274041456 -563510269 694768775 -184289722 -209575836 -675475681 -70487390 -230877664 -969340657 394586037 -482412545 840420226 -703404343 -676127943 57608008 794098728 600447090 858758152 751310587 -969509050 -593698176 -393570004 -959197676 -320777168 430096344 -473744917 -403813262 -351989799 -541235694 -365273660 -18287095 -777110090 522478731 -680036210 652525457 -690847289 -887442492 -863421082 951308776 -419387946 427991807 -492186874 181797561 169991296 -404357873 -174564453 -449041112 714106710 238787527 804177686 -837995498 776991034 -767751407 673652329 55691383 -653904738 -23284453 833105008 919268827 415441411 465661084 -680546311 358121010 158993300 931826905 71546085 5734600 -345060484 769147723 -71051955 -323837448 480442538 -862173770 -671477750 844336964 297239645 938478268 378546063 -196551551 -973261227 859846313 -894951162 -582783092 421502501 -889626968 793829123 207610295 631154422 -494583413 720520536 -55751354 256967984 87933283 327084158 -740781494 663045074 320633879 306006759 324579563 -501281944 151400188 743633922 -518328535 -705823308 -291381525 -540967645 -574717164 937590530 -153143679 526269651 -483404076 -42554449 -623520323 166021793 910772549 -954150962 250269113 -3396026 -543236855 -665971494 803034509 -374887247 19421320 409220268 -55210846 763357274 396446896 -37347939 -369779351 69787467 -988076346 889725322 -179958691 -884530907 222880698 567787114 546713082 557973593 -746098089 471854651 613516386 -160143875 -292770562 -984820872 214959662 -603683310 -537586541 -912022360 539537695 328050676 -27384390 -907976898 -570880674 815729221 290038276 401358490 233619449 -308621578 211205953 -802770441 -563856080 671521490 -209618626 188232015 993266584 -910482711 461854584 -448010961 210163854 230016280 -22195102 -406322893 217172266 756793756 709389642 -839477651 50276483 367605347 798280559 -327419666 -238777341 -532283265 530660747 -483098837 -453821345 -162663391 171524536 9050807 283609896 301989745 -162007913 197116409 -47102657 872309748 174659913 321819240 -151551456 434355439 446236907 398752179 -900139603 322278659 -672054409 -627976069 -295587598 647643851 353135719 354826350 -806516963 684998711 -117714665 116019 -786912221 -519818832 -809027193 -112717496 -455601848 -22276360 -469152845 -273059341 179096876 465149260 -634377557 671339137 237898086 100367584 -748104402 -47638269 -108265810 442323493 95884241 -659901520 -486488569 528729588 -484343053 -290879163 -661865507 -943929733 554681531 -884129322 408217686 308651674 114669333 -22494262 49791998 350877604 767834677 -33931828 204133307 -674293388 -545148551 51469813 697306558 798248841 -238459036 -935456709 426232661 297708503 16362702 -938850459 557972744 -435936675 68731893 -963006053 -757342648 983265683 151580623 417535395 5385170 -276562477 -300540893 420082496 -655179988 40623870 -182693736 462713481 351064014 -286736239 331675024 231048675 -39260111 -86477854 -913513285 -276698888 905771825 458881046 43883116 885794451 -964854026 -35437193 -350965344 -522688293 -636837962 440666871 801006828 529652243 628355636 479987345 513009295 854732430 323558146 522681546 -920125201 -174403299 -630101198 682761385 -593677256 754404584 -215216389 679763496 114699917 -682308926 992653658 139877297 -287805219 -305809908 177887665 -375075406 -768279295 -26127112 -311780733 482599890 -932409822 667195418 397368751 591794611 279828400 -455809957 582854441 411418611 -587359229 -179864623 385437660 -79537623 -799443469 684038054 233896563 -401727072 97955611 107408800 931291228 -855724775 640046421 804253662 946461629 165073128 -836014714 -724706248 688275175 146274323 -664444650 -454297074 98953111 -790477709 42554678 -93696147 -981515601 507488526 -715725399 -837441017 -293203451 988934833 -443369869 -602656662 -635378596 677586172 575999937 412557128 -344134371 -412613836 -358235669 -9519616 89056596 154423578 972556923 -152512571 75157212 -512014755 956999655 -203970321 530389868 -873020418 218403926 -178462406 -284421338 739219019 79555536 282422230 270733485 774148466 -751307402 -136423371 106635488 117610262 628944430 -46754650 -266301647 -534911674 -619041678 68906587 837102259 243115959 -999450435 -745235278 404523503 -876641980 -265463299 541235963 -958972266 -271281804 -258238207 383005440 338175273
513905226 858724744 -748444930 759770682 677003994 802638331 -668799364 -324472196 -997378000 -466892106 95340288 858835902 -577819082 -797932444 644584121 101570010 -99691206 -507119315 289374250 -660812053 -80515762 -911328173 -55485580 178553647 -838681529 -925393854 -997111638 118832267 -465568997 -747768146 182873540 893406634 857037091 130282578 -192756256 -592186216 -899377302 224052944 682794252 781218790 616977035 220061731 374792173 -775690112 804390298 385350786 138552368 -147114875 -491882065 -564433115 -909196909 -886853976 -491454881 -438038086 -905677173 -463969433 738185370 347805013 -421951293 100742077 532219703 756354857 -808563765 580217242 347040710 528719845 -984915712 -723337251 -173223551 550680398 26291172 -288986325 -243347100 -631429110 845537575 -824313645 954980175 147485122 616727610 -371124891 -53497963 729618150 -288574017 236446101 573878315 -891307709 -656478406 -91079848 168975717 599967135 607633374 -565404245 682290155 -201693480 398684239 376568796 -539379682 -779549832 84211621 -532523944 883320516 3067513 886046388 890894922 593649026 -451255123 116320427 958743785 102400250 449329354 174762455 -905067933 -732137300 145655178 -384710545 565972952 476161134 -771703948 853618558 171070005 -840407061 361220710 411985296 -819131191 603624130 -93272685 -623486176 436921056 613950899 975037490 -805318478 -360091301 955809215 5980414 -668171655 -914581945 -689058155 -742384902 530530883 -545593950 858598551 -459556349 -966018955 -300037850 948283828 988295511 229485081 -352887172 -109211450 -80641483 36091330 425878284 384886468 -125771961 802139575 -977214523 745580865 -649986509 -895522 146771170 -961918214 494461288 -387912597 707098853 384705917 933027095 -400631224 418896304 -684233180 312715178 -985678096 -762453750 -429289147 -583772175 184007500 473306498 508721003 953901856 -48174247 -622086185 -721412080 981797639 341681876 206015759 813846392 -123505671 451165287 -45740218 329436486 202587398 -160727921 630911243 393536407 352972 -742250978 -702508498 163030420 -958924068 583358219 579876133 -127107369 707318461 372055590 696044361 858838607 -991002160 -882176198 155327700 673962233 -241848271 730742488 -558366405 763329042 476361449 -321372829 633878202 337838458 -45102978 -366074757 -429621006 -847843381 419544119 171071928 -961987741 -224590363 769069037 632268603 835502220 768295419 762576378 -402517728 701285015 -79117015 -667136678 889627895 412047559 980783545 -72953830 244353648 556472852 -816672467 151120372 -272182017 -680553320 346303880 52747218 -334401227 608263249 -835874411 -646066645 -401430559 398858866 317173287 407101174 338359447 854416841 569355253 -282774637 178057899 -628830267 -379605287 450467256 -439044926 -269819492 -977127308 -481760767 -201407343 -271624846 690731651 -840309633 331805566 357464578 -854051793 -367843964 -792753648 -354824079 -744579424 290748258 411373911 874112981 -982411890 331951770 -142906175 240702511 809663362 92138908 -560108662 -848558702 -79671712 -113405041 -305819857 -42510927 772502804 -136588169 823478250 615910513 431025509 876951222 -18460758 -999914841 -871000332 -658654686 288085702 721094917 731262070 -48705875 -777245005 -90012748 -874094524 -558308988 454807963 -931846087 -233856414 -917204496 237781414 -743136238 126822981 932058521 -945627893 -572415554 690625403 760613719 -868522885 -453462709 -733089818 471297781 504154375 193531122 944746678 768589683 590146991 -130835553 525238193 -504595908 -919320506 813595121 78799167 276434359 865100599 215995140 -102904748 -783070856 -568890487 495374372 943373090 -638937451 162715863 -945375209 -855139228 -798526502 812159182 210765046 503966191 480249616 853480663 196578457 -172374992 969815174 -412975092 101387897 40063473 -580022015 -635114235 974785710 -728700116 -406570832 -855719084 -687173816 -677523398 88370970 -973192737 235238593 250824356 197031466 462564269 723913037 14051052 470222382 570528843 -919581772 237153933 -999634444 209468806 785280855 -947919569 -893071117 959955820 -184190608 211102147 393042070 -229448454 -268993140 -644945802 -859700026 650090614 -809284243 -43308281 349208689 31645597 -148167611 920090702 850598815 -55218562 -368962552 -183770360 -791491477 386952226 812287753 486857756 -369809515 -676392647 -766929598 -549195613 -225775163 -322547783 -380716860 970111689 828764171 -776497878 -283538891 660861311 318459572 705741470 -498838405 986052706 -136495544 883890454 -187888976 156116934 354837055 437093410 -202389188 -779224830 -379432260 836906733 -289190385 120256143 -86978644 634602815 -225409667 474724839 655882158 618722762 -784062579 443223609 550700003 -368295981 240711551 -739995232 451974880 134578797 87662274 -667371819 -276597561 -742603814 371760076 937649249 -300913975 -326749166 -392049554 -967672712 954441193 116390135 -729996175 392215153 836288905 391079265 -425005341 -296697667 -123904415 -257861669 922661838 39446109 -787058564 993813749 -629296377 146570441 -76616571 -961290585 883470114 -732037765 326743665 400248184 -680503946 -33896412 -333387318 -671081150 -609655526 -957292705 912044157 -521632565 243133452 -657633515 248713648 166385038 -704894128 -945118185 682797267 -939936074 875328129 -777894108 -662098573 -337870927 -679904099 -915727799 621034055 -541756319 -9314648 -50872207 -995314521 -111536804 -352862078 30015619 170885931 -843671814 -702303513 -469340159 770356198 407035640 -732503478 -573039980 622639851 366802777 -912328594 -847731975 -18315944 -825062875 -64301716 -802248353 -453491256 752933495 385022022 221796679 -836382854 393636980 406336118 4680167 -374901134 731481878 -591089334 -513969944 -564441549 -829169266 117206382 418159638 212857371 -738121788 866888468 149840732 738253261 -227416546 934528802 -83091222 -364171534 543949301 405336839 -795260932 -182315056 554132306 -206797070 475337280 829029985 63451754 -101924014 -428968332 333837411 -259231517 -101973361 -979623547 133718101 -49749623 659970001 961676667 -186641042 388853010 -373157173 -502885132 30019099 -466113789 253427441 -364787733 142003485 -60225782 -812783048 -649510831 654685133 -905879119 -119067205 954764325 20461546 -29418696 536990976 215970318 69266365 -495324059 -454823479 642411250 510810082 403458978 -393976068 106438145 795903980 788854557 605377737 866047429 751747295 -993308451 157499416 -483468449 242747476 353171267 953300435 -206561108 -919746813 241316559 -387129644 -16732559 863495282 -937881813 593341463 -795231976 -26620959 -462400045 43042375 -242335531 130015309 -776632188 947289442 -712626664 462371430 828589206 -34485724 989662633 603386707 -472229662 -944336306 -552357658 964957548 361504101 13994684 922609549 -533904728 372205021 -308679247 217819657 -710369447 958117179 746182681 -967444698 860808395 -214043136 -933745034 -871276947 -269610944 872723571 323679009 812884202 -542293014 -306713524 -956322588 -121023047 28607309 913238903 -762847825 814084467 -602476224 123799386 -113906327 -759713279 376321942 139182059 -584440484 -85702020 827284844 -494859072 286494428 -649427442 -930762612 -158666438 -257978711 17133190 -874271667 -832056900 -116812265 213774964 409947311 165148076 731146880 -898922755 118471380 -683796574 927990533 229812597 -494897662 304700900 -1654446 -222564966 -511962669 518493581 80944692 931540789 -747283630 153128214 530808681 -366917723 -917357166 -95335774 -956185096 -636469919 -235532181 332785151 -561285737 -735916776 -737616257 432062869 713818980 -868028863 553065745 114893745 742908210 -631699460 287923575 -229947342 -787361124 98430828 -286492277 784682447 717177713 371998368 -135195468 -865478296 -794288647 813238989 626051832 -790924559 669912869 -407105770 -174469579 93058056 -378668419 633741472 357700452 -953679975 316166070 979483921 -13724329 703069970 -805370561 783937713 -241382121 627462784 656509471 708336081 747471656 -840805739 -237169848 32840533 -975099553 -147208149 716826913 -862128980 -903033434 -906615888 -598794330 -118202101 934883693 177129668 -49809158 150270697 -278371347 -994473431 742850540 -212108626 -495230203 -792769156 249581651 -131360810 475755492 172238609 -670118869 541841852 -789931356 565043299 -973673397 -939290856 -560975301 659233916 162995165 -330724130 302207779 -458210635 994280206 -404194618 8364026 494628375 269081360 825110546 744122944 -362112923 562693567 -808050925 177109535 -267820212 -40454010 563579210 637776758 801372365 -443258540 -340925071 -270394368 332859171 116119110 113047859 -420191723 -434093965 -810244662 -162037106 -537924110 691674788 -626990777 779952021 -319371693 607457771 69806542 -12575639 216755917 -702089381 233762613 -105639841 757878567 -902935617 489825501 -241043557 267762598 -652390168 970595402 365856146 -332239542 691817615 651223074 -898509478 362460614 413468891 212179758 246724435 171755499 641677919 -290937329 242105355 -258193452 -982365253 570805315 -16400375 -169037503 -938372119 -286892931 503183638 -257218104 -780061754 -546092860 -355427821 75523792 796889579 337475003 -922202699 -481291711 -426794196 -774094088 950337388 -450699996 858988503 561260171 175253547 957701349 293992031 -888609339 -313339831 -714067762 -155641193 920111765 255178173 656789861 847575571 -682690319 39562846 -196897296 -370472766 102351167 -118450529 719409432 321412330 636636826 462835736 -48192357 700687613 -885845843 -466910415 272932883 -647551251 -315695938 324881850 -888670375 -212109026 -363456274 -808595804 -91903003 -127502589 -875453999 4160385 797070972 -828392476 758340084 414090697 360098477 374428477 794524770 65497543 441743709 -676508379 -293889101 380825968 -153034394 -943649686 253609098 346137516 10684727 9152199 -35519574 -158660271 -157765033 203663611 -82962571 677496330 866532309 717886657 643970386 -684348131 371679046 253771289 23690369 -204345502 827201942 -178008879 461414728 -313757735 455633218 264045833 -612813095 -935081914 -22858095 -513307437 169964336 -289417951 -130864475 116713848 -952764914 -954543415 -940993640 491927939 366169193 263415940 -343244410 14015675 929336612 -775564404 814362471 955515922 -334192410 34673750 397709429 179143868 717081670 -753435670 -752005323 831242363 25831179 38548359 -714647035 -733857059 -108493669 261695735 -150810829 -924562651 -57704976 901425796 -367475658 -480986655 -7530259 407594096 263068493 130171716 508883307 -963991311 994667870 162217927 72552942 -565224068 -825522946 701158923 -921358251