Packing Candies

All submissions for this problem are available.
It’s Halloween. Papa Smurf has received a lot of orders of candies. One day, while packing candies, he counted number of different ways he can pack candies in a box. Two ways are different if there exists a candy type for which its count in resulting boxes is different. Box has a property that they can contain only a fixed number of candies, neither less nor more.
If Papa has three types for candies S_{1}, S_{2}, S_{3} and three boxes (B_{1}, B_{2}, B_{3}), and he has to pack 6 candies in each box. Suppose he pack candies in a way that box has configuration B_{1}{S_{1} = 1, S_{2} = 0, S_{3} = 5}, B_{2}(S_{1} = 1, S_{2}_{ }= 3, S_{3} = 2) and B_{3}(S_{1} = 1, S_{2} = 0, S_{3} = 5), then Box B_{1} and B_{2} are said to have different configuration, while Box B_{1} and B_{3} are same.
But wait, there are some candies of which Smurfs are very fond of. So they gave you a list of such candies and the minimum number for each candy they want in their box. If a candy is not in this list, then Papa can pack any number (including zero) of this type of candy.
Now help Papa in counting different number of ways he can pack candies in a box. Papa has infinite supply of each type of candies.
Input
First line of input contain three integers, N M K, number of candies to be packed in a box, number of types of candies Papa had and length of candy's list which Smurfs give to him respectively. Then follow K lines. In each lines there are two integers, S_{i} X_{i}, type of candy and minimum number of candy he has to put in each box (1 ≤ i ≤ M).
Output
Find number of different ways Papa can pack candies in a box. As this number can be very large print answer modulo 1000000007 (10^9 + 7).
Constraints
1 ≤ N ≤ 1000000
1 ≤ M ≤ 1000000
0 ≤ K ≤ M
1 ≤ S_{i} ≤ M
1 ≤ X_{i} ≤ 1000000
Example
Input #0: 4 2 1 1 2 Output #0: 3 Input #1: 5 3 2 1 2 2 1 Output #1: 6 Input #2: 5 1 1 3 6 Output #2: 0
Explanation
Explanation for Sample Input #0:
Papa has to pack 4 candies in a box, and he has two types of candies (S_{1}, S_{2}). This particular Smurf has mentioned that the box must have at least 2 candy of candy type #1. Then there are 3 number of ways of packing candies, represented by (S_{1} = 2, S_{2} = 2), (S_{1} = 3, S_{2} = 1), (S_{1} = 4, S_{2} = 0).
Explanation for Sample Input #2:
Papa has to pack 5 candies in a box, while according to list he has to pack at least 6 candies of candy type 3. And it is not possible.
Author:  kumarvimal 
Tags  kumarvimal 
Date Added:  2112012 
Time Limit:  0.351585 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, GO 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions