AT_ttpc2015_p Dancing stars on regular expression!

[problemUrl]: https://atcoder.jp/contests/ttpc2015/tasks/ttpc2015_p ここでは、以下の構文で表される文字列を "正規表現" と呼ぶ。 > $ e $ ::= $ a...a $ | ($ e_1 $+$ e_2 $) | ($ e_1 $;$ e_2 $) | \*($ e_1 $) | !($ e_1 $) ただし、$ a...a $ は 文字 $ a $ の $ 1 $ 回以上の繰り返しによって表せるようなある文字列を表す。 正規表現 $ e $ が表現する文字列の集合 $ L(e) $ は以下で帰納的に定義される。 > $ L(a...a)\ =\ \{a...a\} $ - 例えば、$ L(aa)\ =\ \{aa\} $, $ L(aaa)\ =\ \{aaa\} $。 $ L((e_1+e_2))\ =\ L(e_1)\ ∪\ L(e_2) $ - $ L(e_1) $ に属する または $ L(e_2) $ に属する 文字列 の集合。 $ L((e_1;e_2))\ =\ L(e_1)L(e_2)\ =\ \{\ w_1\ w_2\ |\ w_1\ \in\ L(e_1),\ w_2\ \in\ L(e_2)\ \} $ - $ L(e_1) $ に属する文字列 と $ L(e_2) $ に属する文字列 をつなげた文字列の集合。 $ L(*(e_1))\ =\ L(e_1)^*\ =\ \{ε\}\ ∪\ \{w_1\ |\ w_1\ \in\ L(e_1)\}\ ∪\ ...\ ∪\ \{w_1\ ...\ w_n\ |\ w_1,...,w_n\ \in\ L(e_1)\}\ ∪\ ... $ - $ L(e_1) $ に属する文字列 を 有限回つなげた ($ 0 $ 回の場合も含む) 文字列の集合。 $ L(!(e_1))\ =\ Σ^*\ -\ L(e_1) $ - $ L(e_1) $ に属さない文字列 の集合。 ただし、$ Σ^* $ は文字列の全体集合 $ \{ε(空の文字列),a,aa,aaa,...\}\ =\ ( $a$ を有限個つなげた文字列の集合) $ を表す。 また、以下の文中で"!なし正規表現" とは `!` が出現しない 正規表現 を指し、 "\*なし正規表現" とは `*` が出現しない 正規表現 を指します。 さて、!なし正規表現 $ S $ が与えられます。 $ L(S)\ =\ L(T) $ を満たす \*なし正規表現 $ T $ が存在するかどうか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $ - $ 1 $ 行目には、$ 2 $ 行目に入力される $ S $ の文字列の長さ $ N $($ 1\ ≦\ N\ ≦\ 4000 $) が与えられる。 - $ 2 $ 行目には、ある !なし正規表現 を表す文字列 $ S $ が与えられる。

$ L(S)\ =\ L(T) $ を満たす \*なし正規表現 $ T $ が存在する場合、 `YES` を出力してください。 $ L(S)\ =\ L(T) $ を満たす \*なし正規表現 $ T $ が存在しない場合、 `NO` を出力してください。

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