import sys
input=sys.stdin.readline
def main3(n,m,k,lr):
  mod=10**9+7
  dp=[0]*(n+1)
  dp[1]=1
  for _ in range(k):
    sdp=[0]
    for x in dp:sdp.append((sdp[-1]+x)%mod)
    ndp=[0]*(n+1)
    for l,r in lr:
      tmp=sdp[r+1]-sdp[l]
      ndp[l]+=tmp
      if r!=n:
        ndp[r+1]-=tmp
    for i in range(n):ndp[i+1]=(ndp[i+1]+ndp[i])%mod
    dp=ndp
  return dp[n]

if __name__=='__main__':
  n,m,k=map(int,input().split())
  lr=[list(map(int,input().split())) for _ in range(m)]
  ret=main3(n,m,k,lr)
  print(ret)