#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}


int main(){
    int N, M, K, L[3000], R[3000];
    cin >> N >> M >> K;
    for(int i=0; i<M; i++){
        cin >> L[i] >> R[i];
    }

    static int64_t dp[3001][3002];

    dp[0][1] = 1;
    for(int i=0; i<K; i++){
        int64_t sum[3001] = {0};
        for(int j=1; j<=N; j++){
            sum[j] = sum[j-1];
            add(sum[j], dp[i][j]);
        }
        for(int j=0; j<M; j++){
            int64_t result = (sum[R[j]] - sum[L[j]-1] + MOD) % MOD;
            add(dp[i+1][L[j]], result);
            add(dp[i+1][R[j]+1], MOD - result);
        }
        for(int j=1; j<=N; j++) add(dp[i+1][j], dp[i+1][j-1]);
    }
    cout << dp[K][N] << endl;
    return 0;
}