import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;

 
public final class Main {
    public static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    public static void main(String args[] ) throws Exception {
 
        //StringBuffer st = new StringBuffer();
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // StringTokenizer st1 = new StringTokenizer(br.readLine()); 
        FastReader s=new FastReader(); 
        int n = s.nextInt();;
        int m = s.nextInt();;
        long k = s.nextLong();;
        long p=1000000007;
        long[][] g = new long[n+1][n+1];
        while(m-->0){
            //st1 = new StringTokenizer(br.readLine()); 
            int a = s.nextInt();;
            int b = s.nextInt();;
            g[a][b]++;
        }
        g = mmodexpo(g,k,p);
        long res = g[1][n];
        //st.append(res);
        System.out.print(res);
    }
    public static long[][] mmodexpo(long[][] x,long y,long p){
        long[][] res = new long[x.length][x.length];
        for(int i=0;i<x.length;i++){
            res[i][i]=1;
        }
        if(y==0)
            return res;
        
        while(y>0){
            if((y&1)==1)
                res=matmul(res,x,p);;
            
            y=y>>1;
            x=matmul(x,x,p);
        }
        return res;
    }
    public static long[][] matmul(long[][] x1,long[][] x2,long p){
       long[][] res = new long[x1.length][x2[0].length];
       for(int i=0;i<x1.length;i++){
           for(int j=0;j<x2[0].length;j++){
               res[i][j]=0;
               for(int k=0;k<x2.length;k++){
                   res[i][j]=(res[i][j]+(x1[i][k]*x2[k][j])%p)%p;
               }
           }
       }
       return res;
   }
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
    
}