以下最大值均指严格最大值。

思路

首先考虑如果没有 $(a_i,h_i)$ 的限制，那么答案显然是 $c^n$。

那么考虑每个二元限制 $(a_i,h_i)$ 本质上限制了什么条件。

仔细读题：

其中奶牛 $h_i$ 是第一头比奶牛 $1$ 到 $a_i$ 拥有严格更高牲任力分数的奶牛。

使用瞪眼法可以猜出以下两个结论：

• 第 $h_i$ 号奶牛为前缀最大值。
• 第 $a_i+1$ 到第 $h_i-1$ 号奶牛不存在前缀最大值。

::::info[证明]

结论 $1$

如果存在 $j\in [1,h_i-1]$，使得第 $j$ 号奶牛的属性值大于等于 $h_i$ 号奶牛，那么显然不满足题目的限制。

结论 $2$

如果存在 $j\in [a_i+1,h_i-1]$，使得 $j$ 号奶牛为前缀最大值，那么第一头比奶牛 $1$ 到 $a_i$ 拥有严格更高牲任力分数的奶牛应该为 $j$ 而不是 $h_i$。 ::::

由此还可以得出，将限制按照 $h_i$ 排序后，若存在 $i<j,h_i>a_j$，那么无解。不过题目保证有解，所以不存在这种情况。
当出现相同的 $h$ 时，该位的 $a$ 应该取最小值，原因是如果满足 $a$ 较小的限制，那么 $a$ 较大的也一定满足。

实现

将限制按照 $h$ 从小到大排序。

注意到 $C\leq 10^4,Q\leq 100$，复杂度为 $O(CQ)$ 的算法能通过这道题。

考虑动态规划。
设 $f_{i,j}$ 表示考虑到前 $h_i$ 头奶牛，第 $h_i$ 头奶牛的属性值恰为 $j$ 的方案数。
设 $dp_{i,j}$ 表示考虑到前 $h_i$ 头奶牛，第 $h_i$ 头奶牛的属性值小于等于 $j$ 的方案数。 即 $f$ 的前缀和。

考虑转移。

两个限制都与前缀最大值有关。考虑枚举 $1$ 到 $h_i-1$ 的前缀最大值为 $k$。

可列出状态转移方程：

$$f_{i,j}=\sum_{k=1}^{j-1}(dp_{i-1,k}k^{a_i-h_{i-1}}-dp_{i-1,k-1}(k-1)^{a_i-h_{i-1}})k^{(h_i-1-a_i)}$$

注意到 $f_{i,j+1}$ 只比 $f_{i,j}$ 多了一项，所以用前缀和以及快速幂优化一下即可做到 $O(CQ\log n)$。 ::::info[转移方程看不懂的看这] 分别考虑各部分的贡献。

对于区间 $[1,a_{i}]$，贡献为

$$dp_{i-1,k}k^{a_i-h_{i-1}}-dp_{i-1,k-1}(k-1)^{a_i-h_{i-1}}$$

注意这里用了一个小小的容斥。因为要保证 $k$ 在 $[1,a_i]$ 中出现过，所以用全部小于等于 $k$ 的方案数（即 $dp_{i-1,k}k^{a_i-h_{i-1}}$）减去全部小于 $k$ 的方案数（即 $dp_{i-1,k-1}(k-1)^{a_i-h_{i-1}}$），就能得到 $[1,a_i]$ 全部小于等于 $k$ 且至少存在一个 $k$ 的方案数。

对于区间 $[a_i+1,h_i-1]$ 的贡献，每一位都可以任意取小于等于 $k$ 的数，显然为 $k^{(h_i-1-a_i)}$。

二者乘法原理即可得到上面的转移方程。 :::: 别忘了初始化 $dp_{0}$ 均为 $1$。

代码

马蜂良好有注释。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define dd double
//char buf[1<<23],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
inline ll read() {
	ll x = 0, f = 1;
	char ch;
	while (((ch = getchar()) < 48 || ch > 57) && ch != EOF)if (ch == '-')f = -1;
	if (ch == EOF)x = EOF;
	while (ch >= 48 && ch <= 57)x = x * 10 + ch - 48, ch = getchar();
	return x * f;
}
char __sta[1009], __len;
inline void write(ll x, ll bo) {
	if (x < 0)putchar('-'), x = -x;
	do __sta[++__len] = x % 10 + 48, x /= 10;
	while (x);
	while (__len)putchar(__sta[__len--]);
	if (bo == 3)return;
	putchar(bo ? '\n' : ' ');
}
constexpr unsigned int N=1e4+9,M=109,MOD=1e9+7;
int n,q,c;
ll dp[M][N];
//考虑前 h[i] 个位置，第 h[i] 位 <= j 的方案数
ll f[M][N];
//考虑前 h[i] 个位置，第 h[i] 位刚好为 j 的方案数
int h[N];
map<int,int>a;
//qp
int qp(ll a,int b){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return ans;
}
//input
void input(){
	n=read(),q=read(),c=read();
	for(int i=1;i<=q;i++){
		int x=read();
		h[i]=read();
		if(a[h[i]]!=0)a[h[i]]=min(a[h[i]],x);
		else a[h[i]]=x;
	}
	sort(h+1,h+q+1);
	q=unique(h+1,h+q+1)-h-1;
}
//solve
void solve(){
	for(int j=0;j<=c;j++){
		dp[0][j]=1;
	}
	for(int i=1;i<=q;i++){
		for(int j=i+1;j<=c;j++){
			f[i][j]+=f[i][j-1];//1~a[i] 的前缀最大值小于 j-1 的情况
			f[i][j]+=(dp[i-1][j-1]*qp(j-1,a[h[i]]-h[i-1])%MOD-dp[i-1][j-2]*qp(j-2,a[h[i]]-h[i-1])%MOD+MOD)%MOD*qp(j-1,h[i]-1-a[h[i]])%MOD;
			//1~a[i] 的前缀最大值为 j-1 的情况
			f[i][j]%=MOD;
			dp[i][j]=(dp[i][j-1]+f[i][j])%MOD;
		}
	}
	ll ans=dp[q][c]*qp(c,n-h[q])%MOD;
	write(ans,1);
	
}
//debug
void debug(){
	for(int i=1;i<=q;i++){
		for(int j=1;j<=c;j++){
			cout<<i<<' '<<j<<endl<<f[i][j]<<endl;
		}
	}
}
int main() {
	input();
	solve();
	return 0;
}