[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$,...,$x_N$两两互不相同(即不存在重复编号),$R_i$为$<$或$=$,”合法“是指这个图片质量序列与任何一对主观实验给出的判断不冲突。 例如: 质量序列$3 < 1 = 2$ 与主观判断”$3 > 1,3 = 2$“冲突(因为质量序列中 $3<1$ 且$1=2$,从而$3<2$,这与主观判断中的 $3=2$ 冲突;同时质量序列中的 $3<1$ 与主观判断中的 $3>1$ 冲突) ,但与主观判断”$2 = 1$,$3 < 2$“ 不冲突;因此给定主观判断”$3>1$,$3=2$“时,$1<3=2$ 和$1<2=3$ 都是合法的质量序列,$3<1=2$ 和$1<2<3$都是非法的质量序列。由于实验已经做完一段时间了,小D 已经忘了一部分主观实验的数据。对每张图片 $i$,小 D 都最多只记住了某一张质量不比 $i$ 差的另一张图片 $K_i$。这些小 D 仍然记得的质量判断一共有 $M$ 条($0 \leq M \leq N$),其中第$i$ 条涉及的图片对为$(K_{X_i}, X_i)$,判断要么是$K_{X_i} < X_i$ ,要么是$K_{X_i} = X_i$,而且所有的$X_i$互不相同。小D 打算就以这$M$ 条自己还记得的质量判断作为他的所有主观数据。 现在,基于这些主观数据,我们希望你帮小 D 求出这 N 张图片一共有多少个不同的合法质量序列。 我们规定:如果质量序列中出现”$x = y$“,那么序列中交换 $x$和$y$的位置后仍是同一个序列。因此: $1<2=3=4<5$ 和$1<4=2=3<5$ 是同一个序列, $1 < 2 = 3$ 和 $1 < 3 = 2$ 是同一个序列,而$1 < 2 < 3$ 与$1 < 2 = 3$是不同的序列,$1<2<3$和$2<1<3$ 是不同的序列。由于合法的图片质量序列可能很多, 所以你需要输出答案对$10^9 + 7$ 取模的结果

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

5

说明

不同的合法序列共5个,如下所示: ```cpp 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<=100。 ```