#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll MOD = 1000000007; ll dp[3010]; ll RUI[3010]; ll D[3010]; int main() { int N, M, K; cin >> N >> M >> K; vector L(M); vector R(M); for (int i = 0; i < M; ++i) { cin >> L[i] >> R[i]; } memset(dp, 0, sizeof(dp)); dp[1] = 1; for (int i = 0; i < K; ++i) { memset(RUI, 0, sizeof(RUI)); for (int j = 1; j <= N; ++j) { RUI[j] = dp[j] + RUI[j - 1]; RUI[j] %= MOD; } memset(D, 0, sizeof(D)); for (int j = 0; j < M; ++j) { int l = L[j]; int r = R[j]; ll sum = RUI[r] - RUI[l - 1]; D[l] += sum; D[r + 1] -= sum; } ll sum = 0; for (int j = 1; j <= N; ++j) { sum += D[j]; sum %= MOD; dp[j] = sum; } } cout << dp[N] << endl; return 0; }