{"problem":{"name":"C. Mahmoud and a Message","description":{"content":"Mahmoud wrote a message _s_ of length _n_. 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 d","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF766C"},"statements":[{"statement_type":"Markdown","content":"Mahmoud wrote a message _s_ of length _n_. 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's because this magical paper doesn't allow character number _i_ in the English alphabet to be written on it in a string of length more than _a__i_. For example, if _a_1 = 2 he can't write character '_a_' on this paper in a string of length 3 or more. String \"_aa_\" is allowed while string \"_aaa_\" is not.\n\nMahmoud 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 _n_ and they shouldn't overlap. For example, if _a_1 = 2 and he wants to send string \"_aaa_\", he can split it into \"_a_\" and \"_aa_\" and use 2 magical papers, or into \"_a_\", \"_a_\" and \"_a_\" and use 3 magical papers. He can't split it into \"_aa_\" and \"_aa_\" because the sum of their lengths is greater than _n_. He can split the message into single string if it fulfills the conditions.\n\nA substring of string _s_ is a string that consists of some consecutive characters from string _s_, strings \"_ab_\", \"_abc_\" and \"_b_\" are substrings of string \"_abc_\", while strings \"_acb_\" and \"_ac_\" are not. Any string is a substring of itself.\n\nWhile 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:\n\n*   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 _n_ and they don't overlap? Compute the answer modulo 109 + 7.\n*   What is the maximum length of a substring that can appear in some valid splitting?\n*   What is the minimum number of substrings the message can be spit in?\n\nTwo ways are considered different, if the sets of split positions differ. For example, splitting \"_aa|a_\" and \"_a|aa_\" are considered different splittings of message \"_aaa_\".\n\n## Input\n\nThe first line contains an integer _n_ (1 ≤ _n_ ≤ 103) denoting the length of the message.\n\nThe second line contains the message _s_ of length _n_ that consists of lowercase English letters.\n\nThe third line contains 26 integers _a_1, _a_2, ..., _a_26 (1 ≤ _a__x_ ≤ 103) — the maximum lengths of substring each letter can appear in.\n\n## Output\n\nPrint three lines.\n\nIn the first line print the number of ways to split the message into substrings and fulfill the conditions mentioned in the problem modulo 109  +  7.\n\nIn the second line print the length of the longest substring over all the ways.\n\nIn the third line print the minimum number of substrings over all the ways.\n\n[samples]\n\n## Note\n\nIn the first example the three ways to split the message are:\n\n*   _a|a|b_\n*   _aa|b_\n*   _a|ab_\n\nThe longest substrings are \"_aa_\" and \"_ab_\" of length 2.\n\nThe minimum number of substrings is 2 in \"_a|ab_\" or \"_aa|b_\".\n\nNotice that \"_aab_\" is not a possible splitting because the letter '_a_' appears in a substring of length 3, while _a_1 = 2.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mahmoud 写了一条长度为 $n$ 的消息 #cf_span[s]。他想将其作为生日礼物发送给喜欢字符串的朋友 Moaz。他将消息写在一张神奇的纸上，但惊讶地发现有些字符在书写过程中消失了。这是因为这张神奇的纸不允许在长度超过 $a_i$ 的字符串中写入英文字母表中的第 $i$ 个字符。例如，如果 $a_1 = 2$，则他不能在长度为 $3$ 或更长的字符串中写入字符 '_a_'。字符串 \"_aa_\" 是允许的，而字符串 \"_aaa_\" 则不允许。\n\nMahmoud 决定将消息拆分成若干非空子串，以便他可以将每个子串写在独立的神奇纸上，并满足条件。这些子串的长度之和应为 $n$，且不能重叠。例如，如果 $a_1 = 2$ 且他想发送字符串 \"_aaa_\"，他可以将其拆分为 \"_a_\" 和 \"_aa_\"，使用 $2$ 张神奇纸；或者拆分为 \"_a_\"、\"_a_\" 和 \"_a_\"，使用 $3$ 张神奇纸。他不能将其拆分为 \"_aa_\" 和 \"_aa_\"，因为它们的长度之和大于 $n$。如果整个消息本身满足条件，他也可以将其作为一个整体字符串发送。\n\n字符串 $s$ 的子串是指由 $s$ 中若干连续字符组成的字符串，例如 \"_ab_\"、\"_abc_\" 和 \"_b_\" 都是字符串 \"_abc_\" 的子串，而 \"_acb_\" 和 \"_ac_\" 则不是。任何字符串都是其自身的子串。\n\n当 Mahmoud 正在思考如何拆分消息时，Ehab 告诉他有多种拆分方式。之后，Mahmoud 向你提出了三个问题：\n\n两种拆分方式被认为是不同的，当且仅当它们的拆分位置集合不同。例如，拆分 \"_aa|a_\" 和 \"_a|aa_\" 被视为消息 \"_aaa_\" 的不同拆分方式。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^3$)，表示消息的长度。\n\n第二行包含长度为 $n$ 的消息 $s$，由小写英文字母组成。\n\n第三行包含 $26$ 个整数 $a_1, a_2, ..., a_{26}$ ($1 ≤ a_x ≤ 10^3$) —— 每个字母在子串中允许出现的最大长度。\n\n请输出三行。\n\n第一行输出满足题目条件的拆分方案数，对 $10^9 + 7$ 取模。\n\n第二行输出所有拆分方案中子串的最大长度。\n\n第三行输出所有拆分方案中子串的最小数量。\n\n在第一个示例中，三种拆分方式为：\n\n最长的子串是长度为 $2$ 的 \"_aa_\" 和 \"_ab_\"。\n\n最少的子串数量是 $2$，出现在 \"_a|ab_\" 或 \"_aa|b_\" 中。\n\n注意，\"_aab_\" 不是合法的拆分，因为字母 '_a_' 出现在长度为 $3$ 的子串中，而 $a_1 = 2$。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^3$)，表示消息的长度。第二行包含长度为 $n$ 的消息 $s$，由小写英文字母组成。第三行包含 $26$ 个整数 $a_1, a_2, ..., a_{26}$ ($1 ≤ a_x ≤ 10^3$) —— 每个字母在子串中允许出现的最大长度。\n\n## Output\n\n请输出三行。第一行输出满足题目条件的拆分方案数，对 $10^9 + 7$ 取模。第二行输出所有拆分方案中子串的最大长度。第三行输出所有拆分方案中子串的最小数量。\n\n[samples]\n\n## Note\n\n在第一个示例中，三种拆分方式为：\n_a|a|b_\n_aa|b_\n_a|ab_\n最长的子串是长度为 $2$ 的 \"_aa_\" 和 \"_ab_\"。\n最少的子串数量是 $2$，出现在 \"_a|ab_\" 或 \"_aa|b_\" 中。\n注意，\"_aab_\" 不是合法的拆分，因为字母 '_a_' 出现在长度为 $3$ 的子串中，而 $a_1 = 2$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 10^3 $, be the length of the string $ s \\in \\Sigma^n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $.\n- Let $ a: \\Sigma \\to \\mathbb{N} $, with $ a[c] \\in [1, 10^3] $ for each $ c \\in \\Sigma $, denote the maximum allowed length of any substring containing character $ c $.\n\n**Constraints:**\n\nA valid splitting of $ s $ is a sequence of non-overlapping, contiguous substrings $ s_1, s_2, \\dots, s_k $ such that:\n- $ s = s_1 s_2 \\cdots s_k $ (concatenation),\n- Each substring $ s_i $ has length $ \\ell_i \\geq 1 $,\n- For each substring $ s_i $ and for every character $ c \\in \\Sigma $ appearing in $ s_i $, it holds that $ \\ell_i \\leq a[c] $.\n\n**Objective:**\n\nCompute the following three values:\n\n1. **Number of valid splittings:**  \n   $$\n   \\text{dp}[n] = \\sum_{\\substack{1 \\leq j \\leq n \\\\ \\text{substring } s[j:n] \\text{ is valid}}} \\text{dp}[j-1]\n   $$\n   with $ \\text{dp}[0] = 1 $, modulo $ 10^9 + 7 $.\n\n2. **Maximum length of any substring across all valid splittings:**  \n   $$\n   \\max \\left\\{ \\ell \\mid \\exists \\text{ valid splitting containing a substring of length } \\ell \\right\\}\n   $$\n\n3. **Minimum number of substrings in any valid splitting:**  \n   $$\n   \\min \\left\\{ k \\mid \\exists \\text{ valid splitting into } k \\text{ substrings} \\right\\}\n   $$\n\n**Formal Output Requirements:**\n\n- First line: $ \\text{dp}[n] \\mod (10^9 + 7) $\n- Second line: $ \\max_{\\text{valid splittings}} \\max_{i} |s_i| $\n- Third line: $ \\min_{\\text{valid splittings}} k $\n\n**Auxiliary Condition for Validity of Substring $ s[i:j] $:**\n\nA substring $ s[i:j] $ (1-indexed, length $ j - i + 1 $) is valid if and only if:\n$$\n\\forall c \\in \\text{set}(s[i:j]), \\quad j - i + 1 \\leq a[c]\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF766C","tags":["brute force","dp","greedy","strings"],"sample_group":[["3\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","3\n2\n2"],["10\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","401\n4\n3"]],"created_at":"2026-03-03 11:00:39"}}