P12493 [集训队互测 2024] 子集和

有 $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

第一行，三个正整数 $n,m,q$。 接下来 $n$ 行，每行两个非负整数 $a_i,b_i$。 接下来 $q$ 行，每行四个正整数 $l_1,r_1,l_2,r_2$，表示一次询问。

$q$ 行，每行一个非负整数，表示答案对 $10^9+7$ 取模后的值。

### 数据范围 对于所有数据： - $1\le n\le 10^4$ - $2\le m\le 200$ - $1\le q\le 10^6$ - $0\le a_i,b_i