Moke's Game: Counting Valid Game Sequences

Moke is a boy who loves playing games – especially games where his health (an integer) is tracked. In this game the health is always a non‐negative integer (zero is allowed). If at any moment the health would become negative, the game crashes and that sequence of events is invalid.

Moke deliberately chose a cruel starting condition by setting his initial health to 0. The game proceeds through n+1 moments, starting from time 0 (initial state) and ending at time n. At each step between moments, one event occurs which moves the game to the next moment. There are three types of events:

1. Blank tile: the health remains unchanged. There are a₀ different blank tiles.
2. Monster: health decreases by 1. There are a_-1 different monsters (note that a monster cannot be encountered if the current health is 0 because that would bring the health to -1).
3. Item: the health increases by a positive integer. Specifically, for each positive integer p (with p ∈ ℤ⁺) there are a_p different items that increase the health by p. The developer guarantees that exactly k distinct positive values occur (i.e. there are exactly k different positive integers p for which a_p > 0).

Moke further challenges himself by requiring that the final health (after n events) is 0 and that exactly m of the n+1 moments (including the initial moment) have a health of 0. Two game sequences are considered different if, at any moment, the type of event (including the identity among different blank tiles, monsters, or items) is different.

Your task is to compute the number of distinct valid game sequences satisfying these restrictions. Output the answer modulo \(P=10^9+7\).

Input Format: The input is given as follows. The first line contains three integers: n, m, and k. The second line contains two integers: a₀ and a_-1. Then k lines follow; each contains two integers: p (a positive integer) and a_p.

Note: Health must always be non-negative. An event that would reduce the health below 0 is not allowed.

inputFormat

The first line contains three integers n, m, and k:

• n — the number of events (there are n+1 moments from time 0 to time n).
• m — the required number of times (among the n+1 moments) that the health equals 0, including the initial moment.
• k — the number of different positive health changes provided by items.

The second line contains two integers: a₀ and a_-1, the number of distinct blank tiles and monsters respectively.

Then follow k lines. Each of these lines contains two integers p and a_p, where p (\(p \in \mathbb{Z}^+\)) is the amount by which the item increases the health, and a_p is the number of different items that increase the health by p.

outputFormat

Output a single integer: the number of valid game sequences modulo \(10^9+7\).

sample

1 2 1
1 1
1 1

1