N,M,K = map(int,input().split())
LR = [list(map(int,input().split())) for _ in range(M)]
MOD = 10 ** 9 + 7

Mat = [[0]*(N+1) for _ in range(N+1)]
Mat2 = [[0]*(N) for _ in range(N)]

#2次元いもす

for l, r in LR:
    Mat[l-1][l-1] += 1
    Mat[l-1][r] -= 1
    Mat[r][l-1] -= 1
    Mat[r][r] += 1

for i in range(N):
    for j in range(N):
        if i == 0:
            if j == 0:
                Mat2[i][j] = Mat[i][j]
            else:
                Mat2[i][j] = Mat2[i][j-1] + Mat[i][j]
        else:
            if j == 0:
                Mat2[i][j] = Mat2[i-1][j] + Mat[i][j]
            else:
                Mat2[i][j] = - Mat2[i-1][j-1] + Mat2[i-1][j] + Mat2[i][j-1] + Mat[i][j]
#print(Mat2)

import numpy as np
A = np.array(Mat2,dtype = np.int64)
n = K.bit_length()
B = np.eye(N)
C = np.array([1] + [0] * (N-1),dtype= np.int64).T
M = np.array([[MOD] * N for _ in range(N)])
AA = [[] for _ in range(n)]
AA[0] = A
for i in range(1,n):
    tmp = np.dot(AA[i-1],AA[i-1])
    AA[i] = np.mod(tmp,M)
i = 0
while K > 0:
    if K % 2 == 1:
        B = np.dot(B,AA[i])
        B = np.mod(B,M)
    K //= 2
    i += 1
D = np.dot(B,C)
print(int(D[N-1]) % MOD)