题目描述

给定 $n$ 个区间 $[l_i, r_i]$ 和一个常数 $k$。

对两个区间 $[l, r]$ 和 $[l', r']$，定义函数 $f([l, r], [l', r'])$ 为区间 $[l, r]$ 和 $[l', r']$ 的交集长度。

更形式化地，我们有： $$f([l, r], [l', r']) = \begin{cases} 0 & \text{if } r' < l \, \text{or} \, l' > r \\ \min(r, r') - \max(l, l') + 1 & \text{otherwise} \end{cases}$$

给定 $m$ 组询问，每次给出区间 $[L, R]$，你需要求出 $\sum_{i=1}^n f([L, R], [l_i, r_i])^k$，对 $10^9 + 7$ 取模。

输入格式

第一行包含三个整数 $n, k, m$。

接下来的 $n$ 行每行包含两个整数 $l_i, r_i$。

接下来的 $m$ 行每行包含两个整数 $L, R$。

输出格式

输出 $m$ 行，每行一个整数表示 $\sum_{i=1}^n f([L, R], [l_i, r_i])^k$，对 $10^9 + 7$ 取模。

样例

样例 1 输入

3 1 2
1 1
1 2
1 3
1 2
1 3

样例 1 输出

5
6

样例 1 解释

对于第一个询问，答案为 $f([1, 1], [1, 2]) + f([1, 2], [1, 2]) + f([1, 3], [1, 2]) = 1 + 2 + 2 = 5$。

对于第二个询问，答案为 $f([1, 1], [1, 3]) + f([1, 2], [1, 3]) + f([1, 3], [1, 3]) = 1 + 2 + 3 = 6$。

样例 2 输入

4 2 4
1 4
2 3
1 3
2 4
1 4
2 3
1 3
2 4

样例 2 输出

38
16
26
26

样例 2 解释

对于第一个询问，答案为 $f([1, 4], [1, 4])^2 + f([2, 3], [1, 4])^2 + f([1, 3], [1, 4])^2 + f([2, 4], [1, 4])^2 = 16 + 4 + 9 + 9 = 38$。

数据范围

对于所有数据，保证：$1 \le n, m \le 10^5$，$1 \le k \le 14$，$1 \le l_i \le r_i \le n$，$1 \le L \le R \le n$。

特殊性质 A：保证所有给出的区间两两之间要么相等，要么不存在包含关系。