1000 757
292603702 719498333 636171153 96592793 384756526 536377247 330648270 548875979 651093408 894854970 239446988 443122241 203178824 559157561 299382589 550946439 596816905 519375942 185501824 853158486 91584444 946629319 531170825 914921991 609848071 196451648 259542331 867999852 767085088 317754824 69964786 12811503 713067235 533124283 400191851 94273164 405019963 499308239 474567127 739775424 979206524 845775076 794680739 322813376 194351890 838803859 176702576 57130149 739413187 615621440 321570910 349569743 791543476 548752044 527660391 191947795 583381735 231235183 230577495 836385722 344877183 797593834 260708893 854326884 828189084 478387971 368959614 662131564 866199925 458191626 949200262 249124162 437548805 6197708 830999930 919806751 955648834 697103493 303729535 781831801 631097849 74113546 866390578 882910433 385770275 146734598 563871555 843041092 171154690 764720260 985038181 738818208 490522394 687197685 442346403 202501708 529324190 657790944 539911570 108590340 776104761 859617456 694728333 200370719 886929075 439605327 765205861 906044504 43844942 795427336 233151428 38122252 684181585 488506166 844519067 525146135 485284826 835283202 722770764 596965212 520959802 65924458 394627318 419730848 297512003 660200376 53542213 988034449 161398422 384084305 305759623 984593258 436952296 548860855 611168065 463754053 146434046 415434008 664437138 579339464 135818451 428536531 694296832 383475589 914134378 978169000 222883084 494508339 323172627 780188662 207470161 506298369 61751193 231931574 277228374 948368061 504517584 881306996 261413794 141933391 826844559 884982322 2716607 197013968 594217837 568613335 206083587 931015243 608112060 564493169 852504049 211628511 395476023 264953953 474772472 678570759 971126976 747039648 388698862 591752235 608068162 281425787 309646950 186770804 793189501 654646622 409284176 229331253 846492755 162778962 536179842 131141281 84932582 738844577 319979872 711911560 248051204 927474508 646445661 261712597 830086461 589454584 965376583 919616292 898502380 223505513 480070326 453968934 366381354 965817605 359026065 954882388 962438691 511586150 669603619 448668873 389023453 944826861 677079696 599456637 270709021 246941335 355726391 517326693 691369889 572553026 256573030 552291855 247820257 405679246 168195202 146420482 402770413 868056223 436973250 112328047 957846265 139468163 264859902 149248171 41902803 39410509 501589698 857731849 95553384 891708393 277955774 122563611 571207039 461568755 236872846 393184627 398832384 126153885 930522844 864392663 60717862 864067470 437446847 740818364 639428957 166565804 582695439 263629644 660418298 192304229 45760566 832468557 249758664 467618603 33325868 150446234 657529231 10095177 420729932 278510614 583027748 974130561 469889323 31690865 965314650 911451527 136062946 57940417 540181843 671770252 434564395 349696933 433467269 455498434 86922347 221138803 547184850 338525855 754348400 308106136 657604109 708900275 232054802 871253587 218481939 409316580 847107295 816221103 894459226 11549237 838719340 787697677 54821630 525953808 271556172 833728905 381104263 224040634 93628582 376742896 441532789 697708583 472485833 848420394 411878619 478316576 843883379 846360036 488943061 548319337 747400354 991371024 722824928 904711176 225819018 385627908 586927807 955482638 53410713 765341816 498774523 525502723 117956326 991043207 2250394 694983328 378715850 194606887 963147007 114036757 683486573 262115764 349445640 735502231 714141189 550446822 559235550 397151334 659750016 758429525 118238150 23787426 470040103 813575076 788472299 748267985 383849884 180202707 955441437 389023141 598565460 37600182 942016643 11787738 571093396 996267872 210224476 488196658 261393643 372024761 580047355 196172090 829378325 807192246 195003845 705752722 545157691 1556198 350433530 771226668 828459368 111482745 765331305 948632685 40851556 332736083 212125233 451102778 598818788 4980904 842913504 824392690 622828864 308168249 924508829 556446875 472160524 926600795 744338584 156222385 337938283 867329614 74707732 500238927 754836834 924456179 317452173 822355048 445348056 442980032 264433264 88711774 312189891 30197454 785648000 874230814 43529718 474284925 45929796 663694908 627232012 881648417 49915100 304658992 651847394 895763019 154908890 27532443 466281965 279925681 608553200 811766401 217021847 853220315 608836622 944835395 98876995 303011272 548494099 780235583 606147326 985130304 5479032 527006015 990633404 252596295 96445194 38962314 450229140 759653065 155084208 138845391 42617590 386942606 501562027 309277884 596152623 416850677 239110207 905998991 670132126 425947762 757884825 912744312 885264386 805400858 518276538 288378331 534664184 318089020 438818540 369844225 539925047 605647199 28830739 674062520 580667791 972229838 642299933 926516057 998079344 611871726 277206314 46238775 929863661 545307621 870194819 403640225 428649272 544778727 790207523 40176376 538226018 995762210 109140463 56958376 68301243 272679934 257403801 72124030 298264292 547611110 475460377 351818294 432329100 375299842 226448620 789167520 660945175 904020115 978011395 165696985 610265666 278976942 59239612 472728621 363360537 112881669 299303105 386538083 158443703 302088046 138390160 921976341 226389601 198534121 575330889 721211400 257112741 215893209 969518513 625658380 101606989 581990732 248080989 458724296 345877170 816907307 85467811 222717193 815975050 477280228 287953977 982417600 410230333 183261787 987481513 545432454 866137254 293105785 299323368 123806063 18868363 851592983 76144413 577678844 629416354 578829259 648265253 545334740 435141818 184468106 185865222 568633164 550424218 91389010 881680637 682641870 885415577 51457173 186263690 189151120 168602397 294217802 263143811 278931221 302582457 812102294 127853970 287750640 748982228 73957901 590445211 67982692 676284553 149413522 104330392 394191903 276068650 196814233 290111656 235022365 119611197 183975658 487893478 298735396 287310467 504858730 516761600 971347077 60915138 791990444 706350738 172520703 851383664 802850687 590173296 710093035 141476679 905798411 602577505 434706734 119949454 867098687 125527243 698090250 633218941 273092583 99546320 389776154 78888816 838478595 280872364 807712286 73613579 245505968 868694171 836273889 584215287 945757075 437546774 877769458 444770766 381288023 793238602 541161798 683086297 845960641 387127981 716400428 723260787 709104934 977577435 285251465 18092133 610801887 925943534 54461117 220168687 297147394 850294291 202788860 883804780 387014570 865009653 738229583 808570126 260541133 220247559 178915091 60671654 842035679 236719281 915097966 618312108 446216594 755234957 244497774 439553570 252365895 964592039 416179887 971800128 802442933 930216580 561481679 515563464 577335949 80205028 978157314 531482617 77675197 444764480 475013394 419757841 479402293 848398787 553973977 398811910 167940241 98623964 168922142 966995084 415448560 951687722 606217251 813835699 302802523 942739346 497519206 212875758 986757277 448300366 30431021 14791085 465867287 653025407 473904693 765849460 691806384 709956481 266400116 212815093 799934072 85529444 400993415 778904625 95162396 128342808 630060501 686642209 26393142 876078120 716802192 854222071 12140303 182665583 596670202 926031467 870891980 820149000 698408426 323151333 624343756 252060381 431791123 806630555 336195516 443010594 370295521 509704162 375026420 29923606 529883626 846435193 143330077 834871312 881881936 697917118 625875546 567462948 374436225 780111846 982212168 81414756 872527539 583281942 606816188 273048221 371748814 799518454 369093855 770923786 66706726 253158581 342520974 491396869 245684228 945738870 608551124 2314289 720163481 820625803 292424811 685765283 546147502 524875612 787079642 460483687 641903813 9134728 743661312 766212666 218079694 209083723 635049889 807797139 273784314 465148290 230750584 693931047 270937279 38509067 366525515 410878556 470940415 731097936 229261437 939644043 349963499 221000783 896496719 262014470 134626905 655170407 215724065 206978152 60692697 352972311 708881131 657287131 529410715 181222780 474320342 472470838 34415177 697210749 961342663 394744607 844077369 142221031 820374105 901578956 875217479 72535677 777025159 698648648 139437570 490491136 971492432 855156131 933718474 29657692 696077116 402088710 292010679 555341300 1111108 443749806 485861767 812771816 594803473 690458226 993981321 869311591 132915041 289848809 88820093 686221099 426318441 153303708 750956215 980174915 340070329 986821536 662360258 233688393 889438386 445558141 793161996 381847898 101595862 305304160 446075321 925990701 37992656 757461641 168638326 759585887 770711021 923768211 174093128 615564287 558814052 72839920 614978491 186206225 156636342 273697368 914822167 181742490 58501855 46822505 919234590 364867833 113799393 192501848 900869982 387575698 367890929 367095782 789840792 289075351 394237637 695079916 733156486 423562805 852390756 556903805 525438881 485367361 402139572 28381194 394632644 353874206 56591762 835468827 14815712 884791225 743570142 29520955 415399482 874637515 151092769 96191689 871536993 617143578 637771726 987700403 474504444 984272380 356984990 724635109 344746327 662661176 371420286 218300361 886554337 708029707 378604122 792450663 19316434 488308875 144933691 804703083 346208237 844943035 166352202 432886795 822981456 962898071 998731610 677151214 334163019 441841484 485186348 304176893 47618173 210614647 194464114 545373045 229060507 628616855 387482919 375847086 826416610 738760259 399210268 705022212 741428611 445960041 528589885 625750379 663649206 445631671 197223780 77689218 38811804 751638239 246670457 872611306 101232663 263396809 702668187 675382739 569225526 176645405 793688451 149518177 402596398 238475380 260492167 602127103 861040859 338367726 565530527 159804927 472898798 130010285 891343745 865614607 347812567 26231651 408902202