{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMahmoud wrote a message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. He wants to send it as a birthday present to his friend Moaz who likes strings. He wrote it on a magical paper but he was surprised because some characters disappeared while writing the string. That\u0027s because this magical paper doesn\u0027t allow character number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e in the English alphabet to be written on it in a string of length more than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. For example, if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d 2\u003c/span\u003e he can\u0027t write character \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\u0027 on this paper in a string of length \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e or more. String \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e\" is allowed while string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaaa\u003c/span\u003e\" is not.\u003c/p\u003e\u003cp\u003eMahmoud decided to split the message into some non-empty substrings so that he can write every substring on an independent magical paper and fulfill the condition. The sum of their lengths should be \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and they shouldn\u0027t overlap. For example, if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d 2\u003c/span\u003e and he wants to send string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaaa\u003c/span\u003e\", he can split it into \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e\" and use \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e magical papers, or into \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\" and use \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e magical papers. He can\u0027t split it into \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e\" because the sum of their lengths is greater than \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. He can split the message into single string if it fulfills the conditions.\u003c/p\u003e\u003cp\u003eA substring of string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is a string that consists of some consecutive characters from string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e, strings \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eab\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eabc\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eb\u003c/span\u003e\" are substrings of string \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eabc\u003c/span\u003e\", while strings \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eacb\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eac\u003c/span\u003e\" are not. Any string is a substring of itself.\u003c/p\u003e\u003cp\u003eWhile Mahmoud was thinking of how to split the message, Ehab told him that there are many ways to split it. After that Mahmoud asked you three questions: \u003c/p\u003e\u003cul\u003e \u003cli\u003e How many ways are there to split the string into substrings such that every substring fulfills the condition of the magical paper, the sum of their lengths is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and they don\u0027t overlap? Compute the answer modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e What is the maximum length of a substring that can appear in some valid splitting? \u003c/li\u003e\u003cli\u003e What is the minimum number of substrings the message can be spit in? \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eTwo ways are considered different, if the sets of split positions differ. For example, splitting \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa|a\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea|aa\u003c/span\u003e\" are considered different splittings of message \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaaa\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e) denoting the length of the message.\u003c/p\u003e\u003cp\u003eThe second line contains the message \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e that consists of lowercase English letters.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e26\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e26\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e3\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the maximum lengths of substring each letter can appear in.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint three lines.\u003c/p\u003e\u003cp\u003eIn the first line print the number of ways to split the message into substrings and fulfill the conditions mentioned in the problem modulo \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second line print the length of the longest substring over all the ways.\u003c/p\u003e\u003cp\u003eIn the third line print the minimum number of substrings over all the ways.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\naab\n2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\nabcdeabcde\n5 5 5 5 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e401\n4\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example the three ways to split the message are: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003ea|a|b\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eaa|b\u003c/span\u003e \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003ea|ab\u003c/span\u003e \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe longest substrings are \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eab\u003c/span\u003e\" of length \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe minimum number of substrings is \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e in \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea|ab\u003c/span\u003e\" or \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaa|b\u003c/span\u003e\".\u003c/p\u003e\u003cp\u003eNotice that \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eaab\u003c/span\u003e\" is not a possible splitting because the letter \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e\u0027 appears in a substring of length \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, while \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d 2\u003c/span\u003e.\u003c/p\u003e"}}]}