#PU1378. USACO 2024 January Contest, Gold — Problem 2. Cowmpetency

    ID: 1549 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan24来源:usaco.orgscoring:equal_test_cases数学

USACO 2024 January Contest, Gold — Problem 2. Cowmpetency

USACO 2024 January Contest, Gold — Problem 2. Cowmpetency

题目描述

Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed NN (2≤N≤1092 \leq N \leq 10^9) cows for the position. After each interview, he assigned an integer "cowmpetency" score to the candidate ranging from 11 to CC (1≤C≤1041 \leq C \leq 10^4) 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 QQ (1≤Q≤min⁡(N−1,100)1 \leq Q \leq \min(N - 1, 100)) pairs of numbers (ai,hi)(a_i, h_i) where cow hih_i was the first cow with a strictly greater cowmpetency score than cows 11 through aia_i (so 1≤ai<hi≤N1 \leq a_i < h_i \leq N). Farmer John now tells you the QQ pairs of (ai,hi)(a_i, h_i). 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+710^9 + 7.

输入格式

The first line contains NN, QQ, and CC. The next QQ lines each contain a pair (ai,hi)(a_i, h_i). It is guaranteed that all aja_j are distinct.

输出格式

The number of sequences of cowmpetency scores consistent with what Farmer John remembers, modulo 109+710^9+7.

数据范围

Inputs 3-4 satisfy N≤10N \leq 10 and Q,C≤4Q, C \leq 4. Inputs 5-7 satisfy N,C≤100N, C \leq 100. Inputs 8-10 satisfy N≤2000N \leq 2000 and C≤200C \leq 200. Inputs 11-15 satisfy N,C≤2000N, C \leq 2000. Inputs 16-20 satisfy no additional constraints. Problem credits: Suhas Nagar

样例

样例 1

6 2 3
2 3
4 5
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

样例 2

10 1 20
1 3
399988086
Make sure to output the answer modulo $10^9+7$.