1000
262358769 625124334 922474305 731103899 928407104 510187725 613252464 607885213 832427988 355228417 687988954 453598912 608523987 606170486 145568612 124380448 813046667 205761331 459264228 781866966 547153161 427257994 287554048 25541681 961082823 264898779 709463348 400996246 226049409 642142976 969656818 352428072 660167256 708218327 261756400 905790579 242179148 97974074 985276036 507258199 909220748 633595848 720536409 451774061 692764353 157488608 743773984 453068811 311914891 717318961 251378261 789080552 194792433 962896117 799680116 400311736 247768396 498945828 63582584 490849271 210873324 263428507 244413256 866776599 9098938 963750851 630136458 686639922 454236962 8822994 832344009 314906984 599230314 404634924 925872090 221833951 345009444 948944117 121046182 405144667 224328894 645598007 955358259 619942829 949155527 549081724 500052708 606284586 128653772 779158501 26108545 721063081 268750163 197070578 899717712 350085746 670235365 611720181 945182773 299523594 780026470 680483667 154858994 85020892 86309861 185695335 333524934 197311112 667183996 38776595 213465926 472190200 8363568 559460727 956429389 949081285 627520659 317886353 70766636 42216567 462115828 668399019 839968818 407996352 163955072 91720505 704411765 241220292 688211151 801509328 908566765 138547082 894814926 72165835 902359144 196101874 781194437 8561520 494930716 107707890 436795081 753875936 30342205 664750474 486065577 778874223 534455247 528480560 669787128 171360493 336114616 835353306 420500920 910669568 166225535 7966265 32381605 279813037 149420967 59669254 389297435 132856738 954801780 410491812 167508892 476306373 195641634 279307013 49539045 152467861 615243064 87000162 191147681 816057862 369774450 481611217 293606433 774342724 430274256 494753587 516750777 775946802 587928361 386702393 809287994 467949056 654276979 131453290 288945150 552233574 384105447 311040734 569605725 848641905 689281693 318965189 649345235 632396126 829603779 503568161 399871440 76971423 290532218 615879572 704133661 165501434 985356110 36507219 282232294 366439377 234410831 800820026 291658960 27113978 587663416 128060882 835980988 571411565 745817645 594958279 967962512 810335242 783149803 948175919 4123384 140152948 875370765 916856225 101448970 945043245 437257847 595878681 122427495 193451796 701432049 706288695 577325819 69676602 478855499 777655667 33170425 394524417 267160779 304037953 28549906 160891784 776064533 789594387 77431386 313039036 292293232 307359550 625466690 999687866 909501850 668931415 670707458 400728817 368835085 562075617 877492004 842224851 465836832 59557413 445570701 683875074 927189516 570810386 546591519 731715287 921560161 84421792 870646501 87903851 785760211 30664509 341259654 417192468 729082463 230268731 493064681 739238491 335933885 318614360 910861301 564966805 378673138 564455025 152498976 788063489 750245281 801170699 881913916 296888769 670479619 260393076 876840579 310550986 994155106 512515752 59534342 697413257 693008017 42607947 830599942 723645812 989297711 713437004 238222723 264513522 867552037 317097676 920792863 686427134 611907528 818575090 211952280 983541842 849977887 389226727 513001040 854194018 512539721 227042189 517860986 388383773 544994295 184835822 707902575 430157825 581723119 652769254 843545429 456948712 697992957 607886822 289404284 281538724 653840301 163031691 596557325 753144297 619914847 397559124 153737928 248576919 647218767 908178453 759926479 686858998 467208623 596198644 313895519 176142904 413281009 559580577 314370199 435359522 556307506 259483259 684508655 752886826 715709204 522054070 126154326 934627608 7545641 977753769 311394726 547487122 474210482 322219113 180744505 282896962 449559556 316511893 658072230 539561473 930314839 458771315 505213516 422285197 900902333 684166055 925087098 935506484 372954501 882073642 759742202 384976466 592521248 54594584 483559952 333618277 445502414 306093470 948237578 104319482 126385702 821229463 312059028 721915867 903945456 853591855 758156449 980485391 678972823 99764406 431749188 715240879 726883883 887988440 103159133 188386677 145351868 979899836 69469516 337110229 815890378 313028563 930567338 321805143 512223732 410117680 359804799 81642394 386430958 952643131 568554401 65985917 104255945 48845459 642620608 477182194 421432008 222037399 18565016 925007811 680651288 807964665 148507576 284649378 52745205 738944591 254615238 233475915 627128769 508894908 376599526 269590837 881528119 941079357 244227382 465006777 97836690 370435953 500763694 825203909 326227398 789110707 417209911 270157958 641106267 451345228 871044999 743044378 890617868 380181609 278787714 110552426 910096334 438697671 199049047 513508208 612624211 104400408 46434990 69544019 295911826 288253249 271802189 470505496 91615909 458365449 624321046 460545177 463924163 187033787 953275058 386460120 782059908 548859427 963966221 523527315 471044554 532012273 40220820 41147307 160822894 889812290 937173942 358995709 843950288 307557206 680263231 564490294 65026741 462649933 102013538 211644571 682674199 493250515 531807251 535004847 868309548 450987790 332801409 438530418 559375488 822841659 56706108 424938272 935430264 833391929 355156346 917082985 121319211 205341938 193197050 330681363 104015274 508044783 84481483 292943593 598032334 294525044 628911538 652430455 997363306 60025077 678107812 754674189 544503877 970948421 985437874 742046981 371482138 572774085 38506166 653336266 267966419 64910138 771393210 838864653 213906925 476642019 365140295 357647502 566361028 780972923 226651966 454488934 328276527 853958042 397440804 371130785 741998316 842663663 380117692 767450789 548270753 13913392 149616431 442657361 329965468 395272738 944631013 669784042 676964137 355091697 409645975 357864442 571217232 657750364 33334294 274894978 623856497 505864270 457699043 346883811 340032924 469768521 292184821 204202908 128365157 269923088 192591671 926394234 360000482 772774944 716038700 365211455 761656468 466550208 396211130 221903589 652712306 518429129 87140821 926920454 617636938 642140972 694203012 985410603 346209068 219453575 804766635 44918437 341583772 735959871 483605161 208705451 69018273 310710565 171879350 960732693 59931333 605951845 690325172 797745226 890580553 151200844 809663826 860315921 196224692 522630882 228663240 167462042 126874742 54353462 299631939 766416277 62091487 834774511 118930907 613795074 621514046 471602225 936210819 705661000 659256481 601076151 583806056 325779257 536192512 979451972 443721872 9306542 514424999 515400346 365950503 870840272 24468356 274666482 282361558 530870718 497437788 967377509 175180347 135891842 391923720 247390196 752284613 807054030 24760608 34825719 252604241 656226024 225067102 186905152 218471610 299121050 898495763 618068019 998994950 275844475 443253606 391950262 839810753 790409244 648874150 600104273 913362700 197896793 177649034 348859576 117346392 825032691 788347376 447960836 189787763 81070543 72909322 898526254 983173636 74498449 393422542 822323354 776560687 88082669 149025268 449053906 111966129 449605770 317018734 326457512 2662770 656878874 692279198 47985356 346342032 461768138 269297680 659112344 831097361 420531020 523227503 389674 10841723 460257012 712175693 303302987 699904819 630977482 542903619 121322365 13528004 318731930 390749847 151926876 564159131 433133352 202360455 322998816 643524443 737758337 368003125 236501823 628154590 488077933 482812206 465263305 667382273 64724888 88404809 36910795 405797201 764791032 446593737 310586226 265587778 784661918 295295730 113706154 891824764 306110637 72664655 211241938 780749439 260303891 527828348 847359949 311345505 332763810 133966017 434056773 479591567 945760809 891622544 484967344 764497768 875794097 388176005 376380048 630995241 199059910 553288448 906947654 81572076 451987900 373899183 403423943 718729450 954250337 322631875 853978840 72972897 594401458 530946540 778198404 193430964 647485555 194555701 759474424 428245573 15054546 619271060 581713094 369839383 431095642 368381031 586555401 914001551 486493568 173720176 774193147 806242821 78529149 760442216 379270710 988127855 127338696 404325306 952629881 63328745 513685226 204131013 75329441 13090395 720367934 118103313 477794035 709686264 591426376 724211613 184242185 844278240 628732080 272049748 164096344 305763045 527418842 890208602 665356395 628263971 22638353 817900636 827702121 421996872 448023270 625030028 9013015 569410252 338988738 443202170 768459292 782971951 657524395 330548531 610245831 241844025 831978131 100393876 692011409 255857465 628884113 119996918 902342503 318357628 994978918 892424435 132401987 909269212 839130538 866231112 267199846 982546800 852185752 514086358 321066548 749976929 633576307 449775555 515174571 727887836 858418835 931493566 991186561 416299279 763861343 551294938 604989631 537802248 882640300 522067619 875786960 736707216 854688184 430783374 917040694 411297893 888476330 299953574 751754315 539389854 664977230 518577955 622019761 184552834 853870481 357923512 930903129 636296493 338656991 489120408 519958063 143637541 908445442 241527553 754673612 928230503 355412166 87565987 924337938 579419494 504663738 343070665 101944568 781542320 419534524 207684640 185252131 25747328 4779037 271749782 369154334 304862833 651560048 8309086 874357558 99810381 896144628 345886224 760318709 857672452 968020123 589403628 301954361 424609462 56676927 368737263 221147381 472189504 301774558 597628273 58851838 407055812 238802127 491243898 466907458 752957931 617855240 44430786 89080302 966144678 130123599 237975196 6900032 494746342 493187369 254137680 116985197 596399954 734645668 463832251 162861727 591759282 164341857 220124769 856029499 552862618 244333358 739802603 332522688 910171222 981868957 482346592 728132461 55965415 374945920 83728312 678730139 279819379 275963135 222027160 723498823 41123619 157958076 333122596 975010381