P6533 [COCI 2015/2016 #1] RELATIVNOST

您是一位计数大师，有一天您的朋友 Luka 出了一道问题来刁难您。 Luka 是一位勤劳的画家，他的画很好，所以会有 $n$ 个人来买他的画。 画分两种，黑白画与彩色画。 Luka 十分勤劳，所以他有无穷多的画。 Luka 讨厌出售黑白画，所以他希望至少有 $c$ 个人会买走一张彩色画。 第 $i$ 个人会至多购买 $a_i$ 张彩色画，$b_i$ 张黑白画，且它们会至少购买一幅画。 但是，客户们只能单独购买彩色画或黑白画。 客户们会不断改变 $a_i$ 与 $b_i$，这种改变会持续 $q$ 次。 客户以 $1\sim n$ 编号。 您需要求出在每次改变之后，Luka 会有几种方案满足所有需求。 为了防止输出太大，Luka 只需要您告诉他方案数 $\bmod\ 10^4+7$ 的值。

无

无

#### 样例 1 说明 第一次改变后，我们只有唯一的一种方案，就是向两位用户都出售一张彩色画。 #### 数据范围及限制 - 对于 $30\%$ 的数据，保证 $n,q\le 10^3$。 - 对于 $100\%$ 的数据，保证 $1\le n,q\le 10^5$，$1\le c\le 20$，$1\le a_i,b_i,a_{p_i},b_{p_i}\le 10^9$，$1\le p_i\le n$。 #### 说明 **本题满分 $140$ 分。** 本题译自 [Croatian Open Competition in Informatics 2015/2016](https://hsin.hr/coci/archive/2015_2016) [Contest #1](https://hsin.hr/coci/archive/2015_2016/contest1_tasks.pdf) T5 RELATIVNOST。