Little D has been invited to a laboratory to conduct a subjective experiment related to image quality evaluation. The image set used in the experiment contains a total of $N$ images, numbered from $1$ to $N$. The experiment is conducted in several rounds. In each round, Little D is asked to view two randomly selected images, and then Little D needs to determine, based on his own subjective judgment, which of the two images is better or worse, or if the two images have similar quality.

We use the symbols "$<$", "$>$", and "$=$" to represent the comparison between image $x$ and $y$ ($x, y$ are image numbers): if $x$ and $y$ are image numbers in the context, then $x < y$ means image $x$ is "better in quality than" $y$, $x > y$ means image $x$ is "worse in quality than" $y$, and $x = y$ means image $x$ and $y$ have "the same quality"; that is to say, in this context, "$<$", "$>$", and "$=$" mean better in quality than, worse in quality than, and same in quality, respectively; in other contexts, these three symbols have the meanings of less than, greater than, and equal to. The inference rules for image quality comparison (in the context where $x$ and $y$ are image numbers) are: (1) $x < y$ is equivalent to $y > x$. (2) If $x < y$ and $y = z$, then $x < z$. (3) If $x < y$ and $x = z$, then $z < y$. (4) $x = y$ is equivalent to $y = x$. (5) If $x = y$ and $y = z$, then $x = z$.

In the experiment, Little D needs to provide subjective judgments of $x < y$, $x = y$, or $x > y$ for some image pairs $(x, y)$.

After finishing the experiment, Little D suddenly became interested in some global properties of this experiment based on local comparisons. Given the subjective experimental data, a valid quality sequence for these $N$ images is defined as a string of the form "$x_1 R_1 x_2 R_2 x_3 R_3 \dots x_{N-1} R_{N-1} x_N$", which can also be viewed as the set $\{ x_i R_i x_{i+1} \mid 1 \le i \le N-1 \}$, where $x_i$ are image numbers, $x_1, x_2, \dots, x_N$ are all distinct (i.e., there are no duplicate numbers), and $R_i$ is either $<$ or $=$. "Valid" means that this image quality sequence does not conflict with any subjective judgment given in the experiment. For example: the quality sequence $3 < 1 = 2$ conflicts with the subjective judgment "$3 > 1, 3 = 2$" (because in the quality sequence $3 < 1$ and $1 = 2$, thus $3 < 2$, which conflicts with $3 = 2$ in the subjective judgment; at the same time, $3 < 1$ in the quality sequence conflicts with $3 > 1$ in the subjective judgment), but it does not conflict with the subjective judgment "$2 = 1, 3 < 2$". Therefore, given the subjective judgment "$3 > 1, 3 = 2$", $1 < 3 = 2$ and $1 < 2 = 3$ are both valid quality sequences, while $3 < 1 = 2$ and $1 < 2 < 3$ are both invalid quality sequences.

Since the experiment has been over for some time, Little D has forgotten some of the subjective experimental data. For each image $i$, Little D remembers at most one other image $K_i$ that is not worse in quality than $i$. There are $M$ such quality judgments that Little D still remembers ($0 \le M \le N$), where the $i$-th judgment involves the image pair $(K_{X_i}, X_i)$, and the judgment is either $K_{X_i} < X_i$ or $K_{X_i} = X_i$, and all $X_i$ are distinct. Little D intends to use these $M$ quality judgments he still remembers as all of his subjective data. Now, based on this subjective data, we want you to help Little D find out how many different valid quality sequences there are for these $N$ images. We stipulate: if "$x = y$" appears in a quality sequence, then the sequence remains the same after swapping the positions of $x$ and $y$. Therefore: $1 < 2 = 3 = 4 < 5$ and $1 < 4 = 2 = 3 < 5$ are the same sequence, $1 < 2 = 3$ and $1 < 3 = 2$ are the same sequence, while $1 < 2 < 3$ and $1 < 2 = 3$ are different sequences, and $1 < 2 < 3$ and $2 < 1 < 3$ are different sequences.

Since there may be many valid image quality sequences, you only need to output the answer modulo $10^9 + 7$.

Input

The input file is named pairwise.in. The first line contains two positive integers $N, M$, representing the total number of images and the number of judgments Little D still remembers, respectively. The next $M$ lines each contain one judgment, each in the form of "$x < y$" or "$x = y$".

Output

The output file is named pairwise.out. Output a single line containing a positive integer, representing the number of valid quality sequences modulo $10^9 + 7$.

Examples

Input 1

5 4
1 < 2
1 < 3
2 < 4
1 = 5

Output 1

5

Note

There are 5 different valid sequences, as follows: $1 = 5 < 2 < 3 < 4$ $1 = 5 < 2 < 4 < 3$ $1 = 5 < 2 < 3 = 4$ $1 = 5 < 3 < 2 < 4$ $1 = 5 < 2 = 3 < 4$

Constraints

$30\%$ of the data satisfies $N \le 10$; $70\%$ of the data satisfies $N \le 50$; $100\%$ of the data satisfies $N \le 100$.