Problem Description

This problem is about two very common functions $~min(a, b)~$ and $~max(a, b)~$, the function $~min(a, b)~$ returns the smaller of $~a~$ and $~b~$, and function $~max(a, b)~$ returns the bigger one.

Now, you are given a permutation $a_1, a_2,...,a_n$, and $~m~$ expressions, the $~ith~$ expression will one of the follows

1. $b_i = min(X, Y)$
2. $b_i = max(X, Y)$

Where $~X~$, $~Y~$ can be $~a_j(1 \leq j \leq n)~$ or $~b_j(1 \leq j <i)~$.
And the questions is, if we randomly choose permutation $a_1, a_2,...,a_n$ with equal probability, what is the expected value of $~b_m~$.

Input

The input data contains server test case(end with EOF), for each test case
The first line contain two integer $~n~$ and $~m~$. ($2 \leq n \leq 15, 1 \leq m \leq 1000$)
Then following $~m~$ lines, the $ith$ line describe the right side of the $~ith~$ expression(note that the left side is always be $~b_i=~$), and is one of the follows:
1. $min\, tp_0\, id_0\, tp_1\, id_1$
2. $max\, tp_0\, id_0\, tp_1\, id_1$
The pair $(tp, id)$ describe one variable, if tp is 'a', then it means $~a_{id}~$, else tp will be 'b', and it means $~b_{id}~$

Output

One line contain one integer $E[b_m] \times n!$, it can be prove, that the result always be an integer.

3 2
max a 2 a 3
min a 1 b 1
3 2
max a 2 a 3
max a 1 b 1

10
18