Untitled

#include <iostream>
#include <bits/stdc++.h>
 
// policy based datastructure
// #include <ext/pb_ds/assoc_container.hpp>
// // #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define indexed_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
 
#define ll long long
// #define ll int
#define en '\n'
#define ff first
#define ss second
#define pb push_back
#define MP make_pair
#define mod 1000000007
#define mod2 998244353
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
using namespace std;
 
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef priority_queue<ll> pqi;
typedef priority_queue<ll, vi, greater<ll>> minpqi;
typedef pair<ll, ll> pii;
#define debarr(a, n)            \
    cout << #a << " : ";        \
    for (int i = 0; i < n; i++) \
        cerr << a[i] << " ";    \
    cerr << endl;
#define debmat(mat, row, col)         \
    cout << #mat << " :\n";           \
    for (int i = 0; i < row; i++)     \
    {                                 \
        for (int j = 0; j < col; j++) \
            cerr << mat[i][j] << " "; \
        cerr << endl;                 \
    }
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p)
{
    return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const unordered_set<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const unordered_map<S, T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const map<S, T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
void dbs(string str, T t) { cerr << str << " : " << t << "\n"; }
template <class T, class... S>
void dbs(string str, T t, S... s)
{
    int idx = str.find(',');
    cerr << str.substr(0, idx) << " : " << t << ",";
    dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b)
{
    cerr << "[";
    for (T i = a; i != b; ++i)
    {
        if (i != a)
            cerr << ", ";
        cerr << *i;
    }
    cerr << "]\n";
}
#define all(x) x.begin(), x.end()
#define present(c, key) (find(all(c), key) != c.end())
#define tr(c, it) for (auto it : c)
#define fr(i, s, e) for (ll i = s; i < e; i++)
#define revfr(i, s, e) for (ll i = s - 1; i >= e; i--)
#define getv(v, n)             \
    for (ll i = 0; i < n; i++) \
        cin >> v[i];
 
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    for (auto element : v)
    {
        os << element << ' ';
    }
    return os;
}
template <typename T>
istream &operator>>(istream &ins, vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
        ins >> v[i];
    return ins;
}
inline void add(ll &a, ll b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}
 
inline void sub(ll &a, ll b)
{
    a -= b;
    if (a < 0)
        a += mod;
}
 
inline ll mul(ll a, ll b, ll p = mod)
{
    return (ll)((long long)a * b % p);
}
 
inline ll power(ll a, long long b, ll p = mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = mul(res, a, p);
        }
        a = mul(a, a, p);
        b >>= 1;
    }
    return res;
}
inline ll binpow(ll a, long long b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}
inline ll inv(ll a, ll p = mod)
{
    a %= p;
    if (a < 0)
        a += p;
    ll b = p, u = 0, v = 1;
    while (a)
    {
        ll t = b / a;
        b -= t * a;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    if (u < 0)
        u += p;
    return u;
}
// inline ll lsb(ll x)
// {
//     return x&(~(x-1));
// }
// ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime
// {
//     // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime
//     ll x = power(b,c,p-1);  // so we first find remainder when b^c is divided by p-1
//     return (power(a,x,p));  // then just do (a^remainder)%p
 
// }
ll gcd(ll a, ll b)
{
    if (a == 0 or b == 0)
        return a ^ b;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
    return a * (b / gcd(a, b));
}
void fread()
{
    // #ifdef
    freopen("./input.txt", "r", stdin);
    freopen("./output.txt", "w", stdout);
    // #endif
}
 
vvi& operator*(vvi &a,vvi &b){
    ll n=a.size(),m=a[0].size(),p=b[0].size();
    vvi c(n,vi(p,0));
    fr(i,0,n){
        fr(j,0,p){
            fr(k,0,m)
            {
                c[i][j]+=(a[i][k]*b[k][j])%mod;
                if(c[i][j]>=mod)c[i][j]-=mod;
            }
        }
    }
    fr(i,0,n)fr(j,0,p)a[i][j]=c[i][j];
    // return c;
    return a;
}
ostream &operator<<(ostream &os,vvi &a){
    for(auto x:a){
        for(auto y:x){
            os<<y<<" ";
        }
        os<<"\n";
    }
    return os;
}
vvi dist;
ll n;
ll path(ll k){
    vvi ans(n,vi(n,0));
    fr(i,0,n)ans[i][i]=1;
    while(k){
        if(k&1){
            ans=(ans*dist);
        }
        k/=2;
        dist=(dist*dist);
    }
    return ans[0][n-1];
}
void solve()
{
    ll m,k;
    cin>>n>>m>>k;
    dist.clear();
    dist.assign(n,vi(n,0));
    fr(i,0,m){
        ll a,b;
        cin>>a>>b;
        a--,b--;
        dist[a][b]=1;
    }
    cout<<path(k)<<"\n";
}
 
using namespace std;
int main()
{
    fast
    // pre();
    // fread();
    ll _t = 1;
    // cin >> _t;
    fr(i, 1, _t + 1)
    {
        // cerr<<"i="<<i<<en;
        solve();
    }
    return 0;
}