1000
879453137 185838081 414652161 655351216 689082501 945254001 862201377 34409655 821918387 563348303 729235218 744189976 958414851 970542881 504881701 643758065 180191961 186373349 784291241 58466451 14467561 825582209 663068801 499011946 767783124 761604161 21303648 308811897 311462913 302267369 619713733 959343809 458398721 848974067 47092361 268044497 16836641 990397001 543523281 56266241 813301409 542220991 709870689 538521285 97784201 846625025 624775611 96908513 532632685 676560785 711197001 257699785 104809425 26766961 955097313 595135005 748340236 758712567 383456221 452913806 416221451 239401645 832014741 282616577 415008750 881027241 687612609 365085841 944411536 30854721 366227721 746924393 150376981 141909297 55119376 514688885 655729679 643762966 671145129 680381991 417101121 236354001 326544465 892002001 574578801 178419951 405670818 347702649 343722508 807584401 609192076 877588663 343893816 938151595 927698393 737920115 867984897 20663601 528278685 657875529 100710121 982496169 21395101 466082501 881853857 247339701 159607055 532430115 841763801 952482741 301126561 322815943 50855911 133105400 103468489 887107545 858911625 426623105 445295593 237300841 279529971 978189574 177978817 616147251 763250307 829553690 681468926 469864969 163275973 878212115 433422407 200054089 225977637 442340561 272486129 377935437 636102769 732154905 525913649 924777833 121097001 485757825 766144561 672377274 719948109 823320824 144773801 309328481 995603087 624808001 79987571 532570845 445060586 575450876 475332097 515898971 354714249 994480001 791657117 229918981 84937345 137783961 347251611 841623477 198909939 666710401 422552975 454367425 772279747 227951681 942391421 734712011 466011201 554696029 510395521 715203601 681054831 155854517 983994801 172637941 513683941 516250777 279457181 700417669 667452758 92956753 511280921 7335197 851211281 732217474 552974135 855258657 434722053 736074193 669311681 683341822 389909045 218127901 117960955 261968661 535020801 960992281 419082315 228303201 278072797 947179521 914292659 402156797 703039613 887038781 986520645 794810633 666284373 150067881 62193793 889123303 94322821 726299057 952411809 473437076 893358009 733832665 405006187 994765233 960905201 125738481 378000273 805388221 158171916 304070833 963273381 556366226 82083837 814266105 443536935 827363727 13126101 892102497 339597921 514871489 869054249 318621393 5963946 734952577 286770817 656596977 55893761 164690689 815825659 833301313 661275721 271253721 275903946 798569753 703055093 145977631 579365498 365118876 962504961 14995249 547144786 424954726 944912837 61137149 186429488 817209356 383730587 139358721 900296073 340273731 204631371 682678711 87672481 585532941 952341879 251943617 320855669 623730704 903200001 611314470 550906801 885894441 210871526 338763521 835490561 559303681 735398255 137188866 799991455 795979777 880419929 523698241 902982086 598877027 1056626 720304846 542626561 685153057 641475329 680516057 591559488 934099521 445132591 476158831 645500649 173309121 276462113 458791785 200142433 497248064 297536351 600494593 25407179 195177285 154859901 285601708 404007637 537735269 616784897 786003793 523804641 5803087 954624001 993185866 294441729 634356684 838495881 483562586 165647121 502230913 687338433 787653745 18958151 954370413 304571897 697791761 505291630 178696975 441989521 821387609 655808409 832376285 31739601 97614371 519945626 973078551 275831989 688326353 415847117 822194161 395384321 750137800 872418009 387098861 903865820 394994941 571722989 656012954 724987551 209502633 776036729 726204325 370337513 827488161 530152506 811762941 619718907 635501165 365206401 248308033 348889089 392056937 192739947 567439065 248692321 607106796 566473009 780800001 532183475 477989121 765203601 347128713 269971881 829876913 200132801 846857697 197670107 157976521 277419457 721808001 986194121 721893233 370036001 909993281 759426018 585529725 199293745 752186181 186671542 511154631 624141396 523409915 155884313 56042433 340206861 58273596 24060004 273268081 272782337 193948751 94833101 990089973 388717215 171699497 210923601 920739954 688865601 259662001 463774833 885615605 827878241 950965121 373970209 997249531 972383001 294599811 277475447 138770861 738248221 72462681 870729921 70339129 438461261 443216909 848386501 865854721 57550021 344432751 682891737 333173409 681757441 437407921 950604197 31706931 696221851 635499673 522993881 548626931 303595468 960981469 135161301 267919681 919822505 713168401 212820413 136892929 97512001 521647481 567808617 661950120 145052801 112559793 869622441 314714951 436310152 192253697 657291905 59801601 800576561 475735657 355682093 61932545 613941709 643137733 828099631 974075241 118909441 722561428 204374401 689830081 709035705 782322341 943836555 826194231 264969513 40492721 406561871 238775409 48169249 191925369 873915077 977957417 859787693 547188645 849940576 987435211 91579145 655353057 752144869 273441489 921891721 721467376 948415921 421149489 894545011 639517971 252748517 177745481 607661001 998956971 644682275 547264221 477876221 314824279 164502081 927424801 889884131 360235451 484742424 203462309 236590511 711372501 348583345 822385401 563238961 119178469 694972721 683062551 210669265 227735201 169591848 578212501 404369345 63567121 11363921 903948577 24837826 750519583 298060545 713327001 688817825 784139696 602168369 582953006 24058461 668547423 866273813 88766170 463133153 399629713 814335591 165086855 527706433 56322041 40889169 586827261 908081251 848320393 893219059 828363496 278185961 216088129 123051841 609825001 464927713 966047097 48023969 52444641 80302881 861726193 490533823 262595589 751143781 103783231 335046389 612893087 180281830 522337242 818494849 192252851 831449121 716453567 443016245 817049371 210225873 428278081 484811681 517222273 480668161 846676833 892634707 444807341 756882769 451572321 483055751 513356065 504040106 324461697 405934921 845280025 246763751 588420001 873602873 786099661 336108261 46341764 240470329 248103169 536097587 783289681 559837401 258874863 89745457 69473493 289778435 239927201 368369406 644503057 161189977 610315631 562465274 650223601 84876751 475813071 443555891 559497452 304688143 19637248 780824185 446046353 59344801 913154681 187830173 882011893 601811145 610755929 22927791 940686501 352109451 398018401 94873017 353111961 606106759 325448793 691043173 789859841 100185917 29213681 626866951 387865865 569790096 302655801 609029345 117177345 788113158 184973321 957256296 410054901 500404481 534081085 262507065 822269041 425747768 94916641 247763381 820192613 977036001 6803201 370355921 471485271 17906876 42707961 470473371 564462726 312324909 410401121 265006641 300280435 50264745 372666073 563490667 154614001 791358073 471847551 928756921 787725747 919951361 546181231 703283105 221380745 324277139 654869411 306336641 624964513 503703801 722001329 901336721 25994625 994405889 758092881 380803889 498478081 230031025 960480633 471828481 5089361 254925441 370962081 905180881 710575325 575850221 326707755 434555429 659183021 994933191 395505741 84466719 660561451 734396657 379326101 455524481 589085396 714892616 652120697 993704183 54481857 124739631 461697231 815484801 618943131 922480415 109102401 95427777 696110592 613539605 100996019 814970409 39556705 865754141 252156072 886925361 384403025 279888885 813152241 58375269 194161113 647494777 991382045 939309153 949229895 289937533 406035354 632814239 419214929 121728139 161744798 748163570 566969166 553296875 612701401 685919201 251154153 421116419 890153815 125080001 868936602 250843801 497325831 882974049 491644101 956558541 95760671 567783031 80380997 223188457 674857841 329356085 810095793 701379273 997251321 757486231 238701323 668012615 371285649 755878129 835576001 28900649 755416255 535983639 133120459 617722881 481675201 63997889 89458929 502770401 340323034 439755869 38324297 725932401 147587061 525151796 966781173 885390183 609464629 436132373 303169435 497912049 441969953 108469401 566899837 213919377 999312645 962468161 945264801 196058825 998322001 870345025 344494593 767573837 298133529 588685877 700367609 23997361 861522041 643457051 37943721 604111401 838640841 478033751 967147489 546456879 307653945 948512123 708523753 599295481 983787961 62534401 151779677 243519841 690815744 459355193 993941407 824470089 2933761 806127745 372355599 386897241 337879057 12555231 666423821 664719161 995132609 668738951 559927697 631000701 823285806 637904961 134541493 380299521 22987361 182706521 168194607 466937841 104120321 787397406 392153676 675340673 808775461 594515177 741314049 737508025 398235905 702484951 951424217 802637681 705828676 606984933 692445929 885396657 729954924 336721661 71034859 730624079 512453788 591330777 759510637 416915233 645682137 125144943 883056741 786056157 326598551 466302977 171839751 327033221 714732833 491353545 910126820 871183929 388160673 300944601 703720425 302961441 813728841 209076273 317944511 750498097 297382181 297662529 281394251 108093587 813728977 214843385 162297449 277033889 804700673 212667361 468189293 461516941 173121716 937522941 779908641 126416105 709477206 386255201 131464065 973696221 907166529 694732465 788223791 468787433 298744371 584843251 521806721 91900481 788666921 330734417 56264329 460492249 388332161 180366401 753452001 266914127 828544265 467943273 601470233 609227233 350739251 894593513 463335865 357975361 625884849 419581976 504748849 924727731 974772633 984199035 190882561 105064067 779357157 488402345 197646273 65807261 394092627 138925075 18989299 737787313 249196677 935026973 595984566 889158081 883078001 148688996 261676222 952414249 524943969 513581241 360346532 175467701 46043601 291722501 786419329 174041953 798999651 978331265 846772581 434146278 5459779 911011097 460927091 693647697 443531306 327417257 620224401 509850337 145660985 472781931 949967489 30101061 117734703