Given $n$ intervals $[l_i, r_i]$ and a constant $k$.

For two intervals $[l, r]$ and $[l', r']$, define the function $f([l, r], [l', r'])$ as the length of the intersection of intervals $[l, r]$ and $[l', r']$.

More formally, we have: $$ 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} $$

Given $m$ queries, each providing an interval $[L, R]$, you need to calculate $\sum_{i=1}^n f([L, R], [l_i, r_i])^k$, modulo $10^9 + 7$.

Input

The first line contains three integers $n, k, m$.

The next $n$ lines each contain two integers $l_i, r_i$.

The next $m$ lines each contain two integers $L, R$.

Output

Output $m$ lines, each containing an integer representing $\sum_{i=1}^n f([L, R], [l_i, r_i])^k$, modulo $10^9 + 7$.

Examples

Input 1

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

Output 1

5
6

Note 1

For the first query, the answer is $f([1, 1], [1, 2]) + f([1, 2], [1, 2]) + f([1, 3], [1, 2]) = 1 + 2 + 2 = 5$.

For the second query, the answer is $f([1, 1], [1, 3]) + f([1, 2], [1, 3]) + f([1, 3], [1, 3]) = 1 + 2 + 3 = 6$.

Input 2

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

Output 2

38
16
26
26

Note 2

For the first query, the answer is $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$.

Constraints

For all data, it is guaranteed that: $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$.

Special Property A: It is guaranteed that for all given intervals, any two intervals are either equal or do not contain each other.