1000 408087948 455994206 465935760 577924196 29102771 44567776 532788487 532378662 876397676 266784556 234023776 352057344 473063780 320851360 208881020 965363804 829407460 999908910 996330695 347071590 872705365 799284554 292266819 160758359 595050579 803533567 193352750 312624592 490766442 286361373 757188700 775254640 350011021 8604387 203456024 37857407 814707230 569642095 983182988 155982422 919250016 917960445 344095650 947959542 41315989 267763923 61504684 417398665 724421214 638433913 949566216 591873319 286850840 556521866 855266545 65823868 933758777 983574137 49683788 758161602 710657104 19066331 696044800 115155004 921733771 809261856 10615135 31504304 61741416 982700387 469707478 110609417 734786514 625454272 661626507 820679215 634740777 484664939 674404634 845464947 893622205 331084437 40487436 75451620 889904602 581531100 235327142 191973003 52282305 498471581 169235828 226168981 278461851 761586242 382052125 33589751 353247661 904441941 757094976 422256793 792642181 783874112 778647642 91449806 331741807 9384311 174675771 632499127 83781649 205409100 287319295 898623086 966175938 150355755 287810978 337564681 642640080 28159516 658682199 549353699 567005805 513515620 21373575 708905270 486701387 760021764 432781409 505455865 2516794 116683540 257421434 711170171 809174012 314912225 382078083 148781360 605146880 642887304 75670374 999452929 79313474 582721909 778844644 876878788 8811326 489385944 585779621 100187813 718651684 588671193 261585567 755441500 353003150 778058953 415465478 469681266 207057945 857277760 119509312 801583313 674915996 631373972 458215562 468969400 181562580 254607130 837897434 523516682 700477700 413547730 328941248 61727717 270184436 40936401 535486822 490729507 922862913 911277718 553150838 85256189 866007902 810071931 501030345 676785963 142214983 48421867 253161956 404408624 160936160 215539759 993601194 327714934 199912478 613140941 21436066 146683650 734990266 576169620 22192311 807279087 95502949 341070449 144164001 183392039 575294709 562220730 737763171 591707325 768717754 390554135 70137325 409731050 201441519 423891213 205096867 921820236 380895528 613484146 115590867 539567033 548036293 447508841 959774778 713315612 877230457 465403970 445443554 732479315 397869858 537253747 547251769 615959432 258608076 742439120 338505715 233100974 819761657 75732757 365834683 205608485 581904978 548363326 445489792 527073721 451541828 788002457 830862246 536990018 697365335 994496909 201425521 48807316 989038915 220719675 874174535 291655210 323738999 379917089 90000375 392211168 646382137 414047626 397318211 267751823 870552760 76804684 433378217 261505815 350178633 772936810 557044909 58367221 314637878 511569188 153216434 880969367 374927223 330707215 329646626 748357300 775355686 284842452 290664328 751285470 832317491 758569221 598709889 95028360 305492389 895807293 289100496 998244024 999605759 456979157 718063246 130061898 51937470 651747392 140913278 759861982 607897598 880737796 876743039 11114079 976344635 284063830 524797210 728871217 934923317 460511312 512216822 696211181 859390673 507372797 570942973 359927245 910699249 644553374 996045640 434964708 83669023 639542073 141232975 972947418 493499315 516781784 611654408 970245269 548322755 928659174 382743798 197419000 305054387 959050925 490477037 587276375 746405031 601526944 55235437 583854237 25298095 135790890 832661513 408030199 29562966 130055341 600665822 500289220 672992429 903262402 411311281 492369578 346770416 624336798 684784293 644035522 765772760 22302608 213071509 87822579 614203516 247910054 959438612 823986012 704364004 57274992 821766379 355272748 181877724 875322043 217864274 163466560 119425296 444512378 359767452 121791607 879205793 983832888 677540777 307954466 908539143 654637330 13639952 396098186 299708800 584125116 709549752 997048187 218213532 770269117 534473699 300671025 261283056 622897128 959728743 623166711 43024653 626981705 291796052 194538644 851178874 246943620 240052943 767446029 791414845 474569705 532631349 494606826 883227857 403747273 85044957 565435823 26518264 516579728 107132472 100159 726056481 455510007 101724337 732055414 882129887 833950265 679405911 77507895 331309595 983683880 2971273 878837466 61108777 537105344 550005593 797613303 315193879 892594231 432410362 246873422 829198875 266026851 334555629 887830259 927926037 462859777 972705404 746177442 797601245 413854370 922163552 840688825 898905525 48280627 586540162 829077974 117020126 335831335 309395422 346065677 89137222 989256515 12509828 167548102 969635678 122473990 546407864 420892466 368206090 948249522 559503930 383716712 531627698 187773179 111668256 543398518 621811531 190548447 107425290 4398462 313133488 300732648 447387596 211017070 303643235 260673134 513841047 521203961 806041846 869625286 718415973 808967053 567577 857210344 322791633 664652332 733225992 646713234 618756498 710522203 351056021 265402252 808756117 999033907 490788813 203427078 120742327 37393556 668846666 316444189 460124700 775003257 429468693 341043836 936706350 910566503 906648373 502816287 804959286 946726144 498542809 923276851 637113744 42060212 282198301 695187994 976220814 856730775 317025148 381444844 709592531 73315029 581588459 995741985 628557326 956654860 627839029 917742705 386034587 972007530 216441300 419395205 737961665 48574644 631522275 545876125 789042809 734619334 851254646 350686211 818664010 653237476 464750720 302669252 54359165 630139795 275707554 652074517 14093893 979848211 537845028 673139809 419959800 975038588 448512001 855391728 855845243 389428083 170276892 19056437 428594877 617085322 55662737 674954676 163521626 406668338 852112991 168973917 452113889 614301485 82372531 347319170 136435318 804170610 972421714 810534791 329013349 219639771 11248932 487157042 559779034 958880605 62119255 738188201 738407123 882863169 558729998 339584010 681581030 364355086 456203189 543944790 506133482 129446267 918220661 347700477 704204470 742409230 580939715 917476098 959298049 166085973 30730515 628843722 165724608 98603435 970560391 820562575 226231065 343255442 913759035 744422751 779345058 534036391 524399980 918079597 400515786 163827149 523835491 611459963 214533771 748566304 543063063 393784419 919682067 682759645 61713505 129501932 821791393 52665661 696458522 984086116 51948561 889104056 110144529 995989447 312829031 917007009 327449265 328354160 244016490 708153951 294476148 274548076 114850414 536095329 774052127 573847477 487211487 633399701 615816900 364574595 143323204 786936099 558777925 55760397 858978815 320946064 600655373 436979288 538366824 918113227 946971641 464223591 742331389 336226705 119483718 302093509 213668549 348727519 772243624 877922115 145919456 83385594 221898842 721734599 636173683 612629366 980646336 428072370 948733432 968769748 261916769 199032653 45439171 761153667 223444833 980274992 97500044 38883170 708112357 316854891 618596108 469325266 431562161 883967452 299189267 829931053 64632739 473146257 50216344 113449209 751420470 909152266 897148178 406261414 860506528 869248665 676995439 575701677 472600176 836999857 942353478 202424675 723699274 451800400 693175948 246159041 204901598 637020150 370803992 447664748 344979767 617063646 545026205 642401177 487059245 484422391 201528556 472666692 588968132 162614827 480293894 550214096 532660169 222094587 180762589 587022258 258034893 944013044 174888160 740576705 390406208 935495460 646254898 748842539 275995224 15923760 147680623 665325827 744187863 42175333 694068068 841954860 447777130 373193480 242729127 976893330 864892388 793258478 845656906 875145180 206408558 157036483 576530779 65043150 541357046 790067846 902234431 154991642 10635076 889753561 239791281 253006533 787593696 719479200 602415250 860648406 337648700 421480312 529130103 939771966 10771963 436276323 287106222 967721170 392625890 630498353 909687146 337649831 65104151 764596156 522434473 809521477 143252543 990343278 944896463 186377799 662087975 964789715 78263347 946486599 924961117 863108280 279559676 112513046 148129756 707674367 294338596 576548867 529637534 915055667 183790806 191066530 945334164 776655619 636120182 186327531 611729609 930325112 675659755 27119461 285725982 536754112 317838330 763247152 472498619 376441696 360642687 121132574 664709271 841160078 292798689 412092776 350511882 993017902 951502573 984840947 479293226 337849358 174583739 84280873 758810348 787520062 201518520 718441789 423773988 695916367 92894092 636895908 532538541 789021748 491497503 566568149 739355550 806572365 975483469 587101551 929624893 68626045 679281077 368723674 225221517 802064650 663931330 428810361 615950143 130658915 386722570 621376341 612567169 143421582 662470775 644673434 633189260 670813827 966684528 2261137 245859797 653652606 504085915 648936207 557522710 207077538 733055771 199524554 481361717 765701732 164966912 376496693 712697268 537583814 593163250 550788755 975122119 664574061 508362194 417437142 574655108 27734348 560697326 104616902 329067580 762164838 240241659 760416221 797746662 239339466 937914715 26888972 284255503 881919768 147641656 491653144 372596811 693699511 526902973 40110122 892361642 169620694 517804355 855633276 699186128 720913047 89412670 863796192 512430860 248089720 493306620 648651232 798303854 511621777 240372654 85086387 832260849 648187264 723579278 260787342 262609968 646635011 2849871 217552751 7402598 548345592 952587636 41989709 731971908 296135528 434578239 341507753 987318414 802036404 830569620 952962510 911114178 130857822 602655485 919449509 747050226 510277233 273878727 285081399 107914419 194629518 344831305 659276479 767469358 855146389 297858372 690468715 297116756 787799020 243705702 167353007 372332846 247596143 983104838 265490002 983877108 344709208 75424199 383557489 996739449 709189234 622448352 341668366 77650413 374112551 628326193 755067209 368095896 687848639 220944583 46674137