Problem Description

Moke is a boy who likes playing games.

As everyone knows, a game should have HP. HP is always a non-negative integer. If at some moment the HP is about to become negative, then the game will crash, and that does not count as a valid game state. HP is allowed to be $0$.
In general, friendly games have some initial HP. But Moke is a boy who enjoys suffering in games, so he sets his initial HP to $0$.

However, the difficulty of this game is not high.
It lasts for a total of $n+1$ moments. The start is moment $0$, and the end is moment $n$. At each moment, Moke will encounter one of the following three types of events, and then proceed to the next moment:

1. Empty ground. It does not change Moke’s HP. There are $a_0$ different kinds of empty ground in total.
2. Monster. It decreases Moke’s HP by $1$. There are $a_{-1}$ different kinds of monsters in total.
3. Item. It increases Moke’s HP by a positive integer. Specifically, there are $a_p$ kinds of items that increase Moke’s HP by $p$, where $p \in \mathbb Z^+$.

To avoid making the game too complicated, the developer guarantees that $\big|\{p \mid p \in \mathbb Z^+ \land a_p > 0\}\big|=k$. That is, all items together cause exactly $k$ different possible HP changes.

Of course, Moke further increases the difficulty for himself. He requires that his HP at the end is $0$, and he also gives a positive integer $m$, meaning that among these $n+1$ moments, his HP is exactly $0$ for exactly $m$ times (including the initial moment).

Please find the number of distinct game states that satisfy Moke’s constraints. Two states are considered different if and only if the types of events encountered at each moment are different (including different empty grounds, different monsters, and different items).

Moke does not want you to face a problem that is too hard. So he gives a prime $P=10^9+7$ and only asks you to output the answer modulo $P$.

Input Format

The first line contains three positive integers $n,m,k$.
The second line contains two positive integers $a_0,a_{-1}$.
The following $k$ lines each contain two positive integers $p_i,a_{p_i}$. They mean that there exist items whose HP change is $p_i$, and there are $a_{p_i}$ kinds of such items.

Output Format

One line containing one non-negative integer, representing the answer modulo $P$.

5 3 1
1 1
1 1

6

5 3 1
1 2
3 4

64

Hint

• For $30\%$ of the testdata, $n \le 15$, $k \le 1$.
• For $50\%$ of the testdata, $n \le 100$.
• For $70\%$ of the testdata, $n \le 2.5 \times 10^3$.
• For $100\%$ of the testdata, $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$, and it is guaranteed that $p_i$ are given in increasing order and are pairwise distinct.

Translated by ChatGPT 5