[HNOI2015]实验比较

题号：NC20113
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小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₁ R₁x₂ R₂ x₃ R₃ ...... x_N−1 R_N−1 x_N“的串，也可看作是集合

{x_iR_ix_i+1 |1<= i<=N-1}，其中 x_i为图片编号，x₁,x₂,...,x_N两两互不相同（即不存在重复编号），Ri为<或=，”合法“是指这个图片质量序列与任何一对主观实验给出的判断不冲突。

例如：质量序列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≤M≤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个，如下所示：
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% 的数据满足。