1000 487
662518939 604995512 370723442 503598445 255864878 322154146 538490021 104181977 699929955 606060786 153261639 775041778 724547786 362521440 841013850 217766712 314089721 355464402 268346645 410812346 571180836 838360555 492946723 310281462 531076814 890915751 28139104 968840708 582612753 892550738 775216197 567915466 494395114 522875118 701779145 389774504 687925140 228613800 274793339 684327068 603210818 760398364 777597366 534674958 530713556 952575145 549157228 773787279 110906124 83384162 820192339 250791940 850381015 946024661 948060997 420462567 306691513 481841683 198410546 757440075 448782793 647663337 276367246 487952908 715827784 548205704 371454438 367415831 198072883 44738911 164591362 241401177 888555107 3274775 567862857 779222446 612646511 869252102 302567638 870192589 560567330 817688122 457743663 250563622 218107034 731261741 922731245 298449300 200922205 635887198 415473714 611335466 245525855 850718911 503096383 49906578 319414081 895737250 240128418 173436625 960807536 930600263 302620664 454919536 461962204 647495858 352890600 42887645 287416133 339228526 709892740 75738124 221738588 982645732 88653445 390555969 451751643 787780851 430753477 122199975 208169465 193126089 816935332 998336512 994058635 537270687 328482368 154550797 59261800 495081400 303333963 476325297 859083026 497240360 342718580 967977822 7921321 95567980 886430094 764379306 952411765 374196526 145252101 939582425 332344919 632286962 241775417 649542554 167493183 771390506 66434907 424806288 417876741 578037734 612098356 697338913 309192532 573732574 975076229 151884925 24380665 703371628 360528790 313191055 90920735 98278747 569695523 109101094 548812191 138027664 786599839 316181620 144378442 241125861 448417400 168201750 722409065 844929016 953227277 337092864 318178382 99934216 559445893 994272818 461654706 557991174 641382852 461347615 709284265 204696946 552449077 890556446 995526422 617314657 388670003 175463103 876466319 18295534 152109222 285093429 555749056 909698017 639580901 80111359 423581306 183494357 683089695 513259169 208825014 733321801 668162535 595493209 211478919 587750758 730490548 268423379 578381340 683705417 721230726 954197107 885410487 484663166 495663776 177604892 136829600 530798632 427456348 309537211 342599102 887304579 376048231 482068109 952377693 419543690 718212034 869206930 286089533 581681790 729331935 155587158 897580397 792573608 882528784 399124564 84319610 944673388 640843737 526963358 501865427 76053466 627365254 732558951 843795519 803209087 854022524 750913733 326770662 817142360 520388645 678700557 3014312 359795455 719285400 573219098 98787524 67952075 855995465 637846061 856620278 53912451 461385290 245586263 563298895 397896928 538316214 265137651 138574053 971535579 449361462 159826945 762650250 705237880 166676157 292957760 983477051 779674173 519785522 331837868 731699782 841736208 593260605 293743207 130959134 812338574 916996476 999935452 783486117 29722320 608852316 927914482 633852770 701006268 427662889 528256608 788238743 656318351 878851481 996192135 217200462 635889854 814176934 566622235 446998048 303034758 561966420 142006573 591239263 823997906 1777956 891781538 339793894 854863041 311512442 638733301 304284905 164941642 501720532 22421841 450130837 388891050 587093776 904257149 885774804 349534749 689808663 298614833 801797547 71811132 157139647 581801169 624884458 40840961 385911947 499658193 282852403 4512163 693781610 438286311 168555095 834231908 588173065 155147030 480969542 340738240 144687795 180633520 525022095 843405548 606530322 444113458 331013902 509998810 392980915 735385627 565495786 891780108 919830910 755663428 509761099 283099141 679856453 963089592 392103403 231147041 933445040 148047508 296925273 715016037 718887559 946963989 980162260 607871937 635364488 971454855 345715472 540008044 382475658 392216914 49030836 698883913 58138552 208009517 834619386 753002973 677667803 298245335 751088023 677246070 576138834 87596355 872757720 547864276 930048455 303634081 285191020 324932274 576827859 94904423 705790916 345927260 494215655 704885590 637431710 45642220 452423595 545563510 562789902 530852506 861378104 195554122 828474780 936730134 407697624 533950461 886377676 959500124 170545084 898693399 168502933 572959529 688970004 205356690 847309731 750892661 229285251 537052383 196626422 843708057 964279449 660749898 239637670 318304245 474322003 797183486 913879415 518927613 994556917 914672300 396804255 327102201 411003856 259552390 403557063 895591058 958674758 511885216 149425987 310230643 817980907 219160855 227988283 781571599 329108078 469903865 879401114 817417444 516353029 377536308 943988207 231749025 5780265 145448661 635011180 195608902 129293800 5646584 236909997 830847494 71591132 856450319 649056871 824548063 122055059 848744675 61392368 709008664 935727178 738924307 994069097 492578426 536013788 94618439 742533384 722059835 777393857 666888109 546465892 905403121 527103424 890022839 396330568 134361052 186520894 132882595 397253327 814486235 364926902 881556327 261670085 745836891 592135274 219861575 848671041 41161172 135733418 525739526 447623977 84733038 920645074 400194882 590241900 439478170 491080266 90601499 485439961 234657534 135389208 929904178 399453056 621408089 812514968 211048213 591847336 671531803 258548178 992498074 789933039 194280110 975330071 160370200 628870193 690109287 380836138 770057118 779979379 824844144 432478604 602895120 883737571 808931556 589230471 768947966 407947761 701002963 295548229 723559495 112350865 175547965 229655863 801301559 49403218 514326193 346879456 283741748 644176143 582604399 924283582 173609700 905406394 910340223 883933878 503594854 454325969 748068797 833767627 952516076 524573419 969097089 856985523 462999421 270796785 834363442 789836653 384798809 507720815 283295867 363767700 254481039 499081938 958138942 84430442 718313604 428799454 110366970 56291375 544725491 291810528 621066766 784186347 249259941 302659648 560330525 336680311 721623128 279897921 616239289 643403755 955462154 259496074 494923393 190293749 356985988 429682140 733018714 252419898 259564370 463187917 899351963 498343052 970303173 977469282 543964626 294357938 137459149 914352544 128781461 234723382 753403622 35854945 886904769 266346935 273593895 852925570 530719619 426924297 946210716 13614093 367344285 947018851 292298244 85774789 346817519 666357729 335719256 572763287 557551557 557401127 138533159 279994642 812380348 879654223 920740624 148314718 643384773 125268197 788987735 809978158 959800595 342472139 704725378 220011389 264836334 532437460 795522823 634690710 896311499 865465375 299301665 94216187 989387330 840382054 940109636 165049197 316000380 125761056 159707539 327825384 935724908 687609120 748351218 290529741 745287487 258940382 926360243 589953530 450817698 245318333 551281324 89857842 972136538 580002466 730175048 308520157 728573361 479555293 474704781 910514155 49347911 217678753 883183773 328086767 877709319 196241877 348364957 69695994 455203512 493335766 815359434 153016892 649841196 302332997 970396602 296563054 925287173 319581981 863897539 338571665 842420292 423168731 523563384 302430724 587175162 122163483 851958815 166056550 999199301 756030772 165820739 16595978 348934336 532634939 343181506 837049477 232878729 400137379 129973949 932034932 559171377 182445820 879622401 274408024 262695836 269885266 320442898 890171259 155043625 696883512 792753662 336953718 241687198 479439540 33846574 623570411 772684803 61349082 625088001 861435387 325391744 723826911 611145714 333823776 378604471 772126737 859429775 873683924 850534773 418408447 663266414 265981235 322266728 268341439 593925562 597115856 589865599 875851663 603956183 479436484 213141664 762431159 897455629 284824816 965386512 771248686 56292751 69705356 562090015 754826376 728186979 93497893 729625836 300365660 271598338 658808067 421711238 172789938 43102168 660473127 71179950 950672356 372674786 339294836 834658332 392960911 75246259 312654437 131250917 663645866 788979511 976564434 696545441 25676985 791363979 689486365 838594029 238797579 816937630 499434219 412995313 918566979 569082497 485089847 354468119 842419337 43273016 158336622 845692199 350778815 46115575 723695107 356858911 418842588 245251712 889663562 524969865 138081454 680834781 909508692 560412080 640133064 29939486 400518534 466528862 955683923 231886728 338069825 420525078 750242707 741912367 749095944 425001894 92582418 686285415 975985165 485061145 239690178 977396914 38762628 104139404 99890935 797757297 893012891 409969215 650087816 9347219 437074081 551335243 607630128 904091784 59433893 667128959 816307487 920777169 600028663 545106139 26031666 382920731 227991047 296000729 311919722 918107606 793091285 102749025 350768617 478808402 754689558 164655612 23671767 930123310 139318161 455830365 985199682 643478809 275376764 802221341 926392343 687629054 160568088 133031923 450877611 155422299 336842044 932095887 689615490 164895748 738681574 520938260 362572743 532155974 956936097 885367286 833980084 117323497 681967152 975722098 690283165 112432094 584209260 649014974 594165436 220948411 737380159 426003881 312517287 798551919 358360531 247371753 153214243 144469095 899551614 498357883 711179477 510278872 587160347 950993857 301990626 837183083 733147539 536167690 301177057 708944776 163426666 144037979 241050594 658690869 813687062 952845947 368702131 880163107 630998785 97398857 224102275 195519664 681554352 460006055 265399614 137846217 136902524 356101298 738488584 499886197 214544629 715695945 900560600 340029863 240345110 636988777 507629440 390923472 453669062 548186269 988355562 435587699 737016071 118009606 953072779 948106276 842520990 274262171 937441052 60162459 119907832 476451555 999032290 962278351 954702556 251694521 700471677 632253267 251439174 747566629 690903150 173374056 828627268 694148300 777024311 868623188 299343796 539057928 201734589 46839196