Description

Little D was invited to a lab to participate in a subjective experiment related to image quality assessment.

The dataset contains $N$ images, numbered $1$ to $N$. The experiment is conducted in several rounds. In each round, Little D is asked to look at two randomly selected images, and then, based on his subjective judgment, decide which image is better, or that their qualities are about the same.

We use the symbols “$<$”, “$>$”, and “$=$” to denote comparisons between images $x$ and $y$ ($x$, $y$ are image indices): if within the context $x$ and $y$ are image indices, then $x < y$ means “the quality of image $x$ is better than that of $y$,” $x > y$ means “the quality of image $x$ is worse than that of $y$,” and $x = y$ means “images $x$ and $y$ have equal quality.” That is, in such contexts, “$<$”, “$>$”, and “$=$” respectively mean better quality, worse quality, and equal quality; in other contexts, these three symbols retain their usual meanings of less than, greater than, and equal to.

Reasoning rules for image quality comparisons (in the context where $x$ and $y$ are image indices):

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 a subjective judgment for some image pairs $(x, y)$: either $x < y$, or $x = y$, or $x > y$. After the experiment, Little D became interested in some global properties of this locally compared experiment.

Given the subjective experiment data, we define a legal quality sequence of these $N$ images 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 regarded as the set $\{ x_i R_i x_{i+1} \mid 1 \leq i \leq N - 1 \}$, where $x_i$ are image indices, $x_1, x_2, \ldots, x_N$ are pairwise distinct (i.e., no duplicate indices), $R_i$ is either $<$ or $=$, and “legal” means that this quality sequence does not conflict with any of the subjective judgments.

For example: the quality sequence $3 < 1 = 2$ conflicts with the subjective judgments “$3 > 1$, $3 = 2$” (because in the sequence $3 < 1$ and $1 = 2$, hence $3 < 2$, which conflicts with $3 = 2$ in the judgments; meanwhile $3 < 1$ conflicts with $3 > 1$), but it does not conflict with the judgments “$2 = 1$, $3 < 2$.” Therefore, given the judgments “$3 > 1$, $3 = 2$,” both $1 < 3 = 2$ and $1 < 2 = 3$ are legal quality sequences, while $3 < 1 = 2$ and $1 < 2 < 3$ are illegal quality sequences.

Since some time has passed since the experiment, Little D has forgotten part of the subjective data. For each image $X_i$, Little D remembers at most one other image $K_{X_i}$ whose quality is not better than $X_i$. Altogether there are $M$ remembered judgments ($0 \leq M \leq N$). The $i$-th judgment involves the pair $(K_{X_i}, X_i)$ and is either $K_{X_i} < X_i$ or $K_{X_i} = X_i$, and all $X_i$ are pairwise distinct. Little D decides to use precisely these $M$ remembered judgments as all his subjective data.

Now, based on these subjective data, we ask you to help Little D compute how many different legal quality sequences there are for the $N$ images. We stipulate: if “$x = y$” appears in a sequence, then swapping the positions of $x$ and $y$ results in the same sequence. 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, whereas $1 < 2 < 3$ and $1 < 2 = 3$ are different sequences, and $1 < 2 < 3$ and $2 < 1 < 3$ are different sequences.

As the number of legal quality sequences can be large, you must output the answer modulo $10^9 + 7$.

Input Format

The first line contains two positive integers $N, M$, the total number of images and the number of judgments that Little D still remembers.

The following $M$ lines each contain one judgment, in the form “$x < y$” or “$x = y$”.

Output Format

Output a single line containing one positive integer, the number of legal quality sequences modulo $10^9 + 7$.

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

5

Hint

There are 5 different legal sequences, as listed below:

• $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$

For $100\%$ of the testdata, $N \leq 100$.

Translated by ChatGPT 5