n, m, k = map(int, input().split())
mod = 10**9+7
t = [tuple(map(int, input().split())) for _ in range(m)]

cnt = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l, r = t[i]
    for i in range(l, r+1):
        for j in range(l, r+1):
            cnt[i][j] += 1

dp = [[0]*(n+1) for _ in range(k+1)]
dp[0][1] = 1
for i in range(1, k+1):
    for j in range(1, n+1):
        for x in range(1, n+1):
            dp[i][j] += dp[i-1][x]*cnt[x][j]%mod
        dp[i][j] %= mod
print(dp[k][n])