Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed N (2≤N≤109) cows for the position. After each interview, he assigned an integer "cowmpetency" score to the candidate ranging from 1
to C(1≤C≤104) that is correlated with their leadership abilities.
Because he has interviewed so many cows, Farmer John has forgotten all of their cowmpetency scores. However, he does remembers Q(1≤Q≤min(N−1,100)) pairs of numbers (ai,hi) where cow hi was the first cow with a strictly greater cowmpetency score than cows 1 through ai (so 1≤ai<hi≤N).
Farmer John now tells you the Q pairs of (ai,hi). Help him count how many sequences of cowmpetency scores are consistent with this information! It is guaranteed that there is at least one such sequence. Because this number may be very large, output its value modulo 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N, Q, and C.
The next Q lines each contain a pair (ai,hi). It is guaranteed that all aj are distinct.
OUTPUT FORMAT (print output to the terminal / stdout):
The number of sequences of cowmpetency scores consistent with what Farmer John remembers, modulo 109+7.
SAMPLE INPUT:
6 2 3
2 3
4 5
SAMPLE OUTPUT:
6
The following six sequences are the only ones consistent with what Farmer John remembers:
1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3
SAMPLE INPUT:
10 1 20
1 3
SAMPLE OUTPUT:
399988086
Make sure to output the answer modulo 109+7.
SCORING:
Inputs 3-4 satisfy N≤10 and Q,C≤4.
Inputs 5-7 satisfy N,C≤100.
Inputs 8-10 satisfy N≤2000 and C≤200.
Inputs 11-15 satisfy N,C≤2000.
Inputs 16-20 satisfy no additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
