1000 377719376
587272344 774194694 680518882 570425820 803564539 106004440 62416647 337082192 80291345 794372232 979570451 611124641 7544523 763967977 625617041 272356474 971173392 530861899 487508396 764884831 112788492 701871341 469530519 853538162 628184698 847943955 493524558 705968585 344244874 458087110 464944702 898959284 411555861 128975416 207773390 36948199 329577224 363990509 478025291 316716129 293021444 809867817 357244027 843590597 201048873 468283516 723800994 953148501 721575125 171801159 235621857 400236465 652950376 223046233 355296955 567280077 741193921 390340618 958731129 911915822 673889967 719300035 807107424 374161149 155424432 502610261 480737234 339492002 574221222 438536644 233720788 854700753 917557123 71051083 874977340 308598877 38503569 158007130 147651659 447018942 46473530 144511232 49197643 424389845 254735901 912121571 112542906 900893088 428430902 632494682 903031778 763857041 675127349 503540780 878274770 225723061 323082202 501354058 407024085 167632017 537706069 331564262 74560167 878824857 596433183 788385786 781868022 672482972 916429583 522335029 754016021 253572439 979773296 384333277 785978350 813115925 494897374 339294428 263878046 985907515 174833418 947338720 978759403 960531496 231254449 736451310 717814975 224830984 953139414 417503767 475307929 430174013 749203540 142021416 93892000 349223880 7645262 234452151 14003916 433821354 121570296 879802762 611419719 505443147 458687281 795149139 959510974 872617252 87822396 39489474 848236362 338015482 431135411 35080896 856145225 686535422 491556092 517928151 597818328 687515609 369060687 361982873 576894349 731405717 723872634 309865484 5683184 908563918 956514657 259313108 102288346 832974404 942466270 222789441 391128191 583559156 304170141 573865890 353057377 708478355 506415138 578876491 758030384 170310579 272252497 759086716 478402655 210425702 925235728 856536977 374471720 203934067 427221269 906991117 561406355 857385077 965658322 763503970 824769549 631436684 722268191 99845947 761054404 108840941 449815009 668023662 105004644 631048505 95349040 196813757 780128903 813194015 700367758 603766292 107807067 845882081 948474149 786127694 550715205 546402477 660853446 258346970 299221831 694393757 222016349 766512926 241215840 726025371 111385225 914526298 436468985 508703347 164526564 305725326 525687507 605160001 750991525 632637308 406797215 698243747 701629876 810833771 610734187 641603613 187405481 34493277 51958825 693935460 517580047 231910276 759040837 771480213 217643894 725243073 284539104 134156644 899149955 722521518 443004647 330135921 529216417 891267186 809923929 400829631 382419398 520595483 836861605 323610325 69583932 569021989 924575292 252442899 361354952 413057682 238059331 335192100 973885298 403915578 811262817 334841791 249119884 844863238 425515961 739754810 843944006 897812860 516285935 261849904 277831767 104705249 995491609 206576625 322314849 183575451 142204715 804842978 816289367 774450352 372910477 714842625 296797813 242993435 563468818 504470551 457005733 734108437 851623309 358916989 975679971 546562912 921511661 835478844 898926730 612881848 494624607 75232922 90984751 9581552 384351041 581396529 829843935 326783057 656569836 522870026 493930693 562004318 462834186 938657675 402711905 862363374 471917920 276083370 438747242 561878684 760042820 40532900 221042140 704537667 78980976 537411117 949537769 503607061 278624873 600345741 742371502 557889641 404238867 520011063 209790355 908622069 44194461 388236096 888511761 909248768 97634908 424849789 365666067 316564738 84896196 888158964 728432553 740308950 800079678 820737872 362375874 12750403 9160794 508751338 245572549 695374705 286314558 363362843 620293806 148050234 22908407 966728289 274194029 472613904 430093208 691471924 279203736 798088974 971187796 966396043 982999019 907641846 542947079 610424263 844464355 249260460 907166977 19317988 108531429 122740030 730305168 863027903 825187401 709980025 924150322 164909782 186445928 163450167 725528653 428572102 268503953 983072621 319517371 649707820 368995137 486221820 174599385 305275973 594427466 533565344 401202997 246575782 781767503 16064042 573452902 352463047 691977374 788192438 420891997 540893864 950707391 785500031 970843716 460439189 317180791 585438877 931857996 546490922 603550090 836179945 163244622 900300414 12248760 786065190 275251317 976316690 520498203 56841662 58033951 352313974 480705449 31324980 616406728 622364133 430633903 435868753 398330821 886794934 655094817 924325675 766303911 852183305 422551162 30152638 112745301 22323076 394218552 446355814 219802708 513353472 209282189 234445908 689181880 415471640 937905417 568565752 947669838 427301647 404817689 632559326 448340842 428140512 194832782 778797433 361697472 19542657 821084135 64799070 35336086 569484980 613822151 930154714 590001539 162559644 76254348 559821031 154377047 743584937 169980433 408116983 648473394 894669551 817038092 269677547 643665979 381533222 923168428 529620257 437956410 931599609 141660955 933286103 596063516 34943613 353463981 328097411 212458217 610960220 307347748 505767153 385202658 706656649 61661051 449214626 967607133 385344424 486424790 639121960 89293970 986882664 548723978 247997923 889552947 593839628 607970905 664142890 378596866 948013845 313866439 632860037 727905829 633557860 493823144 853492864 396445222 983963663 853435982 314203395 46174698 795720916 118593463 643468101 427031313 881730397 135157538 968822011 57227695 383942642 366372142 952609428 212641260 461483251 502237023 104476736 56741746 10900766 77125798 938906053 830957972 659207752 197414787 973074134 347722754 38591869 591896287 812971268 115401159 334269381 248681214 285694258 410942060 84058561 276976196 437720732 585932235 939791387 953083430 973620289 588078265 645869855 540932143 148627353 965216292 193936953 717666197 459442726 444798626 327896319 522839175 968486063 262163274 33747453 177969683 454679 716667253 646611506 417215960 451886534 316998293 50469303 724065425 700764514 85696717 537809930 310073460 761636788 518610055 445452617 48607891 902496029 648705123 166682516 923050732 914915041 535052593 793762060 799479036 383032685 460347285 178747060 577412662 451330669 125084733 339271175 801234349 91902545 786714323 464817721 243640928 253735177 495645658 45594788 501799809 603514668 657809023 212168543 750384819 900532860 701278780 338545269 427289222 389904240 182411783 567624123 982608522 485854223 417179876 93590080 922176259 612120195 59174459 612278310 104909533 865894343 705379366 512623343 28474426 615086851 963196799 261149549 376876181 404499418 598431555 213275116 386177295 548241707 415360191 841772574 446917786 307827907 610214420 62387630 256016254 86947305 270811727 608606459 692571091 143095551 975164286 792067725 245056769 683749462 574767498 765916082 37768665 231268168 486193578 741347893 813190212 775248249 804515032 745336053 386112244 274193099 711857732 991808546 332404507 937202518 758772971 790649263 965017060 120335314 513403819 768311787 474402138 230294792 569711878 614062548 899993637 402340600 55831470 579835975 850304984 577490792 986433368 679722719 91085565 867882268 870877358 696999517 986277313 570796965 244796068 290101989 467872499 521956224 87646122 880375173 400166099 375570121 481058429 592935852 404247160 600123631 798024583 116096632 901699095 956157254 169619733 823073690 401497896 426697877 181285772 444305879 40475487 511225885 725215008 412153453 108148478 888726941 109072693 800497162 322772105 820290872 974386 280558075 491740136 616209991 390161158 390875857 922240407 302269627 173079114 939994529 759733996 817116190 487201607 466242274 469724260 624338110 470571768 875623254 617825998 85611211 935904850 957146701 4914774 516263140 12025623 810015976 760636932 674932605 271932632 476925208 280296180 612188411 848637577 205374439 733773503 796684995 905595757 821670972 667202533 224849983 819116710 291141341 429196544 639399528 202914717 687281404 841667758 797112007 768391567 996404581 807048124 899819471 442852219 675417908 552359485 651227901 175735726 732678768 821021736 643093780 198623842 535897498 861077152 408811974 304097748 334452738 227338810 849719932 287280627 554547612 619006608 842609094 889179094 424778927 946825978 588908679 214470737 837049021 785464721 148324004 906598983 837106754 346041565 116069401 856526292 88581639 848232192 517112055 498103718 428153002 636602101 865809303 926125032 235560340 548524241 544054466 509767686 20984767 179664244 842590848 519143908 740576711 966133821 467424468 366306168 205673969 24794242 196996310 560963 838220436 874312323 87304228 361204912 625414635 583241300 439093785 678703500 577075932 265180931 111571071 656261430 426505045 908813282 264868330 962474518 181902970 846837418 380013679 605602233 602032632 21730275 389934015 494362380 495957658 256073156 407479284 401739050 611556656 498140793 473392396 52702945 457702365 902340246 795057975 540503421 524764992 137319552 234555642 322520831 537864206 180852062 946646447 764944762 945360302 282714613 708439710 634771367 827776305 412287128 844446210 639882328 169719114 261372295 500099211 881598724 529892874 878375764 914672089 953727758 236473626 224960153 30721181 967853298 99240651 749753965 224654854 891848722 616839021 333669806 783289320 294673017 48954475 97832773 892466066 771568861 38115279 398639253 575205983 852777229 289769861 106750258 293512512 448744584 366890438 715587685 633179150 348760858 925077972 889352680 620976611 850879130 257616603 7986253 433620361 692012039 492191925 597587265 381182877 897541115 84038315 911386934 495599696 592880317 425465782 16301170 918149481 580492709 991670223 948641953 852723875 887395326 736320280 542552287 366959907 658277479 390626806 76657824 697675223 514609021 433017341 340421666 637041315 697550310 702059635 557971346 941718220 190975386 793985983 226558721 466202216 286059307 757615601