1000 841
884146931 846580176 500776311 270735802 627058133 220864067 314551998 677472700 303356107 109308887 130204967 202246364 545400215 889907443 81671267 642391336 446859665 196495296 321724418 684716769 790533339 186688403 381445616 637750413 901495301 216972028 189530426 713644785 930546570 982215211 593286646 491499768 120241604 661835308 502150171 999314708 267918191 401466171 749036495 811403487 651309445 102207139 62736515 11736535 417546218 965710459 887136206 607671580 407826997 369760725 743630559 456591405 113382575 105497130 866916630 28449339 502431760 756571144 947572168 535875684 537321170 899111877 769225682 611629657 972113899 468176594 729347012 596392977 577273332 641332946 366708140 337470766 42525091 630728612 432545714 339332881 412480456 907824436 823062260 222663127 189252705 243742987 742644854 740141926 37563611 777398368 886365327 514778046 667942592 684707366 422443792 335176523 265507724 231283490 184401039 642434037 585645139 525088602 410238673 891770077 743022892 487800669 906774552 108879843 295651547 790841243 649900357 370219529 422722197 251198637 42738994 540260411 615432679 105101967 363702571 53057364 13726047 618131723 472279986 38454512 91668902 603305555 628169663 259119425 526496363 965493975 500348742 514975919 936879210 773872313 880427377 440282807 713933961 940616887 577540716 20590483 252369311 902068353 8162769 100876270 119634743 25476008 320294228 837079375 196727850 512220450 570003828 4431711 534949823 98172156 389791449 133790334 800544530 379551683 731157142 927170848 687882869 394434610 502675249 633704802 43445226 985682558 428027734 317479932 499181834 692400479 447847592 870546854 4474631 230896935 652428861 107789410 257392778 508519569 44658822 940675788 503468606 870211657 920547383 217135842 29440280 945064507 13741591 401149672 587748084 855062477 542986240 106800713 15706351 412568048 103068750 543316727 836394639 600166476 452638441 894241925 124387267 320688815 155920489 132721142 611422737 472734273 328665998 90067454 25705227 843403094 636018496 528346997 32352927 228977500 110279949 130672576 158768247 591081666 143277908 751675049 761562945 387067154 93445458 780614033 148641589 674287126 447015573 49745648 140083691 719653637 746936027 574751997 487745848 918285964 879643403 93556406 38115881 175168758 855198386 664311565 153810950 853350959 925634739 208432456 326041103 948373405 510783034 887397158 23694081 98871772 729138908 945217989 213771291 241364509 916616745 626456682 661787045 695002204 283619150 330468379 260908594 61954769 170479212 677537272 801870504 121860088 438476752 30886424 276945607 747014234 952819513 110823526 802240834 811166866 586303011 989078846 802448657 403683045 120126745 646022465 672163777 929940155 324151575 916896384 687508974 312850771 961657134 27159379 780359591 287746926 565558840 185877717 745533213 355849305 468331668 284095893 279945179 843045823 40634044 524462783 677203049 129394288 142591437 385770209 459347958 665948117 666754539 882984597 891294005 461185710 609363634 918146595 217724674 796325784 474055656 75864085 667620070 812856677 195317529 91510532 732171792 915216203 763824238 717836099 522529361 232990813 858801245 169011359 224739840 459639168 537737496 649689897 894164187 203585569 704151508 957110830 806874319 148873150 222093020 860020344 572780580 261499886 324042716 45570392 658916431 603862943 522609649 435411182 625488804 304459350 617670028 320258905 736435823 678630313 798882288 471534687 61877771 496203650 948376856 52074171 406444914 699605877 170097010 515191986 921980120 795488280 783991418 543122127 420353815 258807157 599914517 126210331 226197264 511878828 413130321 954343479 400939968 181836221 754040436 598681054 431722992 576231781 754871290 276507343 790079429 797791819 385619864 697056008 440063331 510978324 520715994 623601942 3510696 646794763 195054995 959832778 847137147 202692894 760940306 549358241 77151580 842992535 634897669 119473180 20735352 990168017 534203669 759612780 161481634 248529973 853452347 974774622 614815226 228496278 63982261 862970553 641253861 246557689 892198207 818504496 733706408 326712381 115202304 996198750 665093264 814962008 610702685 254663442 631351863 761159499 795162134 573728421 304419144 232470291 355468529 115879450 201816136 444067431 457176084 166811369 409843357 842161179 84101846 321931964 242606520 158450879 119927583 721448090 554508397 242972056 187266522 685109515 325602204 399402831 817053336 389091318 571849222 103874511 519583297 1320093 944362740 946316117 437351394 8469057 883641084 741533339 577854006 682505409 405335482 422443600 346072075 540833263 903377986 432055524 565245356 684195750 251713565 721214771 519468863 281630045 249770894 849420316 240668898 519799239 129141347 844703111 689309249 932012037 781043608 497723694 323611970 762033496 409296648 547139902 793068095 421094025 16303198 391498622 332830956 583445092 307594384 381837052 543451694 795079321 894869240 207326057 40516742 271316677 842771355 537957240 557127809 300318276 587666925 708811083 956965636 533336873 128283108 86917319 276643560 757026366 230051814 219544983 468839953 943705569 579829864 437395378 727862972 739378568 53039207 785549113 426129419 608679470 924274337 240619045 462592778 143668023 817622718 729108301 111979808 248543329 289681667 277487946 735396891 644817087 621354233 985653765 443152666 525678921 668914004 340540196 770968305 34342497 897508708 816271239 440355114 675226750 642609699 742936899 381460284 128652590 927049867 603454756 480683698 132366754 410522998 102644358 939471260 739302115 1961278 801671139 331971090 547693802 838205573 140711286 451448347 749342847 348386390 107035027 587816414 583913389 404675818 733998672 329503612 713538188 265973307 711732070 313045476 37560321 924162028 902299471 959672931 482243202 98830596 138861442 735413880 498354937 657762689 496786295 630968667 709738298 32843351 240270157 273453917 266911430 746102874 78111730 495806832 113541490 23888345 418265557 526515558 537518250 847804879 899785632 878420249 705058600 898625955 990912000 527332382 593577896 466967588 938916271 244344629 854956561 866077575 27676827 799857176 796193404 863574865 223235463 225944960 948300651 97902939 119679078 698445071 205473695 913151176 303365077 916576767 3091626 528631472 13682569 642105217 638317724 112081197 55884094 275287789 101273304 537750975 433554713 880768887 759058831 484139729 352288076 592708243 886417233 55536437 177340836 964653996 224451625 492427228 43838788 160270427 806260581 338970970 767317223 513307340 927893972 138514304 857074913 196646825 6100433 915896906 634485601 872552592 213399454 122302110 56528154 278997900 979891483 635584347 295740269 259753651 438215685 2083878 473075141 701214562 972619711 193078577 496006202 324955546 726143993 283936439 270633483 152369201 559668289 135685105 511651697 144913500 90918542 967491683 860841848 726850884 153639823 940075378 433646860 571539924 909350468 331008760 602680767 163926852 385079756 483356292 790847257 493398516 66145706 777469828 760450225 528439483 864616627 194850344 777516667 814190702 286446383 147916019 340317196 528914006 837111404 42469203 226143303 369180942 537893578 671873173 558869130 138708508 812328629 524879998 16132014 538839168 999897287 909355112 140139998 466629374 356066275 78350887 670733402 145937300 19487853 275608642 495407389 798954018 13223045 255108328 254191720 609429289 919521994 78381694 308595226 202145418 942500587 619142829 388170892 98138754 567762571 715542587 740586471 449100200 833520298 279575255 46036577 873900255 357588799 673158148 64070877 64184381 972653049 670197642 268856524 198379241 417624809 920258915 416049413 153731990 346951417 616689558 128470973 242406510 240373118 942166480 617853812 324467194 794176067 589636558 842890447 129509378 239829895 479372056 190598964 608836288 461863308 770696189 479572583 557067497 364226931 703598856 349495812 859081501 731648545 298556744 979254388 340166937 12881594 29573857 110436654 554261813 239957789 971530923 884404251 736102698 874829525 992585523 406844192 454352081 400762006 747473577 443973196 161208277 37834031 422006462 865308357 643613873 705417678 450312062 321537268 29722187 24042781 316842613 181615343 676067755 322703093 395193725 296000878 448404942 886342798 856179178 795013048 269390831 192871147 615931609 905356237 845770560 548143023 807150630 303267368 238723672 130146890 51089766 941708229 276827793 65826154 176403407 261783877 27710746 838817536 304361647 279004287 520811391 480849497 650318977 784286617 377895230 590998210 204282918 713239949 569306037 312145981 752366309 198484805 694951689 603471853 856984556 167183753 263867023 538978625 503009831 842240472 488437400 600809840 321582583 638322478 686420991 275930914 134234203 990124539 805149132 294101960 36619173 357434044 388179847 385845707 607320341 949947098 424364085 610684545 655692146 60491183 38800613 378645632 867160514 146693787 77657133 138648456 287746318 594789963 293368917 352016519 11813634 540570451 94023877 620658490 851883929 487819882 775814849 215391482 737993485 92445555 689296207 300375014 74530083 538515903 298657439 279353078 6573276 391778119 60521018 905704834 37887601 26334666 198934011 82723489 56283546 820062338 16883789 186102946 244914733 832214216 798853920 624851540 56311007 109416403 984549234 334281445 657583234 961589375 866820882 176630855 660700962 413435938 776873741 307309660 300778856 509815113 257324703 434388554 664424975 931859049 563154351 826116800 505663259 580378693 177255245 333844977 230648523 751129725 549725111 589588470 409918044 162478874 962512293 312042060 552822355 568323264 431711660 699961730 950598853 320504287 91613846 910223982 271781995 408199771 346394436 149172033 853502621 212346280 766411989 198788715 304714180 233804294 872563356 383672525 62556662 464944104 493466940 542275766