#include<iostream>
#include<algorithm>
using namespace std;
long mod=1e9+7,dp[3001][3002];
int n,m,k,L[3000],R[3000];
main()
{
	cin>>n>>m>>k;
	for(int i=0;i<m;i++)cin>>L[i]>>R[i];
	for(int i=1;i<=n;i++)dp[0][i]=1;
	for(int i=0;i<k;i++)
	{
		for(int j=0;j<m;j++)
		{
			long now=dp[i][R[j]]-dp[i][L[j]-1];
			dp[i+1][L[j]]+=now;
			dp[i+1][R[j]+1]-=now;
		}
		for(int j=0;j<=n;j++)
			dp[i+1][j+1]+=dp[i+1][j]=(dp[i+1][j]%mod+mod)%mod;
		for(int j=0;j<=n;j++)
			dp[i+1][j+1]+=dp[i+1][j]=(dp[i+1][j]%mod+mod)%mod;
	}
	cout<<(dp[k][n]-dp[k][n-1]+mod)%mod<<endl;
}