10341: H

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

有一天,FQ在玩一个游戏。

FQ有个数组 a[1...k],一开始 a[i] = i (1 ≤ i ≤ k)。然后FQ不断的对这个数组进行操作,每次的操作都是把这个数组的一个区间反转。

举例来说,FQ一开始有 a[1...5] = {1, 2, 3, 4, 5}。然后他将 a[2...4] 反转,数组就变成了 {1, 4, 3, 2, 5};再将 a[2...5] 反转,就得到了 a[1...5] = {1, 5, 2, 3, 4}

FQ总共对这个数组进行了 n 次操作,并把操作记录了下来。这个时候ZQ出场了,ZQ找到了FQ的记录,但是由于天气原因,FQ的记录不全——ZQ得到的记录是FQ全部记录下的操作序列的一个子串。ZQ就只得认为他得到的序列是FQ的全部操作。在ZQ看来,FQ的序列最终是什么样子的呢?

Input

多组数据,第一行输入数据数 T(T ≤ 50)

每组数据第一行为 k(1 ≤ k ≤ 20)n(1 ≤ n ≤ 105)。接下来 n 对整数 l, r(1 ≤ l ≤ r ≤ k) 表示FQ的 n 个操作。

再之后一个整数 q(1 ≤ q ≤ 105),表示q组查询。之后q行,每行是一对整数 x, y(1 ≤ x ≤ y ≤ n),表示ZQ得到的记录是FQ记录的第x条到第y条。

Output

对于每组数据的每组查询,你应该求出按照记录的第x条到第y条操作反转初始数组之后的结果。并对这个结果求哈希值。假设求得的序列是 b[1...k],要求的哈希值是 (∑[1 ≤ i ≤ k] b[i] × 23i) mod 1000000007。

每组数据,你要输出的结果是所有查询的哈希值的和取模1000000007的余数。每组数据的结果占一行,共T行。

Sample Input Copy

1
5 2
2 4
2 5
2
1 2
1 1

Sample Output Copy

59391934

HINT

第一组查询,a[1...5] = {1, 2, 3, 4, 5} 反转 a[2...4],再反转 a[2...5]。结果序列是 {1, 5, 2, 3, 4},哈希值是 1 × 231 + 5 × 232 + 2 × 233 + 3 × 234 + 4 × 235 = 26611897

第一组查询,a[1...5] = {1, 2, 3, 4, 5} 反转 a[2...4],结果序列是 {1, 4, 3, 2, 5},哈希值是 1 × 231 + 4 × 232 + 3 × 233 + 2 × 234 + 5 × 235 = 32780037

故样例的结果是26611897 + 32780037 = 59391934

由于上述结果都不超过1000000007,故解释中取模的步骤略去。