Mahmoud 写了一条长度为 n 的消息 s。他想把它作为生日礼物送给喜欢弦乐的朋友莫阿兹。他把它写在一张神奇的纸上,但他很惊讶,因为在写字符串时有些字符消失了。那是因为这张神奇的纸不允许将英文字母中的第i个字符以长度超过ai的字符串写在上面。例如,如果a1 = 2,他就不能在这张纸上以长度为3或更长的字符串写出字符“a”。允许使用字符串“aa”,而不允许使用字符串“aaa”。
Mahmoud 决定将消息分割成一些非空子串,以便他可以将每个子串写在独立的魔法纸上并满足条件。它们的长度之和应该是n并且它们不应该重叠。例如,如果a1 = 2,他想发送字符串“aaa”,他可以将其拆分为“a”和“aa”并使用2张魔纸,或者分为“a”,“a”和“a”并使用3张魔纸。他无法将其拆分为“aa”和“aa”,因为它们的长度之和大于n。如果满足条件,他可以将消息拆分为单个字符串。
字符串 s 的子字符串是由字符串 s 中的一些连续字符组成的字符串,字符串“ab”、“abc”和“b”是字符串“abc”的子字符串,而字符串“acb”和“ac”则不是。任何字符串都是其自身的子字符串。
当 Mahmoud 思考如何分割消息时,Ehab 告诉他分割消息的方法有很多种。之后,马哈茂德问了你三个问题:
- 有多少种方法可以将字符串分割成子字符串,使得每个子字符串都满足魔纸的条件,它们的长度之和为n并且它们不重叠?以 109 + 7 为模计算答案。
- 某些有效分割中可以出现的子字符串的最大长度是多少?
- 消息中至少可以包含多少个子字符串?
如果分割位置组不同,则两种方式被认为是不同的。例如,拆分“aa|a”和“a|aa”被视为消息“aaa”的不同拆分。
输入
第一行包含一个整数 n (1 ≤ n ≤ 103),表示消息的长度。
第二行包含长度为n的消息s,由小写英文字母组成。
第三行包含 26 个整数 a1, a2, ..., a26 (1 ≤ ax ≤ 103) – 每个字母可以出现的子字符串的最大长度。
输出
打印三行。
在第一行中打印将消息拆分为子字符串并满足问题中提到的条件模 109 + 7 的方法数。
在第二行中打印所有路径中最长子字符串的长度。
在第三行中打印所有方式的最小子字符串数。
示例
输入 #1
3 aab 2 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
输出 #1
3 2 2
输入 #2
10 abcdeabcde 5 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
输出 #2
401 4 3
注意
在第一个示例中,分割消息的三种方法是:
- a|a|b
- aa|b
- a|ab
最长的子串是长度为 2 的“aa”和“ab”。
“a|ab”或“aa|b”中子字符串的最小数量为 2。
请注意,“aab”不是可能的拆分,因为字母“a”出现在长度为 3 的子字符串中,而 a1 = 2。