P17439 魔术表演

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$ 的值。

**样例 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$。 | 测试点编号 | 特殊限制 | 测试点编号 | 特殊限制 | |---|---|---|---| | $1$ | $T=1,n=5,k=1$，且数据下发 | $11$ | $T=1,n=2\times 10^9,k=1$，且数据下发 | | $2$ | $T=1,n=10,k=1$，且数据下发 | $12$ | $T=1,n=2\times 10^9,k=1$，且数据下发 | | $3$ | $\forall i,\ I_i\cap J_i=\varnothing$ | $13$ | $k=1,\ A_1=1,\ D_1=n$ | | $4$ | $\forall i,\ I_i\cap J_i=\varnothing,\ A_i=B_i$ | $14$ | $k=1,\ A_1=1,\ D_1=n$ | | $5$ | $\forall i,\ A_i=B_i,\ C_i=D_i$ | $15$ | $k=1,\ A_1=1,\ D_1=n$ | | $6$ | $n\le 10^3$ | $16$ | $k=1,\ A_1=1,\ B_1=n$ | | $7$ | $n\le 10^3$ | $17$ | $k=1,\ A_1=1,\ B_1=n$ | | $8$ | $n\le 10^5$ | $18$ | $k=1,\ A_1=1,\ B_1=n$ | | $9$ | $n\le 5\times 10^6$ | $19$ | 无特殊限制 | | $10$ | $T=1,n=2\times 10^9,k=1$，且数据下发 | $20$ | 无特殊限制 |