题目描述

有 $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$
$3$	—	$20$		$20$
$4$		$150$	A	$15$
$5$		—	B
$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$。