Counting Legal Quality Sequences

In a laboratory experiment on image quality evaluation, there are N images numbered from 1 to N. In the experiment, several rounds are conducted. In each round, two images (chosen at random) are shown and the subject (named D) is asked to decide which image is of higher quality, or whether they are of similar quality. In the experiment, we use the symbols \( \) and \( = \) in the following way in the context of image comparisons: If \(x\) and \(y\) denote image numbers then x<y means "image \(x\) is of better quality than image \(y\)"; x>y means "image \(x\) is of worse quality than image \(y\)"; and x=y means the two images have the same quality. (In other contexts these symbols have their usual meanings.)

After the experiment, D only remembers at most one quality judgment per image. For each image \(X_i\) that he remembers, he recalls a comparison between some image \(K_{X_i}\) and \(X_i\). The remembered judgment is either \(K_{X_i} < X_i\) or \(K_{X_i} = X_i\). Moreover, all the \(X_i\) are distinct. D now decides to use these M remembered judgments (\(0 \le M \le N\)) as his entire data.

A legal quality sequence is defined as an expression of the form \[ x_1 \;R_1\; x_2 \;R_2\; x_3 \;R_3 \; \cdots \;R_{N-1}\; x_N, \] where \(x_1,x_2,\dots,x_N\) is a permutation of \(\{1,2,\dots,N\}\) and each \(R_i\) is either \( < \) or \( = \). It can also be viewed as the set \[ \{ x_i \;R_i\; x_{i+1} \mid 1 \le i \le N-1\}. \] The sequence is legal if its implied pairwise relations (augmented by the following inference rules below) do not conflict with any of the remembered judgments. In the context where numbers denote image IDs, the inference rules are:

1. \(xx\).
2. If \(x<y\) and \(y=z\), then \(x<z\).
3. If \(x<y\) and \(x=z\), then \(z<y\).
4. \(x=y\) is symmetric.
5. If \(x=y\) and \(y=z\), then \(x=z\).

Note that if a sequence contains an equality (say, \(x=y\)), then any reordering of \(x\) and \(y\) in that block is considered the same sequence. For example, the sequences 1<2=3=4<5 and 1<4=2=3<5 are considered identical; however, 1<2<3 and 1<2=3 are different.

Given the M remembered judgments, count how many different legal quality sequences exist (modulo \(10^9+7\)).

Input constraints and details:

• The first line contains two integers \(N\) and \(M\) \( (1 \le N \le \text{small},\; 0 \le M \le N)\).
• Each of the next M lines contains a judgment in the format: K X R, where K and X are image numbers (with \(1 \le K,X \le N\)) and R is either < or =. Here, a judgment K X < means that D remembers that image K is not better than image X (i.e. in the legal sequence, it must appear that K is of higher quality than X after interpreting the symbols appropriately) and K X = means the two images have the same quality.
• It is guaranteed that all X in the memory judgments are distinct.

Note: Although without any constraints the number of legal sequences is given by the Fubini numbers (ordered Bell numbers), here additional remembered judgments force certain images to be equal or to appear in a given order. In particular, if a remembered judgment forces x=y, the images must appear in the same block; if it forces x<y (which, by symmetry, also covers the case originally given as x>y), the images must be in distinct blocks with the correct relative order. Your task is to count, modulo \(10^9+7\), how many legal quality sequences exist that do not conflict with the remembered data.

inputFormat

The first line contains two integers N and M, representing the number of images and the number of remembered judgments respectively.

Each of the next M lines contains a judgment in the format:

K X R

where K and X are integers (image numbers) and R is a character that is either < or =. (Remember that a judgment K X < means that image K is considered to be of higher quality than image X after interpreting the symbols appropriately. Also, all the X values are distinct.)

outputFormat

Output a single integer — the number of legal quality sequences that are consistent with the remembered data, modulo \(10^9+7\).

sample

3 2
1 3 <
3 2 =

1