题目描述
有 $n$ 个物品，物品 $i$ 有两个属性 $a_i, b_i$。对于一个物品集合 $S$，定义 $f(S)$ 是如下问题的答案：
- 对于每个物品 $i \in S$，选择 $0, a_i, b_i$ 三个数中的一个，使得所有物品选择的数之和是 $m$ 的倍数的方案数。
定义物品集合 $S = \{1, 2, \dots, n\}$。有 $q$ 次询问，每次给定四个正整数 $1 \le l_1 \le r_1 < l_2 \le r_2 \le n$，求： $$ \sum_{l_1 \le i \le r_1} \sum_{l_2 \le j \le r_2} f(S \setminus \{i, j\}) $$ 答案对 $10^9 + 7$ 取模。
输入格式
第一行，三个正整数 $n, m, q$。
接下来 $n$ 行，每行两个非负整数 $a_i, b_i$。
接下来 $q$ 行，每行四个正整数 $l_1, r_1, l_2, r_2$，表示一次询问。
输出格式
$q$ 行，每行一个非负整数，表示答案对 $10^9 + 7$ 取模后的值。
样例
输入
6 10 5 2 3 7 1 1 4 8 1 2 5 8 9 1 2 3 4 1 1 2 2 1 1 5 5 1 3 4 6 1 5 6 6
输出
33 9 11 80 37
数据范围
对于所有数据：
- $1 \le n \le 10^4$
- $2 \le m \le 200$
- $1 \le q \le 10^6$
- $0 \le a_i, b_i < m$ ($1 \le i \le n$)
| 子任务 | $n \le$ | $m \le$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| $1$ | $100$ | — | $AB$ | $5$ |
| $2$ | $500$ | — | $AB$ | $5$ |
| $3$ | — | $20$ | $AB$ | $20$ |
| $4$ | — | $150$ | $A$ | $15$ |
| $5$ | — | — | $B$ | $15$ |
| $6$ | — | — | $C$ | $10$ |
| $7$ | — | — | $l_1 = r_1, l_2 = r_2$ | $5$ |
| $8$ | — | — | — | $25$ |
特殊性质 $A$：每次询问都在所有满足条件的 $(l_1, r_1, l_2, r_2)$ 中随机选择。
特殊性质 $B$：$q \le 10^5$。
特殊性质 $C$：对于每个物品 $i$，$a_i = b_i$。