3411: 破解
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：23
解决：9
题目描述
历经千辛万苦，ddddddpppppp 终于找到了 IBN5100。
dp 事先了解到 SERN 共有T个密码，每个密码是一个长度为N的01串，他要利用 IBN5100 的特殊功能破解 SERN 的密码。
初始时，IBN5100 中的串每个位置都是0。
这台特殊的 IBN5100 还提供了M个区间 [Li,Ri]，每次操作是从给定区间中选择其中一个区间 [Li,Ri]，将当前01串 [Li,Ri] 的位置上的数字全部取反。
dp可以执行上述操作任意次。为了破解出密码，dp想知道这个01串最多有多少种可能。
由于答案可能很大，所以你只需要告诉 dp 模 (10^9+7) 后的答案即可。
注意：每次破解都是独立的。
输入
第一行，一个整数T表示一共T组数据。
每组数据第一行， 两个整数 N, M，分别表示密码串长度和区间个数。
接下来M行， 第i行两个整数 Li, Ri 表示一个区间 [Li,Ri]。
输出
每组数据一行，一个整数表示所有的可能，答案对 (10^9+7) 取模。
样例输入 复制
2
3 3
1 1
2 2
3 3
5 2
1 2
4 5样例输出 复制
8 4提示
第一组数据：每个位置都可以单个修改，所以所有长度为3的01串都有可能，即 2^3=8 种可能。
第二组数据的四种可能如下：
1. 不操作: 00000
2. 选择区间 [1,2]: 11000
3. 选择区间 [4,5]: 00011
4. 先选择区间 [1,2] 再选择 [4,5]: 11011
【数据范围】
对于30%的数据，N,M ≤ 10
对于60%的数据，N ≤ 10000000 , M ≤ 20
对于100%的数据，N ≤ 10000000 , M ≤ 100000 ,1 ≤ Li ≤ Ri ≤ N , T ≤ 10