There are $n$ dice, each with $m+1$ faces, labeled with the numbers $0 \sim m$. The probability that the $i$-th die lands on the face with number $j$ is always $p_{i,j}$.

You plan to roll dice $q$ times. In the $i$-th roll, you throw all dice with indices in the range $[l_i, r_i]$. Let $sum$ be the sum of the numbers on the faces of these dice. If $sum \le m$, you receive $b_{sum}$ happiness; otherwise, you receive nothing. What is the expected happiness you receive for each round? The answer should be modulo $10^9 + 7$.

Input

The first line contains three positive integers $n, m, q$ ($1 \le n \le 1500, 1 \le m \le 200, 1 \le q \le 6 \times 10^5$).

The second line contains $m+1$ non-negative integers, representing $b_0, \dots, b_m$ ($0 \le b_i < 10^9 + 7$).

The next $n$ lines each contain $m+1$ non-negative integers $p'_{i,0}, \dots, p'_{i,m}$ ($p'_{i,j} \ge 0, \sum_{j=0}^m p'_{i,j} = 10^9 + 8$), representing $p_{i,j} = \frac{p'_{i,j}}{10^9 + 8}$.

The next $q$ lines each contain two positive integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$).

Output

Output $q$ lines, each containing a non-negative integer representing the answer modulo $10^9 + 7$.

Examples

Input 1

3 3 3
4 3 2 1
0 1 0 1000000007
0 500000004 0 500000004
0 0 500000004 500000004
1 1
1 2
1 3

Output 1

3
1
0

Input 2

3 3 6
4 3 2 1
1000000007 0 1 0
1000000007 1 0 0
1000000007 0 1 0
1 1
1 2
1 3
2 2
2 3
3 3

Output 2

2
1
0
3
1
2