1000
305 969 996382367 527666427 487 674884174 614 253 219662038 812457289 988455957 376 625066834 436 570833213 617 466966815 578583445 676 400832393 591 649480468 200999001 764183368 160086861 556 182 515360430 573527167 980086661 216 325 840087055 125 812 736310306 892803611 255138352 41 985147152 888833706 554 260555821 887715569 132815693 487268895 125451635 925904765 557 706732145 687 271952672 757 740 433 158 69 732 186929055 434968628 433 205 194611832 348480348 209813508 320171561 471 803 345504310 522796018 514477904 995 383 329736295 548 178 156 411318490 380 946 40 622 245201143 522 249 531 837 445 781 507001697 133716455 401239628 924 456 243466208 918 301 975069691 111 231290925 839 601244120 520 272 728 152 624019190 14 106642563 605543845 863205521 22 728808188 273 807252740 561895641 387 49 259 931 381054202 569 475799571 211 475 796252511 416998879 855859053 717 488598748 806841418 983 422690167 454 752 209823994 412546699 586052550 728026237 968826775 842 108 842999449 464662912 852 334 526 833 363390634 51 693 218098041 804717367 761 763 352378742 814 444115615 282252484 821 539 745 532000445 110 327141716 981275071 616 225219790 98 572 667 343733238 864184891 468 963 789 741 395431021 597038803 908126632 665230510 616518069 528 322212537 284 443 181 470360803 801927622 496 737943812 524269636 771 393483235 536367335 206 497 487929006 616 160 221200124 188 909 306 592 267850544 905 304 606212164 627747799 910779546 907720935 192 187 541 522 192235445 400 117 456236492 642 481995841 284 865 488524169 175 653 628 294260178 121 739 742 706 190 108 546 511383234 482590894 941332174 48 281 506 572833433 489331286 301835992 652 686903761 187380124 263316530 19 797582776 891736777 953 516 66 172491540 427 649776468 776332565 204126627 930274532 401 441321487 670 641340152 881298651 418420681 659 437 343520918 469927451 793279016 454530827 950417418 927216639 742274589 644 290 625 456 280491294 731 702331649 192 301 236257239 940108457 67 565 592763673 339 47 522811997 285232933 668569149 632640340 960885310 73 352 183 148 413099077 605357318 481991205 344278541 227845667 372 569896671 493612389 358030811 418 539296250 262 61 589533733 968 906 183 394 792571123 227084434 899123321 943 192850174 841501755 320793480 953 260839527 949 956 589071317 755995159 588 539008689 911 130628974 124548835 454618365 137381905 164 954 853 780047616 481 210623965 224 495 838694022 536159032 57 811 996631155 699233494 567396012 187 849130400 732 839 692508305 963395755 611846809 927051867 666 398 901290297 974 124 700813705 233403147 564933185 548698668 542005901 71 247872421 882 490902287 701137921 531984249 605 258 147 953201902 819142125 361 336 852475996 576015010 285763521 322 813 31 629 521533524 424386496 725 606698386 676997253 466197038 197 72 243419315 455 950548138 575989809 449 136 952 613 513 583482264 862448756 350045085 36 382732430 120 151629212 392 112848061 271006969 380708071 471484530 252208131 549 237 88 855 896157923 999 465213444 795697906 970 565 639047806 672 357 159063255 172863540 881211279 519 664 322183582 125666808 489966879 618 494 209816420 794209680 565 848 194736584 674082777 471012849 272 79 445 35 486 408782539 434 318224048 611 44 15 918605659 862444542 315805800 93 935 221575774 531 618285222 239346250 827 945722226 647 927945360 903778851 235595937 143427028 796486981 800 941802231 909636255 413834801 113 634967795 137 184 576773722 354413004 696863405 480 252 260 413 528 504 534011367 804 101649651 844810183 900161981 858 135394619 748 857 918 912 930570479 898500119 879070461 771 146759290 42 336217793 746 367639225 793558449 159 172 376 333802707 378556632 929699077 114 958 281 948 973 788 310862555 833604243 489 601 340678217 40 407457333 232 297470688 993 226 115261626 146489301 934819888 533333396 450158559 200691489 460 816409601 834478562 865 172 327797575 15 477578699 666290848 25 415943234 376940179 112 230712201 562888548 480565247 222 476885250 668143024 528 121044780 472 672139894 652671345 900777463 141282949 309588718 754036857 953694034 517987862 349 878949878 197991999 646 755 6 326141576 895616955 206 16 433 525168253 709 755397932 360 884708314 626280211 211 905168997 408 745 823347519 907363703 263957888 126 665 682 592037450 90 714096600 499 275 678 29 836 409135178 320 681725681 324 319857983 760112101 232665816 906607228 592715769 689639090 759683967 263531199 686964930 403770774 892002469 195 802 997063884 648 251903753 982848386 305 279547140 68 903526347 961673625 665 108 697553853 248679466 828445921 413547896 164214287 602943558 971057919 681 603997646 687 932 961 591289347 752921264 639472824 355358729 316442333 618 297 416491499 713756306 818 199977851 168 344314792 988389285 755474238 246 111 230 820 358 774228451 186 823771405 269 642 688597427 913 807 174 29 392539154 510420981 975235595 715 759 891076845 181613400 618758301 233149475 882971549 397 373 661 850367972 211939039 604285346 712769113 495315710 198 326258311 750075449 720290272 730 231630286 914759034 98 979 60 699 771 937 126500780 304768744 497 895233990 507446844 685173423 407210007 356409693 233585598 192 30 749526294 326714505 250 316 860 790 549 281 978259831 580812577 383 18 726548558 441 858 951 554 808 735 313037594 704 941 875057612 597 383505614 664 179034959 849 519171984 624 424 289 781014757 376094581 924 367 770 625917363 500 217 258318882 578 273 443540764 134 954929197 661402724 410 916 267885124 363851381 133089860 788 166899186 632 567151010 793 892 717570868 935062629 139732748 694 407 657 570214045 682830530 799804757 368058145 387789353 41 477313994 315785128 293962267 276643183 979 342 634615096 978 50 786379228 819397542 853396407 74 316 587 771892209 123844748 677 940 408156857 315945169 724 899 745 661693765 616 686 886623406 819 760987402 245 87 769033398 957618586 577741725 168173035 735 561 450 620 337 200504541 635225763 814 694277954 847739445 454189626 114617366 648037496 891 492480018 369665011 403 248 771 858956563 10 697 394688485 494 260736731 743125610 5 866 856931067 971523937 328 601489367 684 686247503 637 291249963 849476593 416 555025258 195763403 210772984 211857474 30 293 704 193 441093973 803213833 399290819 646 386153697 731866942 511660534 146590648 736 520523562 463035455 719971228 91 379622232 629 621238600 557440923 724 839682994 668 590 910 944 859 72 747 586835852 350551271 464 966839422 463 175132387 737735679 891 401436291 621140396 589 388 827739572 639 939 368 892767454 483 113340378 247 740 599 926744043 591642780 822 986433452 866849164 492 355 777 272501082 284527509 164624331 163653949 489855832 418 894155249 259 701 312 773 33 42 490 314908721 206 172 697 621 579 869 459212431 704627362 275 386377199 939379451 904039127 892 204 654306158 954 844533197 734 7 624 193979668 497093031 891768484 299010105 869 394 879181369 410 726637105 704266602 604558964 639850557 556777020 420 559693528 406514209 377 861874371 297935596 253 449 370229339 574 298442411 581 893 266712924 74 161 736495330 336859183 423781357 274787856