ZYB 是个聪明人。他正在研究一个关于二进制数的问题。

令 $a_i$ 为 $a$ 的二进制表示中第 $i$ 位（从 0 开始索引）的最低有效位。例如，如果 $a = 2$，则 $a_0 = 0, a_1 = 1$，且对于 $i \ge 2$，$a_i = 0$。定义 $F_k(a, b)$ 为：

$$ F_k(a, b) = \begin{cases} F_{k-1}(a, b) + 1 & (a_k = b_k) \\ 0 & (a_k \neq b_k) \end{cases} $$

特别地，$F_{-1}(a, b) = 0$。

ZYB 有 $N$ 个区间 $[L_1, R_1], [L_2, R_2], \dots, [L_n, R_n]$，其中 $L_1 = 0, R_n = 2^m - 1$，且对于所有 $i \in [1, n - 1]$，满足 $R_i + 1 = L_{i+1}$。他想要选择 $N$ 个整数 $A_1, A_2, \dots, A_n$，使得 $A_i \in [L_i, R_i]$，并且对于每个 $i \in [1, n]$，满足以下条件：

$$\forall k \in [L_i, R_i] : F_{m-1}(A_i, k) \ge \max_{1 \le j \le N} \{F_{m-1}(A_j, k)\}$$

序列 $A$ 的值定义为 $V(A) = \prod_{i=1}^n A_i$。

当然，选择序列 $A$ 的方式有多种。现在 ZYB 想知道在他能选择的所有不同序列中，$V(A)$ 的总和是多少。两个序列 $P$ 和 $Q$ 不同，当且仅当 $\exists i \in [1, n] : P_i \neq Q_i$。由于答案可能非常大，他只需要知道答案对 $100\,000\,007$ 取模的结果。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $m$ ($0 \le m \le 17$) 和 $N$ ($1 \le N \le 2^m$)。接下来的 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$ ($0 \le L_i \le R_i < 2^m$)。

保证所有测试用例中 $2^m$ 的总和不超过 $2^{18}$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即 $V(A)$ 对 $100\,000\,007$ 取模后的总和。

样例

样例输入 1

1
2 2
0 1
2 3

样例输出 1

5