题目描述

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$ 的结果。

5 3 1
1 1
1 1

6

5 3 1
1 2
3 4

64

提示

• 对于 $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$ 从小到大给出且互不相同。