题目描述

给定一个边长为 $N$ 的正方形棋盘，以及 $N$ 个 L 形木块。

每个木块的两条“臂”长度相同，且所有木块的边长分别为

边长为 $L$ 的 L 形木块占据 $2L-1$ 个格子。所有木块恰好可以覆盖整个 $N\times N$ 棋盘。

棋盘行、列均从 $1$ 到 $N$ 编号，左上角为 $(1,1)$。

一个边长为 6 的完整棋盘 现在给出 $P$ 条限制。每条限制为 $(L,X,Y)$，表示边长为 $L$ 的木块的拐角必须放在格子 $(X,Y)$。木块朝向不限，只要拐角位置正确即可。

请计算满足所有限制的完整铺法数量，答案对 $10^9+7$ 取模。

输入格式

第一行包含整数 $T$，表示游戏数量。

每个游戏包含：

1. 一行整数 $N$；
2. 一行整数 $P$；
3. 接下来 $P$ 行，每行包含 $L,X,Y$。

输出格式

对每个游戏输出一行，表示合法铺法数量模 $10^9+7$。

数据范围

• $1\le T\le1000$；
• $1\le N\le200000$；
• $0\le P\le\min(100000,N)$；
• $1\le L,X,Y\le N$；
• 同一种边长的木块最多出现一条限制；
• 保证至少存在一种合法铺法；
• 所有测试用例的 $P$ 之和不超过 $100000$。

子任务

样例一

输入

3
6
2
1 6 5
4 3 2
2
0
3
1
2 2 2

输出

2
4
4

第一局有两种铺法：

第三局有四种铺法：

样例二

输入

1
40
1
7 20 20

输出

202092513