#2117. 「HNOI2015」实验比较

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 D 被邀请到实验室,做一个跟图片质量评价相关的主观实验。

实验用到的图片集一共有 N 张图片,编号为 1 N 。实验分若干轮进行,在每轮实验中,小 D 会被要求观看某两张随机选取的图片, 然后小 D 需要根据他自己主观上的判断确定这两张图片谁好谁坏,或者这两张图片质量差不多。

用符号 ” < ”、“ > ” 和 “ = ” 表示图片 x y x y 为图片编号)之间的比较:如果上下文中 x y 是图片编号,则 x<y 表示图片 x 「质量优于」 y x>y 表示图片 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 < = ,「合法」是指这个图片质量序列与任何一对主观实验给出的判断不冲突。

例如: 质量序列 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 已经忘了一部分主观实验的数据。对每张图片 X_i ,小 D 都最多只记住了某一张质量不比 X_i 好的另一张图片 K_{X_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 取模的结果。

样例

样例输入

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

样例输出

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