E-小y的容器_牛客练习赛96

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

题目描述

求将 $1-n$ 这 $n$ 个数放入三个容器中使得容器中的数排序以后相邻两个之差小于等于 $3$ 的方案数（要保证任意容器中至少有一个数且每个数必须放入一个容器中）

例如某个容器中的数若是 $[3,5,6]$ 则是合法的，若是 $[1,5,6]$ 则不合法，原因是 $1,5$ 的差超过了 $3$

其中有 $m$ 个限制 $x,y$ 代表 $x$ 不能放在 $y$ 这个容器中，答案对 $10^9+7$ 取模

两个方案不同当且仅当两个方案中至少有一个数所在的容器不同

第一行两个正整数

接下来行每行个数

输出一行一个数代表答案

示例1

复制

4 1
1 2

复制

对于样例[1][2][3,4]是一种合法方案,[1,2][3,4][]是不合法的，因为出现了空的序列，[2][1,3][4]是不合法的，因为1不能放在第二个容器中

示例2

复制

复制