1000 176
188419064 185318233 912873286 598918985 649826077 334544151 873411389 906854824 894917424 79356253 671076682 764816807 832024358 489710648 153395493 637433439 532630896 587824242 566785234 530258610 71151839 698347359 338665733 545706336 947031706 922471699 405921448 551677592 167678918 919665733 124417823 806335084 136774264 847547854 704819548 897287477 148997251 202556419 866058553 342554620 531391005 899373953 537087446 149214793 301948530 490144894 818423225 104748549 161127488 152546805 792865540 588889285 986805841 396101519 481375842 423692128 472436287 508131452 979696314 660727913 174368325 499329475 580150723 341772390 541649566 192808474 416350623 464473141 225007694 375553034 222669708 815445240 668047866 15297182 480917472 570397789 42664936 618459267 406723741 987896542 645320179 885364218 720066104 517567274 405549808 288515455 543777944 10185001 440458655 240780783 31409250 847435391 514238141 973256239 553910698 701054243 523739590 603854207 867531105 606234131 778182847 649907627 392608817 1789119 439874381 369958408 417247682 329278827 382800515 977933187 777500913 726698 892486786 736344711 937408167 405286916 479730374 64760373 334439950 360952858 890834904 127848808 828392101 37359965 419957111 683453066 215018963 24684575 445110686 11964101 857827417 425984023 934855025 130565348 619183385 446127609 941029385 366034317 520466498 102277348 950814542 639707178 746635472 649722187 676187550 644677900 483798664 864630013 511056476 6773741 92512440 27735019 501718509 523165289 52990724 466015533 386472102 990567472 965471204 357536066 946363317 389104192 924465444 835706369 154559511 623092181 514574234 71075121 257726122 57659294 551746453 528551809 127271871 396772355 595322140 735431332 393834891 628062182 456645527 306537 728026307 16877658 820674672 839714485 550119020 164585174 938688808 569595519 253805511 940496806 997624591 966606645 692917954 844252740 93115899 888923257 110837652 905058751 171156511 76555804 857546099 857242816 788287158 415732128 574457810 42665657 193498869 533171102 694119208 116704044 842363791 79114472 507658036 467578820 695094171 314768986 112932490 881317679 735536560 315590837 986359026 822576301 249861132 4891212 735371196 949208533 935753408 54329029 248846704 262883351 583839542 24886568 796416841 959354943 138352930 51685121 151444675 349003046 306879471 663840296 608007844 322015798 601226553 7486742 310185568 240572531 804997747 714692647 254168731 378278431 133575012 820285338 395897016 738979970 793977791 585986575 586908443 94475323 493610117 981999409 612307218 520672853 884076786 260179284 490708586 602134639 133042884 706779820 583697994 467504496 597965758 641830987 285556141 108040122 194265796 874065552 389257830 680725132 526384559 772986958 594880670 113735065 384149801 519302686 202482915 692594776 868867704 522282849 434869696 99208992 846989675 60659193 845397087 616016237 560874805 796891261 777532334 996629041 527993627 568217474 846747459 229497345 518743523 405076565 64235720 106639650 509768179 413870664 875845914 840167280 454416014 390199710 796321706 51733579 6450265 165911416 948496518 669677705 766376057 691225518 117982955 198041752 678160388 810141545 149481170 280855628 807919573 555715240 70234205 307705644 192994235 693117016 546952568 375675118 381060350 761806927 355489738 483426096 348683945 640270234 71088183 926053138 157431111 435344784 402604274 550644976 496466802 189117796 37627323 693432259 883262476 212707446 496197982 689958214 23817424 923183428 547911726 941300890 720933453 801828189 295267768 539144592 818171404 837218528 779057546 457759697 885625578 376917705 569510936 702335133 370137511 207324109 336753479 74279542 25452303 366026629 10986958 340635345 45079290 120524103 284389023 854562297 782965342 668147790 88109130 25791167 366046458 540159555 512493169 153803188 311611311 511220139 261986391 771252564 233222410 413053617 890436761 596864891 282394361 546438928 549078612 577605859 176207952 478117133 511890881 167031962 826676375 241614271 306408992 894049349 22811459 738206486 528279143 982865840 779873125 54130074 849988761 316572104 616895006 959287695 321375080 439378810 731235040 604337446 992115691 569741438 525361839 140689410 51467938 731104297 879494683 58312603 481346846 537962893 44354295 552637780 804711981 201848455 413338369 750424229 587484638 896176817 163382500 979067997 458115038 26816936 240582389 309724909 297708632 924823819 38402444 50505401 983307057 272025198 441599556 533388551 903888407 740197140 318954995 228056418 623038920 300344188 506351991 194538429 979791042 443062054 295010011 504346045 911993994 899226965 963770009 770754378 788417164 715345049 428108753 572669755 834182307 328580205 254532021 70076942 713374371 258807603 733185493 194687260 576769932 227897272 975189991 226774885 319406601 430546681 395036214 380714883 164821413 337046759 711953741 881237574 673412239 202737416 164872718 163653673 60699583 76002889 839548792 924860157 785703173 194346303 440754744 572267986 760957121 373717816 624488131 555299747 902485861 642566340 72327732 840077034 281636925 507263028 781686180 327240709 811919756 181079918 946347401 606817019 929245853 132004388 90089201 855807155 588745720 27789481 938951466 845299843 316099108 219246620 458686112 487857847 413485927 730520697 996542903 784166836 489467913 401779791 475175132 499454758 973742284 29572654 984901564 344026065 40355327 261578850 651829028 390069075 890152514 300893372 534563463 159739804 517082625 941730314 724073851 429278832 825189900 637802712 922692446 926761139 99075211 572473815 768690976 126999167 390897522 788581361 60580053 774664073 703573803 404609747 96352723 539393622 805122027 424886006 205725753 224244454 115009183 762921711 666479767 744435026 873560507 647055893 701718654 455640493 426944170 464806032 666823534 298443847 271531588 265724591 817651416 848971401 18436864 859374219 634146740 15344880 654757420 719606342 930580480 329922117 517655104 919347339 713862192 242120151 861900830 335403143 287333473 747336095 655776801 74099357 754683574 708039050 198870083 674678819 843595353 304021645 574121256 712769317 560661199 902924705 357745514 803941225 95363020 517842339 692162258 132445506 371271275 892339237 523232607 489718073 981418276 407877530 278316214 547753183 132361276 213547625 139578734 336191160 373686152 735505543 918768985 563474384 347245424 762278857 47897788 761964599 702498193 753579398 733062866 144188616 798995413 650201451 515491568 480179929 573885309 62090949 550393740 835053786 446545838 219715174 548947267 12940278 613924441 643436890 11647365 172105305 984831751 61706672 429803642 933770937 600298570 148478600 186316512 520049332 740537850 367299294 402303615 44740600 390417990 314353769 631452663 350470394 28181577 493437691 255845411 706734573 888517712 999977953 738102169 518571269 672004055 942753119 429976099 527450977 283123661 593682316 819735874 139067028 692095461 570825800 610436858 260562019 9706865 274048427 206024753 433877658 240512417 653738270 23398850 617329721 394225648 306275649 770033545 28751625 372747841 244046581 510369798 452831051 408565522 909515429 191852124 610362844 851995471 877507921 949089695 594027444 790610672 443167435 383631572 328581807 835196569 970093213 852398432 478248713 215162321 359246691 271911444 907728200 334649324 811864359 724392121 588739476 250137960 566064236 440843629 497350623 30090940 96317650 450730596 687497218 158778522 375533538 142930220 17022276 261815963 726055683 744537242 129307011 428691296 797916638 671448675 259565574 911876778 586407623 618158728 569764115 549801640 176870178 529495075 439037351 613667086 819037668 891739950 971979722 759596527 18165086 689087302 146654182 245673174 617439575 433536582 2513108 418488295 757990017 986449771 583012915 11675745 672864535 816136639 624240897 539693763 599013790 925126617 102412393 641350123 235224753 271164642 463917446 91606841 334390492 635389321 783060524 819439617 675273006 32140063 311470378 263299688 951089234 640985579 644241930 901570095 846625165 403290795 904585287 120538787 197633255 648467092 397731193 163726087 60968958 901601760 147821143 883266002 587466247 73561065 517133206 753954475 437523441 339023397 716962397 2940581 265906556 525391742 414447093 791939309 938216270 227425779 567090334 516341972 681433503 29783635 745497172 203094264 446714347 260201270 430809454 105555601 470204336 843305670 862019697 572252251 363615610 793944260 885282066 218634495 40916831 282067532 252835156 716998021 897388821 263438250 932770988 713917304 207674920 736759874 217159763 93465082 754245909 741661096 361465443 29578907 205655874 777668835 227235393 89938940 304184260 46547604 832987947 533992658 456377658 480529037 127088609 768010722 371536083 231694127 323167793 928873157 76101699 819716335 823291539 407467147 731350543 956411651 435562103 264771840 701542856 251524117 338709408 289743137 935836014 619889524 500781718 194947665 111202924 883349021 475181933 606289949 360130793 947272168 34104187 894454913 349709798 495774619 976340823 317834204 259649364 898499965 724002768 964136039 154139840 864993182 169320483 733429181 296490970 387461050 14614724 582952799 483645360 935540237 969825499 667238627 281530917 295905755 669827565 532021681 844281111 969601173 939456021 280132264 25326330 767069696 845118423 842229840 81399586 529352560 313386673 21191010 742652106 948042954 368239583 678448229 56515625 796506451 743245011 774079090 556766078 705721701 465260239 504722846 413556890 54387657 628155668 976041544 917049622 628575025 420459670 750615169 387614081 248903499 361266831 66220109 199190718 179221235 832763202 372456796 230161581 25685400 554411585 378112391 781341403 72854278 25794484 634633016 503514111 313057835 402218354 679277210 72783047 593459022 818724364 266727449 402986248 394403771 372702707 705495359 673416843