406385: GYM102394 B Binary Numbers

ZYB is a smart guy. He is figuring out a problem about binary numbers.

Let $$$a_i$$$ be the $$$i$$$-th (0-based indexing) least significant bit in the binary representation of $$$a$$$. For example, if $$$ a = 2 $$$, then $$$ a_0=0,a_1=1 $$$, and $$$a_i=0$$$ for $$$i\ge 2$$$. Define $$$F_k(a,b)$$$ as: $$$$$$F_k(a,b)= \begin{cases} F_{k-1}(a,b) + 1 & (a_k = b_k) \\ 0 & (a_k \neq b_k) \end{cases}$$$$$$ Specifically, $$$ F_{-1}(a,b)=0 $$$.

ZYB has $$$N$$$ intervals $$$ [L_1,R_1],\ [L_2,R_2],\ \dots,\ [L_n,R_n] $$$ where $$$ L_1=0,\ R_n=2^m-1 $$$, and $$$ \forall i \in [1,n-1]: \: R_i +1 =L_{i+1} $$$. He wants to select $$$N$$$ integers $$$ A_1,A_2, \dots, A_n $$$ so that $$$A_i \in [L_i,R_i]$$$, and for each $$$ i \in [1,n] $$$, the following condition holds: $$$$$$ \forall k \in [L_i,R_i]: \: F_{m-1}(A_i,k) \geq \max \limits_{1 \le j \le N}\{F_{m-1}(A_j,k)\} $$$$$$ The value of the sequence $$$A$$$ is defined as $$$ V(A)=\prod \limits_{i=1}^n A_i $$$.

Of course, there are multiple ways to select the sequence $$$A$$$. Now ZYB wonders what is the sum of $$$ V(A) $$$ among all different sequences he can select. Two sequences $$$P$$$ and $$$Q$$$ are different if and only if $$$ \exists i \in[1,n]: \: P_i \ne Q_i $$$. Because the answer could be quite large, he only wants to know the answer modulo $$$100\,000\,007$$$.

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \leq T \leq 100)$$$, the number of cases.

For each case, the first line of the input contains two integers $$$m$$$ ($$$0 \leq m \leq 17$$$) and $$$N$$$ ($$$1 \leq N \leq 2^m$$$). The following $$$N$$$ lines each contains two integers $$$L_i$$$ and $$$R_i \ (0 \le L_i \le R_i < 2^m)$$$.

It's guaranteed that the sum of $$$2^m$$$ over all cases doesn't exceed $$$2^{18}$$$.

For each case, print a single integer in a single line, the sum of $$$V(A)$$$ modulo $$$100\,000\,007$$$.

1
2 2
0 1
2 3

5