#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
#include <deque>
#include <map>
#include <vector>
#include <list>
#include <functional>
#include <stack>
#include <unordered_map>
#include <set>
#include <cctype>
#include <cstring>
#include <tuple>
#include <bitset>
#include <unordered_set>
#include <iomanip>
#include <utility>
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define us unsigned short
#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)
#define XOR(a, b) ((a && !b) || (!a && b))
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned int uint;
const int M = 1e9, N = 1e3 + 3, LOGN = log2(N - 1) + 2, MOD = 45989;
const ll LM = 1e18;
int YI = 1, LING = 0;
template <typename T>
struct jvzheng
{
    int n, m;
    vector<vector<T>> a;
    inline jvzheng(int n, int m) noexcept : n(n), m(m)
    {
        a.resize(n);
        for (auto &i : a)
            i.resize(m);
    }
    jvzheng(int n, int m, vector<vector<T>> a) noexcept : n(n), m(m), a(a) {}
    jvzheng(int n) noexcept : n(n), m(n)
    {
        a.resize(n);
        for (auto &i : a)
            i.resize(n);
        for (int i = 0; i < n; i++)
        {
            a[i][i] = 1;
            for (int j = i + 1; j < n; j++)
            {
                a[i][j] = a[j][i] = 0;
            }
        }
    }
    jvzheng(const jvzheng &b) noexcept : n(b.n), m(b.m), a(b.a) {}

    inline jvzheng<T> operator*(const jvzheng<T> &b) noexcept
    {
        if (m != b.n)
            exit(1);
        jvzheng<T> ans(n, b.m);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    ans.a[i][j] += a[i][k] * b.a[k][j];
                }
                ans.a[i][j] %= MOD;
            }
        }
        return ans;
    }
    inline void operator=(const jvzheng<T> &&b) noexcept
    {
        n = b.n;
        m = b.m;
        a = b.a;
    }
    void operator=(const jvzheng<T> &b) noexcept
    {
        n = b.n;
        m = b.m;
        a = b.a;
    }
    inline void operator+=(const jvzheng<T> &&b) noexcept
    {
        if (n != b.n || m != b.m)
            exit(1);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                a[i][j] = a[i][j] + b.a[i][j];
            }
        }
    }
    void operator+=(const jvzheng<T> &b) noexcept
    {
        if (n != b.n || m != b.m)
            exit(1);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                a[i][j] = a[i][j] + b.a[i][j];
            }
        }
    }
    jvzheng<T> operator+(const jvzheng<T> &&b) noexcept
    {
        if (n != b.n || m != b.m)
            exit(1);
        jvzheng<T> ans(n, b.m);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                ans.a[i][j] = a[i][j] + b.a[i][j];
            }
        }
        return ans;
    }
    inline jvzheng<T> operator+(const jvzheng<T> &b) noexcept
    {
        if (n != b.n || m != b.m)
            exit(1);
        jvzheng<T> ans(n, b.m);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                ans.a[i][j] = a[i][j] + b.a[i][j];
            }
        }
        return ans;
    }

    void out_he()
    {
        T ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans = ans + a[i][i];
        }
        cout << (ans + MOD) % MOD;
    }
};
template <typename T>
struct jvjvzheng
{
    int n, m, l;
    vector<vector<jvzheng<T>>> a;
    inline jvjvzheng(const jvjvzheng &b) noexcept : n(b.n), m(b.m), a(b.a) {}
    jvjvzheng(int n, int m, int l, vector<vector<jvzheng<T>>> a) noexcept : n(n), m(m), l(l), a(a) {}
    jvjvzheng(int n, int m, int l) noexcept : n(n), m(m), l(l)
    {
        vector<jvzheng<T>> ca(m, jvzheng<T>(l, l));
        a.insert(a.end(), n, ca);
    }
    inline jvjvzheng<T> operator*(const jvjvzheng<T> &b) noexcept
    {
        if (m != b.n)
            exit(1);
        jvjvzheng<T> ans(n, b.m, l);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < b.m; j++)
            {
                for (int k = 0; k < m; k++)
                {
                    ans.a[i][j] += a[i][k] * b.a[k][j];
                }
            }
        }
        return ans;
    }
    inline void operator=(const jvjvzheng<T> &&b) noexcept
    {
        n = b.n;
        m = b.m;
        a = b.a;
    }
    void operator=(const jvjvzheng<T> &b) noexcept
    {
        n = b.n;
        m = b.m;
        a = b.a;
    }
};
template <typename T>
jvjvzheng<T> km(jvjvzheng<T> ans, jvjvzheng<T> b, int t) noexcept
{
    while (t)
    {
        if (t & 1)
            ans = ans * b;
        b = b * b;
        t >>= 1;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    // freopen("in.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    int n, m, k, a, b;
    cin >> n >> m >> k; //>> a >> b;
    a = 0, b = n - 1;
    jvzheng<ll> x(n, n), y(n, n);
    int u, v;
    while (m--)
    {
        cin >> u >> v;
        u--, v--;
        x.a[u][v]++, x.a[v][u]++;
        y.a[u][u]--, y.a[v][v]--;
    }
    vector<vector<jvzheng<ll>>> va, vb;
    va.resize(1);
    jvzheng<ll> xx((x * x) + y);
    for (int i = 0; i < n; i++)
        y.a[i][i]++;
    va.front().push_back(x), va.front().push_back(xx);
    vb.resize(2);
    vb.front().push_back(jvzheng<ll>(n, n)), vb.front().push_back(y);
    vb.back().push_back(jvzheng<ll>(n)), vb.back().push_back(x);
    cout << (km(jvjvzheng<ll>(1, 2, n, va), jvjvzheng<ll>(2, 2, n, vb), k - 1).a[0][0].a[a][b] + MOD) % MOD;
    return 0;
}