Farmer John has N cows (2≤N≤5⋅106) and is attempting to get them to sort a non-negative integer array A of length N by relying on their laziness. He has a lot of heavy boxes so he lines the cows up one behind another, where cow i+1 is behind cow i, and gives ai boxes to cow i (0≤ai).
Cows are inherently lazy so they always look to pass their work off to someone else. From cow 1 to N−1 in order, each cow looks to the cow behind them. If cow i
has strictly more boxes than cow i+1, cow i thinks this is "unfair" and gives one of its boxes to cow i+1. This process repeats until every cow is satisfied.
Farmer John will then note the number of boxes bi that each cow i is holding and create an array B out of these values. If B=sorted(A), then Farmer John will be happy. Unfortunately, Farmer John forgot all but Q values (2≤Q≤min(N,100)) in A. Luckily, those values include the number of boxes he was going to give to the first and last cow. Each value that FJ remembers is given in the form ci vi representing that a ci=vi(1≤ci≤N, 1≤vi ≤109). Determine the number of different ways the missing values can be filled in so that he will be happy mod 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers N and Q representing the number of cows and queries respectively.
The next Q lines contain two space separated integers ci vi representing that cow ci initially holds vi boxes. It is guaranteed that c1=1, cQ=N, and ci<ci+1
(the order of the cows is strictly increasing).
OUTPUT FORMAT (print output to the terminal / stdout):
Print the number of different ways modulo 109+7 that values ai can be assigned such that Farmer John will be happy after the cows perform the lazy sort. It is guaranteed that there will be at least one valid assignment.
SAMPLE INPUT:
3 2
1 3
3 2
SAMPLE OUTPUT:
2
In this example, FJ remembers the values at the ends of the array. The arrays [3,2,2] and [3,3,2] are the valid arrays that will make FJ happy at the end of the lazy sorting.
SAMPLE INPUT:
6 3
1 1
3 3
6 5
SAMPLE OUTPUT:
89
SCORING:
Inputs 3-4: N,vi≤100
Inputs 5-6: N≤100 and vi≤106
Inputs 7-9: N≤2⋅105 and vi≤106
Inputs 10-12: N≤2⋅105
Inputs 13-15: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
