1000
-912215076 -128106232 -102864698 619698443 268253339 33367895 -326845359 -640163833 -64932798 220663082 294515796 -2397506 444225066 698219165 371958046 -503724937 -698932150 -375063184 -562125604 -116474044 -122788131 -564347991 228497821 145418107 -322822664 538071989 -444332210 -701336565 -627413041 -97446472 -195762206 384864883 -975044688 645983396 -548121395 -378082831 950465341 -862089963 -286969065 -946759906 645787587 -39914233 177178438 979331900 534120441 479187634 280080306 -297199148 581468398 -368560075 -758923129 -527576084 -99687976 718564049 19852620 230099629 829434445 -657587318 424796226 371164897 223297596 -312844577 -77199871 860106725 -342657408 466140265 -631693839 684545746 -830402107 868828926 655854297 713833568 497075892 -169917544 -147150078 -655189391 915264438 122490160 482416399 214277587 155197558 -44696014 -77618601 -667223038 -316511495 -818744205 715896953 -524481008 108281517 249843089 310155675 983827758 -289262427 887820239 -386270536 -650495466 -125086090 561840519 328711889 -936931391 351927225 660169122 226604345 512914774 -39492753 -757506486 -806351144 -176255325 -518393527 413419741 240783306 -27081566 816339016 -830098325 517650664 858971408 -697579442 -860366342 -64182496 815918537 155691417 504089189 538208513 -958245980 -836961306 -299738216 644504389 -475932147 -850673205 -427759461 211610026 -299969022 646058632 -691093010 -601299007 427809322 -305861303 -491529594 -97744537 -255180815 507753897 936638402 838637296 -613193458 -747829457 -933931414 -813586220 -673332762 -646164963 818394995 835579678 -41078584 -897533407 204150511 -637428729 -237703407 397202359 -692853430 529042407 -975603699 -138661230 -598389659 -171733876 -6177597 281843233 -956406872 -958140158 -447391277 -448096993 -379504307 913122930 686309738 -966294262 418936760 -574905072 489148160 868059111 -74981761 -627198645 -638252028 -459373859 35407780 -919436640 -527730229 -385628506 -503633073 40012771 -750601837 268448987 843473373 -791709532 -623418017 -650984286 -134434765 -581997968 535663507 563524078 -318387920 827678127 -641021545 -917744444 89517789 -791676143 494868830 -252965689 -438637006 -203070097 -932673759 59630469 635429420 900780831 918805406 770792170 -92513210 -982674892 -598200970 -221665153 -7455213 629671003 -95190524 347398874 -788446092 48309748 784872025 -557434441 -36541061 -506174534 238435062 951356362 259726544 -17354298 537769289 -794900681 125278561 326919302 -671807199 688418424 616028706 251144926 -724557807 685812711 735700862 194993049 61051912 -457235901 771815741 669602900 589045807 -440846328 170218267 301901690 -647554754 916824847 531927242 940186081 374542396 915760101 380279850 691862444 771129030 -353922126 -73429762 -630469755 -561410447 275201227 566900878 668168306 611880357 -630446280 904343303 -771820528 233019348 357499375 131056672 -997545783 -1006395 -297440925 -670376768 470814398 -933628680 -756426065 -114549970 -167361839 898069354 378731313 205936611 902429555 516083234 -524022839 28877464 266061480 658489693 504028484 -94847665 219520808 553597072 231379038 142155386 -852193736 -151141635 -155094041 -79423662 105804961 287299198 815751533 771835870 509270943 950191430 375095502 -290218062 344592690 955233441 257209401 -186225788 -778956668 -726845540 -779050223 270390039 -200218631 644503907 -720150914 551640430 -135692394 303950425 -433862508 956571402 -681765978 -913325953 -724445198 -453457182 -935634513 -441102034 -165993462 19792408 449971809 224114604 -844894788 -474510059 218289671 -766584041 -569020174 -410354051 980890724 79303255 235016098 -315462071 816966069 669834534 -647769940 326178364 41568628 -582829117 -52259528 -192469608 654435992 953712359 969669380 -663863197 927352490 31660574 -194882563 -114964592 -767317897 -516351610 -514190543 760165748 -517444613 722636501 862210417 -907358074 -214783155 536644512 -401331314 924593582 -184529060 -378929898 -442718541 -130953662 427620502 -487890763 556603368 -392193465 42975143 -353234873 870386058 871219092 -400244184 841541962 339367294 -282601840 -337218596 678555924 237734836 -695301129 164746180 967456899 -371442373 925287403 79167033 -761655595 -138638606 477261774 -774666253 812609753 -600889637 -314046077 20901002 -416285916 -741038540 -276967574 -416258260 -950172627 101300691 318541743 64124002 -764590666 721478725 144297343 -272960100 17839846 -404398839 231215210 786841818 -1488394 -525900994 -495422791 307482958 481211791 -819536780 506957398 393674969 781055099 943963949 718444305 -298696507 -385643943 634036049 -80918246 200123229 5963659 -174949561 -316527438 -219617442 -424492426 -930387872 -738521200 271892289 117085310 -331072119 487490564 526240634 851615923 -636593402 480609857 63910940 -900715404 586657349 685373708 -292560261 678114932 -789963423 -864247375 588264708 628262492 -548306902 -459300714 98128556 -300002683 -920692830 -487738776 431049293 -990229237 -871096867 971542694 911140342 -715185774 253516758 370161730 341295805 125026312 595478004 -547489264 658247290 884857654 801254035 886583191 -778122146 -341759468 -457656884 -943815243 -251707822 408841105 -836376072 51369085 -432174159 -863918366 558398335 804437141 -761337000 -672432562 -237661556 114703364 695059269 -806451258 -326130904 727269600 -515383787 892365172 331002812 21075834 581109670 -984602053 -968372022 943033006 -956322882 -244382967 226680635 95607735 381794654 287642985 610766340 -215010228 779761227 -407314109 573527130 159837076 -489805363 584525011 594561182 -387670314 668949337 -660020493 -682411429 263697079 890624907 827303466 454273730 359596632 651018549 -110793301 973004384 610372448 -469427550 -558044520 242573029 519721178 -580373727 -98607778 -114317293 744529749 -145722571 882512050 -964180491 -27084248 296726326 62211580 662778047 -293132354 919267808 -286691249 -312462682 -126889468 507575284 851668340 -352642353 85843863 922813662 -526615067 951509536 444097959 138371190 835445886 838098673 -767747756 120960987 155674122 -891245570 -356331814 346002919 -786050956 866552270 404641403 -254408353 395478190 141332907 715643544 -959118473 -896113946 526629065 -967349455 -405580683 -680998044 941855900 -278210777 927748435 -897887137 72913677 673569982 462677025 653435236 224966273 942140981 403061546 -802797449 -337614600 -71885990 -767092579 625069728 247707496 -20381867 684480179 -726059027 472109323 377037468 214336661 236888929 674017337 -440666260 541905909 -305074637 375973859 -538603832 -455982725 958913124 -866504389 -389700082 30796348 824126797 -266476443 -952329837 984941211 -15822290 975415192 144655531 124372625 632462438 -684548297 -888299053 -232544673 969757829 286563652 417689393 840154495 740632522 930678908 -457000173 31945556 -287412959 -247998112 -177432790 400374087 763307121 334205271 898741511 623840156 231840585 -314093239 964523453 -581944357 300376431 -547130547 -725834345 973362215 -704577193 -847255032 863189847 -533878608 -95592063 249584979 162721133 584030790 81971321 -859493816 -89056206 479305748 947840070 -993943856 517547079 -78899634 107145905 583195090 957995262 -966258591 -176085819 597466709 385074344 -463317891 141589617 -243547652 -987590860 284370265 -62436119 775182474 -142806362 662561697 -469821806 454351110 -400697904 957943459 -806376601 -464109670 -912363743 -653279065 598965562 -731132629 -467617945 143009626 -917319094 174112107 816226627 726160126 700707684 650751254 -628001892 459958547 -373577533 -628461844 -539105774 -208933886 -714616314 -842956641 -901838760 709462635 -894164441 -572043810 96140090 -794594556 -445318611 383089655 721824812 -17915507 670980381 -501534107 -100400365 -476689140 210942254 -167036874 185345514 11550943 -600931343 15745910 434801411 788292043 765260592 -30799210 -975956822 931266880 -88864720 -643877324 90926419 -640528087 -39405322 -899048050 -481468504 597250161 58466066 158653226 2470733 173983423 -478043125 -275237629 -195979794 194637424 347132952 -269000183 -144734340 479944251 6217622 -622088719 -939117043 -631481078 -566649524 586643220 617186043 439663494 849109061 -931613082 -243303355 -463571414 17805953 978170408 -662291069 704561798 854858162 -57495834 876775528 263704754 -910184215 9747001 -967227309 16048691 -491844216 186540153 39883156 -982840320 287715530 -558779876 -424792231 418667140 418651091 -87616024 -690406520 -533987534 -77164447 -573508898 -541181719 339368493 -470667759 -556835319 365569269 -425286160 574062668 -885055203 -330774201 148146040 305607346 680622841 -665830820 575401648 -706942086 583099393 -851818601 -250373132 814021848 -292456927 -594397031 680773803 -570960357 -231621812 -188466381 98299788 -431484890 -320727930 292098322 -515789218 274529628 336324979 -828382415 -778041567 -620672260 6083156 279795185 -980950954 -947946661 91546185 389821717 -986058399 539576733 -172604541 -494480340 16129551 804849737 -782190556 -146148810 368642787 667509736 -876545899 -873942973 -720952221 -572831763 -87781374 596343940 -35479849 -805962473 -965980080 659695096 -478863756 401281875 678564154 996433910 -127110482 -885146035 918325504 376203816 -162892850 530616814 -270929067 576251043 -151018104 -823694797 299238543 -349717979 -742922786 534466075 -517668251 872138082 457964369 -235425414 -824238976 -680492626 -470777995 -729463108 823211207 579454731 927443328 580903376 -775505318 -221350946 -244909180 77849364 -360499487 602522762 -953844922 590889294 -538935898 -665463025 -560710354 977911304 -601887121 758969391 435688440 -648831869 -608257871 683551032 12128282 -953643684 878564027 -713257981 -225997747 -582016338 709868760 -322966894 331169807 856279379 538138496 -700364844 36558451 745048896 -739867019 -93688309 -313792985 715505919 469625499 740053615 161948074 -309394051 -702207748 480628551 -244199015 460255327 37600743 -368697404 315442999 159782647 257601125 409318734 -398621280 607856033 614887641 193932947 798240648 430072760 220424228 -400532121 -124621458 -78470885 464297760 114556064 912688170 711368834 -27937926 -903780237 379848652 535769956 983218006 667717599 890637035 499676365 993820648 268804391 -751009021 -487406184 152232499 -746889240 6936066 -577830406 541717059 741653279 896133486 -821081369 398061416 -941091711 -561319749 689628827 -295012071 605051375 7482161 -332556789 986363363 699023535 -77438086 -454095298 921316240 763603223 277608421 -862053845 -194834929 309693515 -579541820 -543651615