684 340
280614250 978143132 751929988 261346491 240740408 280665862 178639273 931508702 909310366 746731731 968654485 977352424 827461243 5054922 887126581 890961738 62468365 951283597 139932794 748175045 745413569 776296518 205033516 132792727 829504886 812382981 938805518 820087751 50914939 740029981 127681655 47361537 97965880 797929656 77663138 866299134 934242624 83956088 877298955 198703902 769127672 990993261 913861315 230883613 773596243 764742624 138259851 162583883 211644142 85206154 55803274 121720314 102797303 69231600 799252668 100134916 238772418 8114359 281941523 168717777 184971628 966943184 2313640 109396131 42551647 90959220 818494996 981854943 125083166 897297505 804726923 196510969 138950364 247242059 106677603 104233977 919730534 809657917 37483029 199814022 84339289 190692473 788162826 970851509 927656937 945770676 894318114 245801947 935683105 85230961 53948020 182266873 797789436 116499413 883196037 977463868 823327253 868100751 746436671 992315775 238287310 207498900 933190167 875134325 44282886 86470723 185611814 106063937 87275298 120720049 91707694 833198495 810506766 189751839 975259148 887942987 742081277 743318253 109924325 779411538 264815385 272455258 233687917 901375999 923058084 198215745 95488798 36313697 147363515 867389176 930241872 781685273 990021587 273205668 165532695 94598829 912304866 239241661 279240980 262584620 892470742 75952863 134478691 219470110 101375974 236898623 753990866 833305250 907137443 191267067 827519265 952266862 161242801 799109977 197744583 981866445 245329259 270274242 218502089 948194843 783874125 894010750 775808709 174632348 865240567 92274994 906877929 972934181 948933172 232236152 882478216 873946178 740870669 916067190 74527063 35121599 270115792 43783594 192247476 198870108 996585553 130285058 46504359 278568387 892384090 910141498 148817508 249874439 786910346 950289676 47893993 117557653 880164674 872590897 738661937 923290954 120900780 45409074 170335149 58770493 123424709 208797925 731185015 796195094 756797307 17542125 957045405 986027428 207682432 892608755 68691352 939468024 265382256 889196782 275508630 266672742 266569017 871579033 834098527 280034156 937879764 983790638 96860294 223739671 40809128 21491254 960836443 755422685 65107053 166500445 15970251 110836502 895178564 900326251 254536894 224227302 922574029 758390743 794211126 967542828 214780276 940683 240484409 156871974 22934870 803780917 73659045 49243504 9065224 834911115 224824054 807903815 906045036 227090087 759755428 112830221 279421081 821399785 906574509 107593436 831747764 177042618 33453649 882443871 822407812 57156419 890123799 990842553 61242011 159139604 817365795 204941361 762372833 51684196 807748791 786515914 181328868 956165721 46065159 767343709 112616383 997433116 223228031 928668345 975638054 864597142 754131927 880175566 63222270 267419385 108932166 777518687 51737701 175687550 879127902 782772917 995249512 918868987 940331123 248899091 154148335 959629939 801616401 50437297 177970489 743504018 144480634 983011346 202997989 763388358 735503513 897182046 936853918 797175925 24866534 943466544 965877836 922817162 90349247 733870694 204323721 944530578 88691858 28872825 149368341 770618133 785126652 228842482 228129467 923674579 144881280 21765034 880737085 249770247 731244894 134387915 271589428 186539280 159355390 212476897 39207770 154890394 778145625 155905172 811328279 895441027 135830485 137118787 819501960 993813164 187670991 254096747 167942135 805834098 125274863 745067018 863798164 10224956 904739358 965147500 824364926 171995624 944704169 169692191 133512611 172975947 262909376 230051316 973809699 252091154 795530303 955495728 29653553 963774352 250866733 255759189 70629946 269349317 973023358 277147891 954197401 950072486 979700730 862858189 914692205 197078872 998886470 888510774 274346504 158212474 7156926 268876909 216324717 54823332 981453174 170309653 993069566 146484347 740028340 56332376 786665044 252689620 914385766 977492800 909573826 791111371 153619214 917394662 771270742 734811567 980402079 903482310 117987690 73338698 792411168 217966034 889010329 144880036 215324668 111928821 200706190 902370392 13167445 913055578 117610558 150800549 216759845 143712303 941400941 742841247 988470531 825672843 56066501 250087005 41661517 881593175 732865923 752209850 967466029 164348769 17052423 28203530 979968670 246953656 30992636 925115627 926481646 789766545 874505150 985288078 7891886 814948736 264124985 790952492 122017817 27249711 180794033 772385717 793734447 812357800 114137251 918408221 128954091 259393560 210362454 999999999 150084607 106050871 220036023 143031632 220539303 19736663 826170292 51431723 908194852 89199864 761948878 735379856 40289782 100917322 226231549 908794173 753317073 785486465 258497320 736614513 995980752 770296625 748906699 248166046 746991422 239910860 234323795 191714498 930150147 131566724 978769450 756101062 152246852 816777344 798277499 163189012 254648313 896561528 232496693 869080751 174306830 28917678 894773676 265011269 252549177 778061415 21381597 971543496 920910766 225022766 235730634 917658740 911561719 985224165 195722546 241581352 772699584 754131016 776531508 828595069 94296471 773528385 257163065 209511214 251117193 976471938 48610997 808632036 737204900 100245568 40223022 765985471 140630290 32216779 774419608 18959599 732542657 138375380 98811180 885493899 145728041 119431339 955071177 280737027 804747451 750743993 105154183 141641302 63802301 750028612 888104829 115780933 935215778 877964711 153701009 260030931 759220520 759249777 201853826 93489805 989863835 899622378 760911056 211301673 45704653 179491676 276803476 961224674 943678323 243849982 59972902 183665884 85814740 780588950 884627813 39628309 32746357 14521507 37966103 887534183 836166178 787086862 34352055 52650833 922208563 755535423 137057639 165063635 155799491 928235837 757118454 929775097 813504518 213479845 17100801 61724906 145316201 912863803 768796281 126314221 989958252 923569484 23897772 770411190 958398497 832105238 159893382 775315659 132207357 5686815 244649864 193511718 221581344 938838940 20910912 221979859 777265687 806534919 88873240 809243936 194854704 72321559 66473298 188602403 116936850 976681365 56855681 115156491 987072501 6574911 142605282 36670947 998333077 177070835 76708007 3708033 876029550 962657634 797113024 25925532 58188329 870414547 117949168 810700938 67394293 802367535 833638565 949099770 744596221 154948619 931756565 927085897 71887904 171318594 123976506 60669376 157122171 899714235 150882125 886235906 815423829 175065039 898314779 953755391 942196622 830361676 949026816 257799794 877969962 242840411 947127627 900034392 206372202 185601184 953058367 788950972 800438039 970115160