P3240 [HNOI2015] 实验比较

小 D 被邀请到实验室，做一个跟图片质量评价相关的主观实验。 实验用到的图片集一共有 $N$ 张图片，编号为 $1$ 到 $N$。实验分若干轮进行，在每轮实验中，小 D 会被要求观看某两张随机选取的图片， 然后小 D 需要根据他自己主观上的判断确定这两张图片谁好谁坏，或者这两张图片质量差不多。 用符号 ”$$” 和 “$=$” 表示图片 $x$ 和 $y$（$x$、$y$ 为图片编号）之间的比较：如果上下文中 $x$ 和 $y$ 是图片编号，则 $xy$ 表示图片 $x$「质量差于」$y$，$x=y$ 表示图片 $x$ 和 $y$ 「质量相同」；也就是说，这种上下文中，“$$”、“$=$” 分别是质量优于、质量差于、质量相同的意思；在其他上下文中，这三个符号分别是小于、大于、等于的含义。 图片质量比较的推理规则（在 $x$ 和 $y$ 是图片编号的上下文中）： 1. $x < y$ 等价于 $y > x$。 2. 若 $x < y$ 且 $y = z$，则 $x < z$。 3. 若 $x < y$ 且 $x = z$，则 $z < y$。 4. $x=y$ 等价于 $y=x$。 5. 若 $x=y$ 且 $y=z$，则 $x=z$。 实验中，小 D 需要对一些图片对 $(x, y)$，给出 $x < y$ 或 $x = y$ 或 $x > y$ 的主观判断。小 D 在做完实验后， 忽然对这个基于局部比较的实验的一些全局性质产生了兴趣。 在主观实验数据给定的情形下，定义这 $N$ 张图片的一个合法质量序列为形如 “$x_1 R_1 x_2 R_2 x_3 R_3 …x_{N-1} R_{N-1} x_N$” 的串，也可看作是集合 $\{ x_i R_i x_{i+1}|1 \leq i \leq N-1 \}$，其中 $x_i$ 为图片编号，$x_1,x_2, \ldots ,x_N$ 两两互不相同（即不存在重复编号），$R_i$ 为 $ 1$，$3 = 2$” 冲突（因为质量序列中 $3

第一行两个正整数 $N,M$，分别代表图片总数和小 $D$ 仍然记得的判断的条数； 接下来 $M$ 行，每行一条判断，每条判断形如「$x < y$」或者「$x = y$」。

输出仅一行，包含一个正整数，表示合法质量序列的数目对 $10^9+7$ 取模的结果。

不同的合法序列共5个，如下所示： - $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$ $100\%$ 的数据满足 $N \leq 100$。