P7896 『JROI-3』Moke 的游戏

Moke 是一个喜欢玩游戏的男孩子。 众所周知，游戏应当有血量。血量**永远是非负整数**，如果在某个时刻血量将要变为负数，那么游戏会崩溃，这就不算作一种游戏局面。这里允许血量是 $0$。 一般来说，友好的游戏都会具有一定的初始血量。但是 Moke 是一个喜欢在游戏里受虐的男孩子。所以他把自己的初始血量设成了 $0$。 不过，这个游戏的难度并不高。 它一共进行 $n+1$ 个时刻。初始是第 $0$ 个时刻，最终是第 $n$ 个时刻。每个时刻 Moke 会遇到以下三种事件，然后进入下一时刻： 1. 空地。它使得 Moke 的血量不变。一共有 $a_0$ 种不同的空地。 2. 怪兽。它使得 Moke 的血量减一。一共有 $a_{-1}$ 种不同的怪兽。 3. 道具。它使得 Moke 的血量增加一个正整数。具体地，一共有 $a_p$ 种使 Moke 血量加 $p$ 的道具，其中 $p \in \mathbb Z^+$。 为了不让游戏太复杂，游戏的开发者保证 $\big|\{p \mid p \in \mathbb Z^+ \land a_p > 0\}\big|=k$。即，所有道具总共只造成恰好 $k$ 种不同的血量变化量。 当然，Moke 还是给自己进一步增加了难度。他要求结束时自己的血量为 $0$，且给出一个正整数 $m$，表示限制这 $n+1$ 个时刻中，他恰好有 $m$ 次血量为 $0$（包括初始时刻）。 请求出所有不同的，符合 Moke 限制的游戏局面个数。两个局面不同当且仅当每个时刻遇到的事件的种类不同（包括不同的空地、不同的怪兽和不同的道具）。 Moke 不希望你面对太困难的问题。所以他给出一个质数 $P=10^9+7$ 并只要求你给出取模 $P$ 后的答案。

第一行，三个正整数 $n,m,k$。 第二行，两个正整数 $a_0,a_{-1}$。 以下 $k$ 行，其中第 $i$ 行两个正整数 $p_i,a_{p_i}$。表示存在道具造成的血量变化量为 $p_i$，且这样的道具有 $a_{p_i}$ 种。

一行，一个非负整数。表示答案取模 $P$ 的结果。

- 对于 $30\%$ 的数据，$n \le 15$，$k \le 1$。 - 对于 $50\%$ 的数据，$n \le 100$。 - 对于 $70\%$ 的数据，$n \le 2.5 \times 10^3$。 - 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^6$，$1 \le m \le n + 1$，$1 \le k \le 10$，$1 \le p_i \le n$，$0 < a_0,a_{-1},a_{p_i} < P$，保证 $p_i$ 从小到大给出且互不相同。