题目描述

有 $3N$ 名编号为 $1\sim3N$ 的学生，要把他们划分为 $N$ 支三人队。队伍之间无序，每支队伍内部成员也无序。

给出 $K$ 个“禁止三元组”。除这些三元组外，任意三名学生都可以组成一支合格队伍。

求有多少种划分方式，使得划分中的每一支队伍都不是禁止三元组。

输入格式

第一行两个整数 $N,K$，其中 $1\le N\le1000$，$0\le K\le20$。

接下来 $K$ 行，每行三个互不相同的整数 $a_i,b_i,c_i$，范围为 $1\sim3N$。所有禁止三元组两两不同（按集合意义）。

输出格式

输出合法划分方案数的完整十进制表示，不含前导零。

样例 1

2 0

10

样例 2

2 3
1 2 3
4 5 6
1 4 5

8