CF766C.Mahmoud and a Message

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.

Mahmoud 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.

A 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.

While 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:

• 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.
• What is the maximum length of a substring that can appear in some valid splitting?
• What is the minimum number of substrings the message can be spit in?

Two 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$ 的消息 $s$。他想将这条消息作为生日礼物送给他的朋友莫阿兹，而莫阿兹很喜欢字符串。马哈茂德将消息写在一张魔法纸上，但令他惊讶的是，书写过程中一些字符消失了。这是因为这张魔法纸不允许英文字母表中第 $i$ 个字符（即字母 'a' 对应 $i=1$，'b' 对应 $i=2$，依此类推）出现在长度超过 $a_i$ 的字符串中。例如，若 $a_1 = 2$，则他不能在长度为 $3$ 或更长的字符串中写下字符 'a'；字符串 "aa" 是允许的，而 "aaa" 则不允许。

马哈茂德决定将该消息划分为若干个非空子串，使得每个子串均可独立地写在一张魔法纸上，并满足上述限制条件。这些子串的长度之和必须恰好为 $n$，且彼此不重叠。例如，若 $a_1 = 2$，且他要发送字符串 "aaa"，则可将其划分为 "a" 和 "aa"，使用 $2$ 张魔法纸；也可划分为 "a"、"a" 和 "a"，使用 $3$ 张魔法纸。他不能划分为 "aa" 和 "aa"，因为它们的长度之和大于 $n$。若整条消息本身已满足条件，则也可不分割，即仅作为一个子串发送。

字符串 $s$ 的一个子串，是指由 $s$ 中若干连续字符组成的字符串；例如，"ab"、"abc" 和 "b" 都是 "abc" 的子串，而 "acb" 和 "ac" 则不是。任何字符串都是其自身的子串。

当马哈茂德正在思考如何划分该消息时，艾哈布告诉他：存在许多种合法的划分方式。随后，马哈茂德向你提出了以下三个问题：

• 有多少种方式将该字符串划分为若干子串，使得每个子串均满足魔法纸的限制条件、所有子串长度之和为 $n$、且互不重叠？请将答案对 $10^9 + 7$ 取模。
• 在所有合法的划分方式中，可能出现的子串的最大长度是多少？
• 该消息能够被划分成的子串数量的最小值是多少？

若两种划分方式的分割位置集合不同，则认为它们是不同的划分方式。例如，对消息 "aaa"，划分 "aa|a" 与 "a|aa" 被视为两种不同的划分。

The first line contains an integer n (1 ≤ n ≤ 103) denoting the length of the message.

The second line contains the message s of length n that consists of lowercase English letters.

The 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$（$1 \leq n \leq 10^3$），表示消息的长度。

第二行包含一个长度为 $n$ 的消息字符串 $s$，由小写英文字母组成。

第三行包含 26 个整数 $a_1,\,a_2,\,\dots,\,a_{26}$（$1 \leq a_x \leq 10^3$）——每个字母在子串中可出现的最大长度。

Print three lines.

In 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.

In the second line print the length of the longest substring over all the ways.

In the third line print the minimum number of substrings over all the ways.

输出三行。

第一行输出将消息分割为子串并满足题目所述条件的方案数对 $10^9 + 7$ 取模的结果。

第二行输出在所有合法分割方案中，最长子串的长度。

第三行输出在所有合法分割方案中，子串数量的最小值。

In the first example the three ways to split the message are:

• a|a|b
• aa|b
• a|ab

The longest substrings are "aa" and "ab" of length 2.

The minimum number of substrings is 2 in "a|ab" or "aa|b".

Notice that "aab" is not a possible splitting because the letter 'a' appears in a substring of length 3, while _a_1 = 2.

在第一个例子中，分割消息的三种方式为：

• a|a|b
• aa|b
• a|ab

最长的子串是长度为 2 的 "aa" 和 "ab"。

最小的子串数量为 2，对应分割方式 "a|ab" 或 "aa|b"。

注意，"aab" 不是一种可行的分割方式，因为字母 'a' 出现在一个长度为 3 的子串中，而 _a_1 = 2。