Problem1064--#2117. 「HNOI2015」实验比较

1064: #2117. 「HNOI2015」实验比较

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

用符号 ”<<<”、“>>>” 和 “===” 表示图片 xxxyyyxxxyyy 为图片编号)之间的比较:如果上下文中 xxxyyy 是图片编号,则 x<yx<yx<y 表示图片 xxx「质量优于」yyyx>yx>yx>y 表示图片 xxx「质量差于」yyyx=yx=yx=y 表示图片 xxxyyy 「质量相同」;也就是说,这种上下文中,“<<<”、“>>>”、“===” 分别是质量优于、质量差于、质量相同的意思;在其他上下文中,这三个符号分别是小于、大于、等于的含义。

图片质量比较的推理规则(在 xxxyyy 是图片编号的上下文中):

  1. x<yx < yx<y 等价于 y>xy > xy>x
  2. x<yx < yx<yy=zy = zy=z,则 x<zx < zx<z
  3. x<yx < yx<yx=zx = zx=z,则 z<yz < yz<y
  4. x=yx=yx=y 等价于 y=xy=xy=x
  5. x=yx=yx=yy=zy=zy=z,则 x=zx=zx=z

实验中,小 D 需要对一些图片对 (x,y)(x, y)(x,y),给出 x<yx < yx<yx=yx = yx=yx>yx > yx>y 的主观判断。小 D 在做完实验后, 忽然对这个基于局部比较的实验的一些全局性质产生了兴趣。

在主观实验数据给定的情形下,定义这 NNN 张图片的一个合法质量序列为形如 “x1R1x2R2x3R3xN1RN1xN” 的串,也可看作是集合 {xiRixi+1∣1≤i≤N−1}\{ x_i R_i x_{i+1}|1 \leq i \leq N-1 \}{xiRixi+11iN1},其中 xix_ixi 为图片编号,x1,x2,…,xNx_1,x_2, \ldots ,x_Nx1,x2,,xN 两两互不相同(即不存在重复编号),RiR_iRi<<<===,「合法」是指这个图片质量序列与任何一对主观实验给出的判断不冲突。

例如: 质量序列 3<1=23 < 1 = 23<1=2 与主观判断 “3>13 > 13>13=23 = 23=2” 冲突(因为质量序列中 3<13<13<11=21=21=2,从而 3<23<23<2,这与主观判断中的 3=23=23=2 冲突;同时质量序列中的 3<13<13<1 与主观判断中的 3>13>13>1 冲突) ,但与主观判断 “2=12 = 12=13<23 < 23<2” 不冲突;因此给定主观判断 “3>13>13>13=23=23=2” 时,1<3=21<3=21<3=21<2=31<2=31<2=3 都是合法的质量序列,3<1=23<1=23<1=21<2<31<2<31<2<3 都是非法的质量序列。

由于实验已经做完一段时间了,小 D 已经忘了一部分主观实验的数据。对每张图片 XiX_iXi,小 D 都最多只记住了某一张质量不比 XiX_iXi 好的另一张图片 KXiK_{X_i}KXi。这些小 D 仍然记得的质量判断一共有 MMM 条(0≤M≤N0 \leq M \leq N0MN),其中第 iii 条涉及的图片对为 (KXi,Xi)(K_{X_i}, X_i)(KXi,Xi),判断要么是 KXi<XiK_{X_i} < X_iKXi<Xi,要么是 KXi=XiK_{X_i} = X_iKXi=Xi,而且所有的 XiX_iXi 互不相同。小 D 打算就以这 M 条自己还记得的质量判断作为他的所有主观数据。

现在,基于这些主观数据,我们希望你帮小 D 求出这 NNN 张图片一共有多少个不同的合法质量序列。我们规定:如果质量序列中出现 “x=yx = yx=y”,那么序列中交换 xxxyyy 的位置后仍是同一个序列。因此: 1<2=3=4<51<2=3=4<51<2=3=4<51<4=2=3<51<4=2=3<51<4=2=3<5 是同一个序列, 1<2=31 < 2 = 31<2=31<3=21 < 3 = 21<3=2 是同一个序列,而 1<2<31 < 2 < 31<2<31<2=31 < 2 = 31<2=3 是不同的序列,1<2<31<2<31<2<32<1<32<1<32<1<3 是不同的序列。

由于合法的图片质量序列可能很多, 所以你需要输出答案对 109+710^9 + 7109+7 取模的结果

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

5

数据范围与提示

不同的合法序列共五个,如下所示:

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

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

Source/Category