1000 162347439 569957770
131868530 341372779 824691456 901266737 179364585 807203136 319599223 185024605 191994759 442927487 488682732 246183581 206720245 583670274 204930335 269644290 91566463 336313166 261159071 445534081 944653260 940193435 402541259 727389100 546204198 109922460 832275238 892788652 754068423 909998038 50231045 32141600 189471608 105999361 662632879 279435249 675650660 632481590 103505338 512903830 726024714 142285536 215127488 82972670 530192176 907051 194253355 586921494 511004929 156522006 617192123 340719880 958709387 404114198 367845764 935470192 733281449 262168203 544715501 278620250 508776691 682145973 880954582 109312573 644029470 63840769 393858755 526475224 342415534 901932151 616737352 806780297 963645892 287168417 19343798 40671993 389382135 712005298 503315297 550265801 649751707 881464952 987354543 69209892 416317894 375685070 271952567 221829236 903411158 421985868 119011134 669560396 456098227 27711460 901431994 278280717 749287725 965001110 354742321 867630135 183877151 784993691 631749999 102861022 232539667 717717967 946011934 222370471 225361562 3293036 223594581 761185501 397076088 792974752 429146568 594252669 676877132 544787226 55637603 418232821 740601444 844508931 779133229 301593737 335752317 86980058 561545344 507177083 177096661 86037388 654281976 816652551 921050724 191074325 744463181 111185092 12945121 694537952 110722262 765976271 612487201 26288847 363404845 775169161 302507696 847180225 103835732 689911821 815428236 554123591 478432068 339471982 620984909 933974504 800905911 375306197 937385638 719621673 787715797 417868341 96852978 560481996 857579958 956741163 526987678 321390044 137877990 865246287 242963902 65878599 569214264 353010896 137746059 731797558 124047339 965153802 155590165 962178351 178693452 609276764 835007261 509370741 560575717 127509645 167262368 796567156 462225436 655359774 659697529 655339404 758430823 946856366 665299974 377022134 140131892 687374591 762659566 161710444 598619283 174927492 362150685 96766525 674361632 257174203 974645950 273727283 883335252 824000492 209543424 575869154 406335896 606414596 439260941 445675966 37545490 537366205 974526603 705877542 327362415 594982645 285159765 461557488 348608508 746053027 617782700 41114280 491476136 888941164 898212341 101754300 805853239 742869228 656486349 362938214 548294875 573029759 998075467 868481572 412969357 758191483 589774779 350814018 1506426 226549296 294285373 609565911 754554362 147420327 539876051 514178104 902826143 799346374 232507541 47994755 379465742 425786848 537733540 281107775 369395834 290420576 777412161 470977801 653767496 119355247 417361917 570051228 700762020 504330565 452760347 915513474 684150671 119601344 339791693 58703798 205723596 348832655 439982438 779737419 633710312 864453821 482618341 688254137 635021438 954123089 664311696 511213640 417570231 880689289 373279913 676575574 418998986 260192917 832659070 396166329 597867124 841599895 11995205 11500083 950406956 506752445 822416552 738503505 74657716 399394283 707022101 389230511 787327895 926892279 345795900 310690474 228874829 852057525 648120184 103369987 495009442 810344237 740652964 10301960 458088471 670788670 201774582 582538491 588412538 693622558 85724280 375305613 209009379 74156932 192706838 408173317 384590862 810220747 673207912 650958856 777326692 242564818 207717641 802441202 77254838 10165114 9150453 103620632 694910264 650739561 823744905 462911635 143398061 960077050 246567824 695925169 691651639 751693212 475895655 621790318 174600957 543645149 210917747 844387030 896422205 163452507 545843407 138647109 231477194 334287801 705763185 293969868 256488921 520253833 770030275 312261282 942062845 29053594 481021733 362517898 325357424 178628830 659849153 497688992 970382875 887218418 265144518 955158244 988540521 645317685 111734937 230161433 187051655 514530764 508058169 127040817 693470276 975150858 836532778 157881954 917952629 753973696 756044258 42725497 848302215 550770063 838030053 944262341 501795349 710675493 974671933 948207891 364502528 577615333 706119536 16529751 496280344 254318755 879691449 721569918 437248005 674322753 121978498 875752510 203995499 165877774 278815593 69607527 665120330 715864634 403188586 773577686 131168516 32917486 558703056 640643987 830348238 324424404 844168263 643607535 812778118 256348740 218496782 99950534 894034712 910665708 212752909 710077598 310055091 125197460 616469253 978228980 844150204 380353886 300113646 819399719 115097137 512691663 762162557 157174047 782868328 7638117 643994043 221681890 715506910 344266191 915803029 524349169 592706374 896362138 840161230 916796847 174658868 57852951 983060918 284284218 302197490 387563653 513561475 586113945 436465390 425158621 842219143 15199126 232332512 345609017 751633658 38022118 714360926 557704623 851874640 743990408 652913676 531591635 341642088 290104840 858718762 436148832 504806553 146828049 364616707 276502889 168743984 457857531 680137212 317141739 534304098 961872957 526724399 249100020 532215043 210356632 810216836 949969071 793623344 979993044 362587313 378258119 108672393 49547950 519585936 716641451 957112624 277477099 722818117 292923246 121047463 241209761 369177118 934241789 861441771 157282156 797391876 45091058 120937972 779884325 515967550 180998917 237131018 405448734 263401131 716818499 771311643 440286941 955333576 599649039 848357961 207514805 713396428 383494029 753974965 604010313 942684221 672534721 959227270 814170763 265919375 681961609 764451329 80137028 334537823 474271487 721241737 129151125 149380832 613163584 690207609 536642804 934162910 695051674 271694379 574101352 533058387 692469033 501644160 51304067 731675579 481215369 44833962 747152353 878514192 152532215 384615693 461609014 425876653 45482936 190777292 361509292 382316408 357282665 189322126 612629859 619579103 22599111 674205963 408254444 884954906 187885148 955795013 932833483 244336540 394159593 229718108 587800065 593263482 998117868 623142633 497325264 792156234 476796890 857106709 788803871 8614997 587510877 184782220 856159064 222016087 652506805 464173922 118288050 720815458 27043280 723864937 660357295 542986209 241581545 372233560 217292844 38999432 114809456 851494883 843246788 468030776 551601258 441363581 404336371 451508136 186752651 387519461 562937185 547507860 638486170 4061867 117857661 998501626 29645511 537211651 251715360 545367524 169577499 963382259 266819914 99705031 754912431 817793441 942357424 269721548 29350124 442012724 461557939 485781952 802273758 826556596 223695829 280480956 254396588 484218158 78920094 355419233 92511837 35904963 786223976 467491787 2004005 80481728 220347936 173829931 101571990 374160216 587199734 442204296 675453290 522228879 387215048 713861032 792611059 35215997 766853781 379490130 476929534 113950048 821215133 71597778 519060927 282837185 434305846 835024878 446254036 975879168 358956148 118623129 880367201 101663929 645318822 375668066 180601380 786444592 747724066 29860560 131501728 976304400 943463139 142928020 440747623 321966410 661040933 474587405 576984836 949095900 279516795 951560021 189884921 205061523 700419384 430196342 290171281 387363801 298475881 765262055 176575417 171975268 395570575 349723687 778096472 884937544 340214708 248401573 305272949 253839123 720848664 961067737 898542363 815646692 780344157 404525403 503088126 462099187 871169287 740085045 938059888 253323471 804824034 925955103 352768683 394976949 352267031 392824827 452662905 114830078 903212717 908383671 597553680 103739824 401958388 523532836 926307521 60572756 124065663 154671871 688031021 741493678 731831344 50527266 201137211 792037109 413148481 878667022 335118450 308122962 800571430 468298423 228661626 199578572 771035370 891072353 387296190 143743184 233260028 680554401 914609870 380638320 878229965 682470169 62761210 208266662 823190976 34996359 240865148 883094537 900732998 828958227 953197289 197463853 435233637 984407267 291346134 893486403 51031740 582950245 727152555 437860601 624370776 691907046 401539964 472462992 438169196 448903293 35613533 888260760 433398317 142613530 457708037 293367125 111964031 231558792 237575021 527531505 792661227 264096910 43542173 208530399 105099609 327934057 860771229 236646046 728466627 627560540 793379043 453711393 920142457 653426662 855327082 927716061 292827717 40591888 705657687 45309824 933885247 566704085 402923181 574456257 85394568 107397209 666428285 487177312 373127899 385889156 310135533 785166688 125129423 36049384 631706638 455182578 420962436 866404062 666414351 855320112 458960599 842043092 76250508 844784781 390225487 103994419 651590277 239481623 509126607 631866621 305462573 304442537 386510924 301494394 844375320 616448875 632746753 191754755 7221689 454773938 8617937 463955807 460667986 741629475 755832445 272008873 43449832 234904930 550325708 8353853 882656140 434643522 718616516 547626958 617265747 459040585 365919681 320544234 452831860 897100475 694268950 470437171 493815916 344020873 604980897 790879374 855378619 415419808 778265481 825428114 583230120 550496534 709868854 434601855 213912620 649383149 419914143 394890254 575108949 895333697 87445578 239434606 196097538 148680997 173237822 923392760 791518045 494386540 38471162 413337914 913692851 437695023 305072455 153703034 925693910 150101559 679086248 268815128 784837970 86004968 742235598 554835177 527036209 645901540 95114820 985712857 823579826 830241665 933022129 668921821 321487391 667425667 812308527 215071371 892789635 850106364 138281736 625617645 812620788 963738834 946829372 533755110 183755104 665441659 426043293 911207612 702736127 348045872 594031409 147443542 255688188 150829273 168415053 631627347 425792097 106181534 723815583 332036879 644864225 882343708 580292006 453025963 457300590 330167012 409471984 530655663 33561848 377366224 203320114 182371553 369230218 624999232 568747807 829739077 545988356 337167552 784552192 330504284 31726015