#include using namespace std; using i64 = long long; #define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++) #define all(x) x.begin(),x.end() const i64 MOD = 1e9 + 7; int main() { i64 N,M,K; cin >> N >> M >> K; vector> vec(M); for(auto& v : vec) { cin >> v.first >> v.second; } vector dp(N + 2,0); vector sum(N + 2, 0); dp[1] = 1; for(int c = 0;c < K;c++) { rep(i,1,N) sum[i] = (sum[i - 1] + dp[i]) % MOD; rep(i,1,N) dp[i] = 0; for(const auto& v : vec) { i64 a = v.first; i64 b = v.second; dp[a] = (dp[a] + (sum[b] - sum[a - 1] + MOD) % MOD) % MOD; dp[b + 1] = (dp[b + 1] - (sum[b] - sum[a - 1] + MOD) % MOD + MOD) % MOD; } rep(i,1,N) dp[i] = (dp[i] + dp[i - 1]) % MOD; } cout << dp[N] << endl; }