552 275
770416242 706115507 876450374 635467803 943198546 560450032 177052676 128351081 170828085 708736882 145259215 865143845 559075393 723933287 194267148 599202773 605664902 944797868 781379295 125041316 573095111 479732292 159805746 139320158 577141548 960760326 814806971 578932744 978572470 896701093 773241492 870170285 732971992 783360276 478130525 996770434 498137655 525420909 134078397 768401078 442022746 762210277 964491928 602258068 579589869 593759865 447853066 473488907 544409062 468189466 976763901 739539587 882214487 450136412 735522748 515972834 563703618 856493471 792870733 148593248 938196882 537774865 179242826 941595653 188133984 460791618 991861878 493645407 873269149 155819754 641841574 647123729 482231114 800874566 149290801 624774233 180402329 775221653 538114713 595139987 642690681 584565017 613628217 905164429 735871271 553430923 141938581 481510655 445159260 524413703 855629247 584106572 769578236 173167333 511448089 438656948 561815380 885586543 492591001 596479729 579587274 483355813 953789860 733636449 866459876 765027590 777068143 964837715 459676688 499809465 562805353 964221884 591052424 975265315 716600491 163757531 879036754 867984549 531283322 188511359 447857969 804332975 551758742 889719847 807846366 645903633 463960302 616414160 158946776 644365508 800343595 980156813 503901988 724961819 633161239 505697441 519918962 996081792 492746892 950211914 989302906 537815589 506080746 890701083 135459165 621415466 547414414 907270559 962415937 438801003 726956024 589702291 160478590 482892842 457272847 727876218 721494772 860530124 592317887 603136739 195532146 816426684 753697132 143796948 747093900 4886814 200843586 556056886 485060641 808061971 517180737 182098985 139657518 810916090 564813091 947547378 892345088 617920539 616603046 887711911 551464402 619364466 565598760 176001892 154718893 607787841 754745385 500271719 508445776 990967844 548363782 757491025 162052116 599652469 499281541 771386443 785915091 451625354 185891609 509975711 744510247 710001459 528092476 812566498 128258666 611362821 130740785 858893278 193362520 576130876 744249955 635992671 141034793 712683301 3784290 466389421 462400357 495107382 861940275 650370786 189677158 979026036 776704027 141266852 454234024 948200191 997441376 954990798 856233150 442293722 558671601 476222305 762728167 711802225 498770306 717792613 778384909 791759708 534922198 532856294 162155708 488925408 971538946 649296148 648877844 129070838 804871944 752660326 787663532 737697462 736417401 502895692 970936415 719404989 183306001 801194046 787170978 957806039 984300091 779513801 190114592 485928647 995781959 527527987 465015287 523993762 503609201 142132610 455351585 588271543 719881208 481765664 721921272 999999999 799190289 715104393 893922692 967949853 157051435 137186843 546152690 554737245 501430055 449329645 490784201 597793569 899009789 706254859 779550081 725357029 766636346 900022096 502229616 582916421 719480844 745107516 603702805 717510372 165335152 604257089 619184786 470730604 130686712 631497884 484508484 742823849 881656546 584110179 518964567 869978855 863426535 801909592 477421927 898076530 571745790 178011968 439530197 998568536 496656813 454605619 611753627 458463401 730584508 942336638 640391562 3202292 755320088 886775064 443734540 796016100 550165876 614920436 754797282 196748189 161169775 594845745 538362418 586953304 761514447 591688083 626424173 856362587 781431822 959319913 859155603 567308307 806672958 137801503 600972578 802933410 956813190 534569794 567586794 1529899 596507318 627224863 783121931 794637135 457155594 737056038 880084056 573507752 809910927 474899642 585987967 903456479 956226696 187497600 871410529 734983573 487696864 561416137 883899031 514162833 604955460 620176174 525402859 541201445 129810626 550861662 492888191 199821721 760535111 798618020 894402992 901282080 564727421 738118107 782469122 809706035 719052510 148309166 948418787 581387662 610912368 168709142 763651287 982717117 939745161 749780011 874918237 176384586 573469206 992101855 757352690 144526377 126504761 728233806 946082098 543790657 159389138 150257615 531207877 468357874 519486543 504821950 140462031 164888295 707016682 623134015 471396385 167028558 742621623 795517864 906257482 521500928 877824884 740921702 746572112 896145509 795638385 713399927 169426891 949901970 565074760 868701445 187841104 441958878 857464815 527687370 992747751 469720327 568712211 732321090 138894903 588444065 981362435 523660618 889060747 609126974 729117879 569058174 452731485 779745938 716724360 198385127 902936184 530841613 151279709 172588504 593453916 806960855 565973843 132166807 751226635 576347314 990667988 905410382 472143684 735995546 614906517 152174155 557137200 525159023 789099529 985330484 744524317 987873567 540061897 790352684 804510056 157386958 876769678 940837986 127360072 639572585 758563885 805863026 606186231 980160664 612684946 722279321 575099047 973983322 759194773 813723479 477988940 446199516 610858808 512563406 627725693 196937005 972863643 437803431 945321797 862527785 892081968 986621983 773112465 133913529 191587241 868706531 888351119 559997202 722002418 536440662 184735736 507551210 728395619 774902784 522897524 153647820 791614004 797588041 146512821 629070997 634418423 174250441 727382571 543038626 147855936 529052187 872252090 965398263 951978344 460439237 527163063 994386350 440987387 570541138 966831946 978823369 756775011 140382749 454923824 722678001 629755265 748246850 609346720 542403121 784662557 190259353