CF766C Mahmoud and a Message

Mahmoud 写下了一条长度为 $n$ 的信息 $s$。他想把它作为生日礼物送给他的朋友 Moaz，而 Moaz 喜欢字符串。他把这条信息写在了一张魔法纸上，但令他惊讶的是，写字符串时有些字符会消失。这是因为这张魔法纸不允许英文字母中第 $i$ 个字母在长度超过 $a_i$ 的字符串中出现。例如，如果 $a_1=2$，他就不能在长度为 $3$ 或以上的字符串里写下字符 'a'。字符串 "aa" 是允许的，而字符串 "aaa" 就不允许。 Mahmoud 决定把这条信息分成若干个非空的子串，这样他就可以在若干张独立的魔法纸上写下每个子串，并且满足上述条件。所有子串的长度之和应为 $n$，且它们之间不重叠。例如，如果 $a_1=2$，他要传送字符串 "aaa"，他可以拆分成 "a" 和 "aa"，用 $2$ 张魔法纸，也可以拆成 "a", "a", "a" 用 $3$ 张魔法纸。而不能拆成 "aa" 和 "aa"，因为总长度超过了 $n$。如果整个字符串满足条件，他也可以不进行拆分。 字符串 $s$ 的子串指的是由 $s$ 中若干连续字符组成的字符串，比如字符串 "abc" 的子串有 "ab", "abc", "b" 等，但 "acb", "ac" 就不是它的子串。任意字符串都是它自己的子串。 当 Mahmoud 正在思考如何拆分消息时，Ehab 告诉他有很多种拆分方式。于是 Mahmoud 问了你以下三个问题： - 有多少种方法可以将字符串拆分成若干个子串，使得每个子串都满足魔法纸的条件，子串长度之和为 $n$，且互不重叠？请计算方案数对 $10^9+7$ 取模。 - 在所有合法拆分中，可能出现的最长子串的最大长度是多少？ - 在所有合法拆分方式中，最少需要分成多少个子串？ 如果拆分的位置集合不同，则两种拆分方式被认为是不同的。例如，对消息 "aaa"，"aa|a" 和 "a|aa" 被认为是两种不同的拆分方式。

第一行包含一个整数 $n$（$1 \leq n \leq 10^3$），表示消息的长度。 第二行包含长度为 $n$ 的消息 $s$，仅由小写英文字母组成。 第三行包含 $26$ 个整数 $a_1, a_2, \ldots, a_{26}$（$1 \leq a_x \leq 10^3$），分别表示每个字母在子串中允许出现的最大长度。

输出三行。 第一行输出将消息拆分成满足条件若干子串的方案数，对 $10^9+7$ 取模。 第二行输出所有拆分方式中出现的最长子串的最大长度。 第三行输出所有拆分方式中最少的子串数。

在第一个样例中，三种拆分方式分别为： - a|a|b - aa|b - a|ab 最长的子串为 "aa" 和 "ab"，长度为 $2$。 最少的子串数是 $2$，如 "a|ab" 或 "aa|b"。 请注意 "aab" 并不是合法的拆分方式，因为字符 'a' 在子串中出现的长度为 $3$，而 $a_1=2$。 由 ChatGPT 5 翻译