背景

2024 年 5 月 18 日，随着最后一发通信题的提交出现了 Wrong Answer，小 Z 的 APIO 比赛结束了，也意味着他在 OI 生涯中又一次打铁。

痛定思痛，小 Z 决定批量生产通信题给自己做。如何批量生产通信题？只要要求 Alice 通过一种奇奇怪怪的方法发送一个正整数 $X$ 给 Bob，中间还会遇到各种奇奇怪怪的篡改，要求 Bob 还原 $X$，这样就能批量生产通信题了！

那为什么这题并不是通信题呢。

题目描述

这不是一道通信题。

Alice 和 Bob 是著名的魔术师。Catherine 是一位富豪，她非常喜欢观看 Alice 和 Bob 的魔术。某一天，Catherine 决定向 Alice 和 Bob 发出挑战：只要他们能成功表演如下的魔术，Catherine 就将向他们提供巨额奖金！这个魔术的表演过程如下：

• 步骤 $1$：Catherine 告诉 Alice 和 Bob 两个正整数 $n$ 和 $k$，以及两个区间序列 $I_1,I_2,\dots,I_k$，$J_1,J_2,\dots,J_k$。其中 $I_i=[A_i,B_i],J_i=[C_i,D_i]$，它们满足：

  • $1\le A_i\le B_i\le n$，$1\le C_i\le D_i\le n$；
  • $I_1,\dots,I_k$ 两两不交；
  • $J_1,\dots,J_k$ 两两不交；
  • 对任意 $i\ne j$，$I_i\cap J_j=\varnothing$。

  也就是说，每个 $I_i$ 仅可能与同下标的 $J_i$ 有交。

• 步骤 $2$：Alice 公开告诉 Catherine 和 Bob 一个正整数 $m$。Bob 知道 $n,k,I,J,m$。随后 Bob 进入密室，在魔术全程中只能通过 Catherine 获取信息。

• 步骤 $3$：Catherine 告诉 Alice 一个在 $1$ 到 $m$ 之间的整数 $X$。

• 步骤 $4$：Alice 生成一个集合 $S$，其中每个元素都是 $1,2,\dots,n$ 的一个排列。$S$ 可以为空集。Alice 把 $S$ 告诉 Catherine。

• 步骤 $5$：Catherine 可重复任意次以下操作，包括 $0$ 次：

  • 从当前集合 $S$ 中任选一个排列 $p$；
  • 选择 $U=A,V=B$ 或 $U=C,V=D$；
  • 对于 $i=1,2,\dots,k$，将排列 $p$ 的区间 $[U_i,V_i]$ 前后翻转，得到新排列 $p'$，并用 $p'$ 替换集合 $S$ 中的排列 $p$；
  • 将集合 $S$ 去重。

  最后将最终的 $S$ 打乱后告诉 Bob。

• 步骤 $6$：Bob 根据 Catherine 给出的信息，猜出 Catherine 告诉 Alice 的数 $X$ 是多少。

然而，Alice 和 Bob 被这个魔术难倒了，于是他们不得不寻求你的帮助。请你写一段程序，计算出在 Alice 得知 $n,k,I,J$ 后，在保证一定拿到这笔奖金的情况下，最大能报出的 $m$ 是多少。我们可以证明，这个最大的 $m$ 一定可以被表示为 $\sqrt[L]{2^{n!}}$ 的形式，其中 $L$ 是一个正整数。你只需要输出 $L$ 模 $10^9+7$ 的值。

输入格式

第一行读入两个整数 $c,T$，分别表示测试点编号、测试数据组数。特殊地，样例的编号为 $0$。

接下来读入 $T$ 组数据，对于每组数据：

第一行读入两个正整数 $n,k$，分别表示 Catherine 告诉 Alice 和 Bob 的两个数。

接下来 $k$ 行，每行四个正整数，分别表示 $A_i,B_i,C_i,D_i$。

输出格式

对于每组数据，输出一个整数，表示对应的 $L$ 模 $10^9+7$ 的值。

0 1
2 1
1 1 2 2

1

0 1
2 1
1 2 2 2

2

0 1
560700 1
3 560600 1 560699

133656720

提示

样例 1 解释

由于 $A_1=B_1,C_1=D_1$，单点前后翻转等于什么都没干。相当于 Catherine 不会进行混淆操作，仅仅只会将集合打乱并去重。那么此时 Bob 收到的信息有四种情况：$\{\},\{\{1,2\}\},\{\{2,1\}\},\{\{1,2\},\{2,1\}\}$，每种分别代表一种数字，那么 $m=4=\sqrt[1]{2^{2!}}$，故 $L=1$。

样例 2 解释

考虑如下通信构造手段：Bob 收到的集合 $S$ 是否为空，若为空即为 $1$，否则为 $2$，所以 $m=2=\sqrt[2]{2^{2!}}$，故 $L=2$。

数据范围

对于 $100\%$ 的数据，满足：

• $0\le T\le 10$；
• $1\le n\le 10^{12}$；
• $1\le k\le 50$；
• $\sum k\le 50$；
• $1\le A_i\le B_i\le n$；
• $1\le C_i\le D_i\le n$；
• $I_1,\dots,I_k$ 两两不交；
• $J_1,\dots,J_k$ 两两不交；
• 对任意 $i\ne j$，$I_i\cap J_j=\varnothing$。