882 439
913327005 842863690 184249051 757362120 917066248 794908909 130917621 724881976 971601952 163921292 922792526 15888142 863943426 680180625 112458320 893798838 846200406 963158384 884082387 774805225 959814718 603154852 838674041 756291288 843683850 989367110 39583147 53612161 677017865 878733438 926331593 720548080 908886866 203427860 732499850 606727409 720254005 7385587 723789514 999443853 176108677 129885426 797860104 921819286 108305253 845606023 959117738 701258984 157659332 769807175 901940767 805978783 869257110 992029519 852443764 776785978 791970775 97991460 867320970 709511443 785096235 904239828 197377027 898957637 944448069 200775873 975402738 758772380 139435640 51014410 771557577 900762810 906594324 865707518 795787441 966900443 93781766 610173860 834626727 954129434 607661241 103547481 770637646 786616338 10587594 18299164 890189360 21604380 139749467 600920909 16249143 135898907 116289584 88423353 133407849 627851410 126739895 1413296 932846122 997509342 785971872 35249670 928109654 51626908 171102645 985675650 167271765 29089735 977124796 873952608 163693394 98376552 837990865 875328547 937002587 768888291 4894130 141718896 840956464 695209941 742566828 912724277 838777523 847193900 854774037 745498219 722513589 185900839 800125796 854783009 756160310 827903105 814272975 95706765 780069914 765093387 706629125 857469842 699486782 979080664 212074696 885294639 148050596 918814025 864611444 967497180 988865008 96474879 127749537 954620584 726047103 778289164 954751126 677976338 186476106 3657803 815331757 977935936 46540708 154291281 769187754 907510043 957648327 613514221 859363225 866331689 805773520 886202531 751568886 787166721 829054603 133950179 802748656 867293062 151013575 185263642 182811097 791816834 895775112 730802913 189124542 92168107 34250702 175289338 85216128 816395266 810186430 798871551 612547246 818690851 835848536 621376747 996358873 958003150 214223631 759667230 973759139 783748417 735266534 726850791 974453801 17610723 776574853 158490654 697715242 169376441 916429626 876558456 822322150 875808762 123748704 792031618 610648795 706810224 772647816 916751120 737342021 953554957 204091249 90897187 808188353 948265428 205198694 179110853 699752712 840523899 109675206 94837720 22442057 211782759 936183803 625060163 152546896 193680223 974091539 624931432 892225598 101309291 771723080 883741600 927875185 208804930 898239014 107830437 50119242 908494973 929026051 618705508 105364543 94708685 848195456 55278423 833873223 830107904 39255588 994905290 767169620 120152552 10756205 813651124 709415708 110527404 149221104 803148211 826241416 152109953 209492530 968578138 920911107 813611319 703629918 602159256 781037829 13608336 6900101 177117633 819721323 823330313 964109685 42707228 162339054 14533930 201595475 903199574 938956691 701221202 191672207 797370241 960816787 981603523 770342809 619779104 9479455 104633093 847743598 743020507 969507881 35234187 176569304 617904634 125964872 625602989 823439963 872335296 118945916 615872902 889654593 992944430 919888518 872914891 820893498 817408624 947092908 800572277 29783882 202318927 867352666 30949104 985404428 188023973 808719158 813324791 101943068 30398606 861778354 31561013 849148490 626494353 156147486 853499090 24154474 621655488 708077818 833018245 679106000 778783315 189639660 711126042 24624592 707225323 628768864 976485442 839669041 939484006 723647616 821858096 118432898 610009367 123537975 147405164 115872600 869763728 140793116 973478575 869163101 964765782 28998502 861005871 57391588 943728612 746757762 748687822 747292133 845311560 196080174 141193902 901398642 109010176 945954259 117535558 782743107 28838732 848031486 972575282 949368527 858282262 738387606 779232508 627032645 125234641 869713922 623292258 133781955 624358741 714269810 178209576 993425722 210654419 195534474 826207854 156813905 930979156 975321014 857237821 137659200 174412405 764202264 895065721 848284802 160884820 196597717 140653040 720097194 914174507 727844761 788863527 167687099 709884170 787857380 896042195 198649944 180244154 983867751 91425556 951066368 128828234 717988913 122443953 701474699 721257126 209474756 18944511 801205899 977602246 205555524 950439513 856530488 797454737 870612303 150101772 718504516 734396290 148461813 741460032 793106247 190980752 169991868 760802858 763161110 918597641 15689213 208198998 858710807 27004091 97333082 841880038 955496574 719565165 874852731 844038838 113095347 857450533 602932869 611514678 42947180 604358414 868055355 216138326 851513695 43985335 709089881 886339871 19148126 978620304 111859588 159211957 109752140 732024616 41732697 745234942 604068347 210263600 152986315 979340525 146308096 212628475 99209161 988008622 917390679 957247858 165389206 100624730 119653248 606868902 722512564 88346673 790447755 886767797 906750763 894100502 93177606 868396130 923885963 144449065 182162211 915343355 765820967 827353326 680706991 738697527 864465645 114029133 928809268 622486697 210961519 142683695 789953748 792440160 147718370 820557605 933707598 825186408 20663114 627903257 38508939 702981962 199451613 54328606 748573531 944584563 49028604 952111550 698353009 712642981 749356239 725427443 763937391 832283345 748145294 775807455 93813804 911707485 729754588 180742452 723568461 799115522 996964492 680844314 116908868 760548401 121392852 860472971 962754469 10579338 739524495 213017105 795935959 736461824 11829720 215767991 790171964 776368647 777050398 853694548 946505223 784154162 899679901 862648580 12498972 809243831 932187397 5319729 133326497 1668146 945179576 969491253 99932481 849997306 882954059 974448710 817815497 171912230 107177791 143722301 950055797 855778041 746357055 791049914 206075785 166178689 924302348 197741714 56362223 766171156 982920333 30545467 48311087 37688505 837327986 902845695 138344375 795901618 132050510 719936211 615169000 844657824 3021296 891404361 905763134 890588161 146314326 995974269 751230349 781634863 896544574 740917429 990209899 926079469 755738615 785110881 947485894 132713393 817272651 741914775 880426030 871767532 207107680 180542430 975021462 757935315 163996980 735597221 45088616 49160924 747590196 198863896 851045558 115998228 798078790 909863971 828280009 917709350 981849744 155019480 40099473 15374093 124839433 810180182 983709326 903802934 125917994 935057494 831039012 785146715 700838947 881259791 733009897 790145618 970494650 89160542 205614943 153512721 881941915 901103578 616960203 987371842 173294285 965884069 884131447 160182078 937868643 796611535 998418807 724046307 976587078 47871171 887831549 25953903 120651130 601769444 111607013 871133692 951764127 200442181 710071793 711835132 928047864 678499981 853124413 713349091 14252437 2995257 49989323 750897244 793123893 918064702 25817358 106682219 126138762 797735733 812247143 105615382 163374646 802296919 969111848 728698410 116606174 797072926 797420706 185700973 87256417 868088628 95822493 762155193 980496637 846089664 999999999 46874779 23397765 216597692 876820266 744149872 947284005 775131567 192602745 620934309 869051030 853529010 761628560 6432953 808118800 925592252 729066067 115072657 695905914 86312954 36658362 892843073 608991869 169153207 10794082 13961453 866937934 16784252 187364472 164953431 702865121 862831106 145795709 927247586 880856908 601148235 134968221 764932539 800886810 870396974 734138774 748554720 990456579 836482970 45441140 940140743 953107688 46087254 168553236 811057963 172708621 893048074 931729931 877661546 174351328 132982337 891384464 879751254 766603854 706517730 908740301 870592982 41203375 701742061 204176514 969700768 758761141 905097915 963251261 619822088 904095405 20042724 990937878 49771896 800510284 978232103 145713539 914775677 102944796 984403764 45066810 614085114 835442007 760942518 773065472 626217776 929561528 759358252 679699272 696902986 56728265 888591457 181120579 934693540 913438257 986796292 840349847 897404192 619675964 824441579 749890595 994240706 988450164 605978622 606457542 768243666 979855702 145207322 115395377 25339724 174200448 930246366 186159010 90090726 160270599 190473583 987822783 763295165 985584712 765410761 138062713 28088433 619345641 629891827 804257828 115129677 901765849 923099993 962204342 739955995 608319119 214128396 811976660 704561882 924527537 46908554 680382201 194727704 35964279 4085461 628031135 875930961 179432297 726332276 705392738 125481299 698920512 892625872 956424849 8480514 214702781 137510542 748948291 806913999 649036 90664318 773916201 721741776 102380515 777264003 961236713 910622937 698027041 793999861 730919415 805271629 2034102 791584655 161251277 807800070 923623394 832113343 999809961 605119670 136456485 121404854