#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

const int MOD = 1e9 + 7;

struct LazySegmentTree {
	std::vector<int> seg, lazy;
	int sz = 1;
	
	LazySegmentTree(int n) {
		while(sz < n) sz <<= 1;
		seg.assign(sz * 2 - 1, 0);
		lazy.assign(sz * 2 - 1, 0);
	}
	void initial() {
		seg.assign(sz * 2 - 1, 0);
		lazy.assign(sz * 2 - 1, 0);
	}
	void update(int k, int x = 1) {
		k += sz - 1;
		seg[k] = x;
		
		while(k) {
			k = (k - 1) >> 1;
			
			seg[k] = (seg[2 * k + 1] + seg[2 * k + 2]) % MOD;
		}
	}
	void push(int k, int l, int r) {
		if(k < sz - 1) {
			(lazy[2 * k + 1] += lazy[k]) %= MOD;
			(lazy[2 * k + 2] += lazy[k]) %= MOD;
		}
		(seg[k] += (i64)lazy[k] * (i64)(r - l) % MOD) %= MOD;
		lazy[k] = 0;
	}
	void add(int a, int b, int k, int l, int r, int x) {
		push(k, l, r);
		if(b <= l || r <= a) return;
		if(a <= l && r <= b) {
			(lazy[k] += x) %= MOD;
			push(k, l, r);
			return;
		}
		
		add(a, b, 2 * k + 1, l, (l + r) >> 1, x);
		add(a, b, 2 * k + 2, (l + r) >> 1, r, x);
		seg[k] = (seg[2 * k + 1] + seg[2 * k + 2]) % MOD;
	}
	void add(int a, int b, int x) {
		add(a, b, 0, 0, sz, x);
	}
	int get(int a, int b, int k, int l, int r) {
		push(k, l, r);
		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b) return seg[k];
		
		int L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
		int R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
		return (L + R) % MOD;
	}
	int get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
	int operator[](int k) {
		return get(k, k + 1);
	}
};

int main() {
	int n, m, k; scanf("%d%d%d", &n, &m, &k);
	std::vector<int> l(m), r(m);
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &l[i], &r[i]);
		
		l[i]--;
	}
	
	std::vector<LazySegmentTree> dp(2, LazySegmentTree(n)); dp[0].update(0);
	for(int i = 0; i < k; i++) {
		int cur = i % 2, to = 1 - i % 2;
		dp[to].initial();
		for(int j = 0; j < m; j++) {
			int tmp = dp[cur].get(l[j], r[j]);
			dp[to].add(l[j], r[j], tmp);
		}
	}
	printf("%d\n", dp[k % 2][n - 1]);
	return 0;
}