Problem Description

Here, a string represented by the following syntax is called a "regular expression".

$ e $ ::= $ a...a $ | ($ e_1 $+$ e_2 $) | ($ e_1 $;$ e_2 $) | *($ e_1 $) | !($ e_1 $)

Where $ a...a $ represents some string that can be expressed by repeating the character $ a $ one or more times.

The set of strings represented by the regular expression $ e $, denoted as $ L(e) $, is defined inductively as follows:

$L(a...a)\ =\ \{a...a\}$ - For example, $L(aa)\ =\ \{aa\}$, $L(aaa)\ =\ \{aaa\}$. $L((e_1+e_2))\ =\ L(e_1)\ ∪\ L(e_2)$ - The set of strings belonging to either $ L(e_1) $ or $ 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)\ \}$ - The set of strings formed by concatenating a string from $ L(e_1) $ with a string from $ 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)\}\ ∪\ ...$ - The set of strings formed by concatenating strings from $ L(e_1) $ a finite number of times (including zero times). $L(!(e_1))\ =\ Σ^*\ -\ L(e_1)$ - The set of strings not belonging to $ L(e_1) $.

Where $ Σ^* $ represents the entire set of strings $\{ε(empty string),a,aa,aaa,...\}\ =\ (the set of strings formed by concatenating a$ a $'s).

In the following text, a "no-! regular expression" refers to a regular expression that does not contain !, and a "no-* regular expression" refers to a regular expression that does not contain *.

Now, you are given a no-! regular expression $ S $.

Determine whether there exists a no-* regular expression $ T $ such that $L(S)\ =\ L(T)$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

• The first line contains the length of the string $ S $ ($1\ ≦\ N\ ≦\ 4000$).
• The second line contains a string $ S $ representing a no-! regular expression.

Output Format

If there exists a no-* regular expression $ T $ such that $L(S)\ =\ L(T)$, output YES.

If there does not exist a no-* regular expression $ T $ such that $L(S)\ =\ L(T)$, output NO.

Sample Input and Output

Sample Input #1

6
(a+aa)

Sample Output #1

YES

Sample Input #2

17
(*(aa)+(*(aa);a))

Sample Output #2

YES

Sample Input #3

14
(*(aa)+*(aaa))

Sample Output #3

NO

Notes/Hints

Sample Explanation 1

$T\ =\ (a+aa)$ is sufficient.

Sample Explanation 2

$T\ =\ (!(a)+a)$ is sufficient.

Sample Explanation 3

There is no no-* regular expression $ T $ that satisfies $L(S)\ =\ L(T)$.

见题面 Input 部分

见题面 Output 部分