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

小 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\dots x_{N-1}{R}_{N-1}{x}_N$” 的串，也可看作是集合 {xiRixi+1∣1≤i≤N−1}\{ x_i R_i x_{i+1}|1 \leq i \leq N-1 \}{x​i​​R​i​​x​i+1​​∣1≤i≤N−1}，其中 xix_ix​i​​ 为图片编号，x1,x2,…,xNx_1,x_2, \ldots ,x_Nx​1​​,x​2​​,…,x​N​​ 两两互不相同（即不存在重复编号），RiR_iR​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 已经忘了一部分主观实验的数据。对每张图片 XiX_iX​i​​，小 D 都最多只记住了某一张质量不比 XiX_iX​i​​ 好的另一张图片 KXiK_{X_i}K​X​i​​​​。这些小 D 仍然记得的质量判断一共有 $M$ 条（$0\le M\le N$），其中第 $i$ 条涉及的图片对为 (KXi,Xi)(K_{X_i}, X_i)(K​X​i​​​​,X​i​​)，判断要么是 KXi<XiK_{X_i} < X_iK​X​i​​​​<X​i​​，要么是 KXi=XiK_{X_i} = X_iK​X​i​​​​=X​i​​，而且所有的 XiX_iX​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$ 是不同的序列。

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