1000 496168721
979342348 590807693 342212763 404958593 452992962 549253121 413473863 274109548 443138125 757100987 928475416 203253728 558320540 130733101 746407838 889067454 771751563 185055060 291893725 341026563 169911433 850640220 395581337 197876252 308368432 192562113 35050941 249497021 268259189 575413923 780891252 866471763 219590181 797347578 648400546 278041344 799619617 242669887 994454855 392379268 801209909 921493901 998432246 348538762 936224207 852010442 26789742 430677740 428176459 508542632 989624660 155585322 906175397 868966247 918542434 359311349 272928552 417429716 483649712 16862502 216410042 238146233 377640231 663318459 538770414 349257914 462351205 594142061 484536939 728426211 954286097 12275980 326644738 65114500 712638536 490700333 151325592 81888284 589478192 137051241 615118293 61288332 607135410 953216245 701104150 109738217 354048119 410486854 118738666 558269236 817429602 360378333 823357273 859961934 269659720 712172161 584334543 408974680 371854011 792679312 967834640 584348106 637437664 500049866 487867843 260888702 232153894 721000163 922960334 676421591 343032095 843137305 208822925 506232749 963593574 336547314 135108625 342058856 365581998 169940616 512298689 850080099 276785484 814897152 344004415 399679457 936233876 286200454 938757066 984335580 972986381 848564761 764627029 390684400 551097552 394477014 402669633 48652739 371645462 514169470 394222259 768310986 490310543 748887998 272705525 349129019 712405066 837248610 965012762 24767999 420040619 426886862 190257184 634595672 71654560 493086145 281247026 686532422 536937969 582755500 62335557 31430449 269328507 478758231 618196218 917699869 46651983 44064636 187661326 223549302 629166681 963418379 469876451 27208916 881782380 952648733 691485733 30197302 360927035 325933552 643438560 869512206 351262945 645737392 919842087 911627800 423674106 177003138 986429242 316272270 402027908 814947776 378924098 573621158 620760476 220739370 87016991 637665738 823116909 33204956 638871658 155638334 788058261 143541234 795722205 201318907 704028378 755992676 762468302 434893026 132430433 858727901 7495669 571512921 848641386 664125865 48462492 857087713 778313256 301569565 833495745 198481127 783376577 227938868 655802475 308697221 238805259 452643335 617802961 797418482 675052688 154334649 867163946 471992222 799638953 264284882 584949748 690000525 727907564 153147744 915667088 324945009 179438180 202169127 285151104 160356339 109827973 519585373 272566719 129697496 232337300 145918643 323744129 972891024 411208220 288133363 596196649 84286565 230355341 325324559 933035025 292596579 21221582 319429942 947642979 119619231 123280087 820755720 928867853 539470498 992907625 979825295 939688334 70988583 995211830 136384930 569729996 205754771 674811999 757014568 454872987 14077682 383650196 234119226 934621908 127343107 290720814 890284787 226459785 101833928 987212147 616459713 124481901 417217082 741618186 160293365 865502858 958321971 82516391 371682766 255584483 529678900 273358811 515103650 920360168 188227099 352903868 602350010 522454201 973470412 415227664 106661297 336529049 912984311 941025381 923982892 19246275 851109062 843447598 50708035 542034294 739869749 553368482 153067373 172110768 442280325 290178627 305544737 316392906 224898925 3229037 370991835 745660112 355915832 543423950 282080570 497531812 708995996 992715804 823806593 306537991 52305278 988723648 795606826 582664244 169170158 626436450 634743492 627527686 764309859 573579882 687896436 738120658 614382446 185346579 668258326 378630220 785791690 633963385 468074812 645789384 769689377 524190656 119132690 333673775 275915421 805237618 832740854 988049687 367240146 435424114 678823663 948154894 499785916 758817703 148505626 607171412 8834662 375717280 968013500 969275942 696197334 545143986 227634396 175576015 229053973 448666857 934383263 187985156 216110662 843155776 573300400 302811702 27864361 739847909 221428103 406993674 179593327 339455180 517505158 762045021 66595747 420895051 910057474 286304505 108298048 999636336 416868682 478783489 25223313 277458467 459110705 683535580 26182096 696324852 644858871 876299641 634644045 94252954 138371712 421869897 119057959 678895123 710786241 323759051 766271334 143453693 767019695 411312394 25887883 416295899 385717763 521125987 91292674 838476678 199727886 470359800 109718219 418546465 101523705 116381960 332555547 155943887 365051093 908101098 228789754 928287057 905731833 970809333 334438782 165894570 602770585 128417795 508590074 473709409 561424881 183463869 853628087 401528008 115527151 21671850 197927760 285064845 150032059 682452876 460061920 241324098 806642077 692224765 831163204 165595045 726202632 226667284 477262118 236845359 929948100 269912017 443479012 289211812 707130888 509336393 36041092 189683664 231245206 779997007 334331438 132901365 537817842 941335319 17978730 651642445 641167712 487840316 631358277 725938632 797184789 352848725 639200481 254613131 602278845 199500765 705672405 274237187 430890011 78536910 159869827 755946512 737961634 544439012 984885622 623953556 281467980 220887915 65260840 101726870 609808961 93426475 103513571 440975868 355732478 675022695 845993800 938048394 941554005 332641844 208205556 152382717 439232428 145190465 35573482 580541946 138535497 24710854 22425572 518775320 860625681 402381685 35693436 381527827 979307005 36925926 420360698 35838034 779734071 297969654 549966378 762742228 983004178 49129175 61027082 735674981 422238329 161424460 62851228 23182683 59849327 590805158 736679256 119453935 725933918 10094058 820649578 792044228 638849523 192729793 18258710 147390676 784983140 380057563 199195422 275153123 407403041 182029891 972181611 729850276 130484818 972851143 22263616 809284117 48212166 192747174 284116528 417861053 317832331 494284312 705645238 304684031 415349008 17379215 812969663 564199218 370337345 864251468 745142156 155593313 110417798 436688368 846668457 517429811 788822592 963233070 513689845 190205324 773310421 72847768 303957130 366187292 276066546 595681116 124746902 265326250 938824671 354270531 868038454 194081303 381044550 875320058 929175999 976636843 794254781 353039810 481270728 311731467 3516083 939207439 171181046 284984258 40604571 871078136 156937523 114679096 718989602 463890538 795882313 375063587 749049994 497864272 486673690 126782146 956102137 143369688 185998272 676753698 414390573 207302570 238239060 63985505 632976930 888585279 691704239 815907674 526431973 439822994 700823556 734674084 398528950 110076471 859772463 202186922 918092332 762202766 680333655 81856300 483597513 198927960 189669984 712177196 340419688 170209139 82486866 150383364 839468923 823887254 338857806 212986772 611391263 581700814 967195319 665275133 987466818 58636815 725369268 21121162 681270309 773050561 971460648 189963455 578316469 174569938 698129168 434932251 430583749 129095316 94280214 731283701 868459823 747273891 237307392 490330215 54271410 904404668 458857404 980508643 303407622 290369574 59793949 93942200 166043444 792443416 179849413 751197862 862008767 67902931 582448412 328788265 837437327 930386840 555853855 101254911 275840670 854511950 100600333 735590439 953731081 909517557 174280215 221013242 707960299 18470775 555715365 678624843 976595823 787679427 950951320 189518175 786942399 644257111 881039603 604785533 959137071 572835999 702518942 76107540 817821914 616631228 454977919 636584023 857822928 105442937 380962549 979367993 296158028 685944696 416233514 276534658 340707207 615643676 211257077 31862077 890093377 618786692 953089474 665553534 251045022 170873517 104211913 648334475 349626204 183871362 893049761 58625724 297031153 413758946 944908317 601269880 940083944 99691182 781834064 97611346 86461570 511178163 743800127 395820829 102874728 172052369 177696995 308176310 473187298 556232193 852221730 386485504 874676228 956875916 878772316 97195563 263185370 873987569 437463878 65100005 316152482 773574819 200902157 534077011 310645814 301016888 814789364 276071617 587108609 684245717 10553444 147324560 403711775 734218365 526261470 259073584 900999780 224753840 20968542 368186820 33239560 65341956 203184700 340391422 350244744 517488865 291408333 272005011 953435884 172435464 596867581 315059705 113705829 991946450 813059955 130184498 306164783 826315921 477322682 779192977 188416571 948010020 188824550 670196218 889794910 514412071 850151760 72493435 717706133 353071849 149012589 754821454 281784378 392633201 547717480 655380287 254326817 40548837 642406075 712001408 353504044 195760162 418265931 801111511 15020315 721099642 611488392 596503882 952371625 688710359 677998845 963633943 650328965 826998279 690860194 362943751 272289103 592389394 701748770 785160922 243382267 892523187 686734450 858733702 190693120 680053200 290311914 133900333 240226142 226900771 213909931 729152234 848515960 40584203 461617311 222708460 347050245 12798601 885974709 935357102 754175338 329694114 132391984 291375298 849042378 98505402 565211434 44659888 361689105 624710920 541834719 844887775 104187822 906925843 550436171 730853665 688689519 835840951 22446832 179726848 768637694 856897343 596030142 824285732 545732790 95531458 119076446 383428630 70724416 113329791 590687890 309207489 847205942 114549437 593803331 536833549 88514057 651953850 386899162 201253438 12443710 855294908 990374609 284636321 176249352 345195434 596710744 227492802 981070863 127833165 109129814 184078126 834362739 174589405 182251758 713452739 784316994 677454032 291030301 871223339 520656921 854396809 35311343 103784850 817287047 165988092 358005662 22043744 608873273 774824206 188669968 421100148 801354401 453601966 786397544 275723605 154064819 664713216 115754809 518982739 860907818 84274990 381256872 268453266 695969739 381515969 579388591 303659216 348709864 966664915 544379945 475381846 659101235 664312020 654733658 758768789 939393686 127892341 94424513 119872448 723331827