AT_ttpc2015_p Dancing stars on regular expression!

在这里，我们称以下结构的字符串为“正则表达式”： > $ e $ ::= $ a...a $ | ($ e_1 $+$ e_2 $) | ($ e_1 $;$ e_2 $) | \*($ e_1 $) | !($ e_1 $) 其中，$ a...a $ 表示由字符 $ a $ 连续重复一次或多次构成的字符串。 正则表达式 $ e $ 所代表的字符串集合 $ L(e) $ 可以通过下面的规则递归定义： 1. $ L(a...a)\ =\ \{a...a\} $，如 $ L(aa)\ =\ \{aa\} $, $ L(aaa)\ =\ \{aaa\} $。 2. $ L((e_1+e_2))\ =\ L(e_1)\ ∪\ L(e_2) $ 是 $ L(e_1) $ 和 $ L(e_2) $ 中任一集合中元素的合集。 3. $ L((e_1;e_2))\ =\ L(e_1)L(e_2) $，即 $ L(e_1) $ 中的字符串与 $ L(e_2) $ 中的字符串组合而成的所有字符串形成的集合。 4. $ L(*(e_1)) $ 表示 $ L(e_1) $ 中字符串的任意次数（包括零次）连接。 5. $ L(!(e_1))\ =\ Σ^*\ -\ L(e_1) $，即从所有可能字符串中除去 $ L(e_1) $ 的集合。 这里，$ Σ^* $ 是所有可能字符串的集合，形如 $ \{ε,a,aa,aaa,\ldots\} $，由 $ a $ 字符有限次重复组成。 另外，无 `!` 正则表达式表示不包含 `!` 操作符的表达式，而无 `*` 正则表达式表示不包含 `*` 操作符的表达式。 现在给你一个无 `!` 的正则表达式 $ S $，请判断是否存在一个无 `*` 的正则表达式 $ T $，使得 $ L(S) = L(T) $。

输入为以下格式： - 第一行是一个整数 $ N $ ($ 1 \leq N \leq 4000 $)，表示第二行输入的字符串 $ S $ 的长度。 - 第二行是一个无 `!` 正则表达式的字符串 $ S $。

如果存在一个无 `*` 的正则表达式 $ T $ 满足 $ L(S) = L(T) $，输出 `YES`；否则，输出 `NO`。 ### 数据范围与提示 - 示例 1：可以选择 $ T = (a+aa) $ 作为答案。 - 示例 2：可以选择 $ T = (!(a)+a) $ 作为答案。 - 示例 3：不存在符合 $ L(S) = L(T) $ 的无 `*` 正则表达式 $ T $。 **本翻译由 AI 自动生成**

### Sample Explanation 1 $ T\ =\ (a+aa) $ とすればよい。 ### Sample Explanation 2 $ T\ =\ (!(a)+a) $ とすればよい。 ### Sample Explanation 3 $ L(S)\ =\ L(T) $ を満たす \\\*なし正規表現 $ T $ は存在しません。