584 292
948774583 757183890 942314254 78236974 889783798 943991605 933652215 669393883 92891314 974395329 703580785 161977630 928018852 85744418 894358112 165110770 816911056 723919209 694451298 147581493 993066447 797392100 22024093 963711685 692235030 648503746 945730531 827502200 641456659 860485488 714693595 77237195 740189141 916123850 658966689 803053066 629509988 982124582 819386714 72236006 134498894 151987384 801193956 944716438 884827265 729240495 853818746 769593194 787088704 681742387 898001271 739177182 636959131 670783615 190826484 971262708 680372874 716064106 953316371 823646845 115856021 774773048 913748967 922768965 998815158 95879292 968544884 661434348 683518541 671147642 924697480 106903309 84863129 113688111 838301623 862509843 960852441 713766239 179132832 132030423 948078122 169855873 85213927 815208190 676700253 865878875 737131922 665445181 833640293 911724109 827008367 669838100 851844287 988810576 147914271 879249040 104839941 672637557 952383731 701206735 672170396 15970436 689188600 882287794 894999030 776997831 705470203 775355738 127702836 767155707 718806055 110917236 905679837 762686121 746825822 985219512 685918445 823016532 806537021 935730581 646434280 657240625 800144871 634951128 745195900 920856645 867714834 84549293 805675605 818004826 934524845 921111490 869402319 856860856 932460302 898408475 855201776 805031381 103981542 659838850 733597942 954096241 839153811 130128759 880659451 719649352 167761769 950712924 978074207 698206253 991556108 190599621 762251408 789750483 679148253 186074382 791407971 174258567 925909667 936386074 772048260 83110203 129349360 184680981 130525509 976745317 662564553 712255894 150296467 789919110 146127823 631252519 919658743 663758041 730329641 792439060 182740367 635671230 82142016 679071862 86580131 104339688 185935509 686443805 809474700 733306322 820226405 672153806 191475007 194372976 105743612 112343671 176899201 854584403 967473588 674800061 808415658 691129602 848001787 791565553 687489781 87402813 690831465 987192926 858279789 719489318 90249580 652109962 127328858 169649268 675028598 811561871 737530665 164876351 958465608 899770692 929066366 941377807 891293593 194349091 124210468 639334082 793146653 15118699 73715211 629373820 194392544 755778467 883814374 729194144 915234051 649284809 901697196 886008375 175233243 700731399 713908314 911379044 709756379 121188144 930979134 986127199 3730807 682582830 727898290 779881256 933877026 96251639 984054247 629939137 148972279 707833898 990027234 786918130 650183084 697288141 22817887 661337005 870056017 94331827 853108374 922994739 633790998 726110680 109770119 785753284 944462194 983391872 734961626 99057033 653301101 889588906 896836690 748876215 167251766 70853163 709914359 161984562 813898632 956488854 902725811 642866923 827622829 165844030 805696215 674165039 966188323 654761092 939687576 688478724 830341145 102334391 981250217 697014396 773502093 831414625 664111799 906282355 814677252 991907005 788131816 647718618 118375775 2758830 675366020 738315149 792998480 976310997 634211148 888337692 858901641 768867111 180483641 926683334 861244976 159016446 812202836 797418823 874458520 995903721 126749818 803486613 821322337 824294205 115373606 74994457 892374287 90301726 929567726 726671845 17188901 832500123 117060635 884214067 188615978 963072926 643329814 741822225 699619305 705743953 18534535 974767362 956445194 809893624 879639903 658656499 647269785 100002568 668227172 645007139 815487222 661189099 677487678 919616585 120194228 849225907 743290928 777202919 17544158 904242869 75195711 144681676 802059655 655988760 927897499 941344758 702350715 999746114 645101958 939563544 850634399 878821951 154058520 731993028 102256283 908814070 770802205 784162032 187288547 781109136 101255468 965243985 804806971 195306013 69529117 735489514 763763002 878408345 170239978 133655969 185251435 693048882 706285980 177487567 136110842 141829881 80670765 670143524 835227415 765530198 12591899 163079549 747890340 871715215 795003473 161125932 86793887 938030349 77711328 909765031 150319133 778571494 693109435 793545188 137336118 969115959 760709413 959986231 97774063 972918737 122861937 935559293 830993079 143326949 91612214 196685309 886668028 118064762 163540987 182035962 930718252 864273936 792343228 645917844 139537080 3193662 159835573 152581962 862908177 774830077 702908395 980653511 801625362 863677156 770359253 895554518 710696742 782556666 140616614 777811428 144179929 947709065 798297906 762524378 107075046 698452537 907953814 164173453 107211122 197206854 876709696 702130063 917733798 876502401 979596867 813976817 962597286 643993551 783243754 717304119 721197373 994745772 630092567 918331029 867274365 655246570 17807334 125711333 138704615 706064383 779182294 695188289 861166196 912809722 733581218 171919258 762105858 969680245 79464473 731582034 801680954 931745428 872908951 996842696 829206719 191383522 642701598 85461954 966142907 828036217 745029001 172086800 637913530 848734380 764847947 796440995 946173515 81348950 1251464 14231369 875994599 823758668 767263093 837575443 168773722 893068212 94173272 119362674 643768409 977310276 168086851 993651547 77937472 962065812 696141079 118485288 19785292 15926493 721927349 69053725 154312186 780791957 172782212 725117192 105331234 879821250 974683988 186591216 682714605 193106635 796497630 799032145 886767954 723108899 197458475 20917476 949767584 759010048 900927861 836113217 157329747 108162636 825635360 979776025 900064961 155648533 109754296 906689447 998348235 640807628 793951307 666895995 684406957 779853296 189013640 88639252 744246084 806734768 902204461 893717282 76351272 708825204 651353086 632403286 69848395 892840789 955757328 757453809 184065790 107182989 703832522 999999999 952848890 800261437