#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define fi first
#define pll pair<ll, ll>
#define se second
#define lll __int128
#define ld long double
#define all(a) a.begin() + 1, a.end()
#define iofast                   \
    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0)
#define lowbit(i) (i & (-i))
using namespace std;
const int maxn = 1e6 + 5, mod = 1000000007;
// modint
template <int MOD>
struct Fp
{
    ll val;
    Fp(ll v = 0) : val(v % MOD)
    {
        if (val < 0)
            val += MOD;
    }
    int getmod() const { return MOD; }
    Fp operator-() const { return val ? MOD - val : 0; }
    Fp operator+(const Fp &r) const { return Fp(*this) += r; }
    Fp operator-(const Fp &r) const { return Fp(*this) -= r; }
    Fp operator*(const Fp &r) const { return Fp(*this) *= r; }
    Fp operator/(const Fp &r) const { return Fp(*this) /= r; }
    Fp &operator+=(const Fp &r)
    {
        val += r.val;
        if (val >= MOD)
            val -= MOD;
        return *this;
    }
    Fp &operator-=(const Fp &r)
    {
        val -= r.val;
        if (val < 0)
            val += MOD;
        return *this;
    }
    Fp &operator*=(const Fp &r)
    {
        val = val * r.val % MOD;
        return *this;
    }
    Fp &operator/=(const Fp &r)
    {
        ll a = r.val, b = MOD, u = 1, v = 0;
        while (b)
        {
            ll t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0)
            val += MOD;
        return *this;
    }
    bool operator<(const Fp &r) const { return this->val < r.val; }
    bool operator==(const Fp &r) const { return this->val == r.val; }
    bool operator!=(const Fp &r) const { return this->val != r.val; }
    friend istream &operator>>(istream &is, Fp<MOD> &x)
    {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0)
            x.val += MOD;
        return is;
    }
    friend ostream &operator<<(ostream &os, const Fp<MOD> &x) { return os << x.val; }
    friend Fp<MOD> modpow(const Fp<MOD> &r, ll n)
    {
        if (n == 0)
            return 1;
        if (n < 0)
            return modpow(modinv(r), -n);
        Fp<MOD> t = modpow(r, n / 2);
        t = t * t;
        if (n & 1)
            t = t * r;
        return t;
    }
    friend Fp<MOD> modinv(const Fp<MOD> &r)
    {
        ll a = r.val, b = MOD, u = 1, v = 0;
        while (b)
        {
            ll t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        return Fp<MOD>(u);
    }
};
const int MOD = 998244353; // 看取得哪个模！！！！！！！！！！！
typedef Fp<MOD> mint;
mint qkpow(mint a, ll p = MOD - 2)
{
    mint t = 1, tt = a;
    while (p)
    {
        if (p & 1)
            t = t * tt;
        tt = tt * tt;
        p >>= 1;
    }
    return t;
}
class matrix
{
public:
    static const int n = 200;
    // mint x[n][n];
    array<array<mint, n>, n> x;
    matrix()
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                x[i][j] = 0;
        }
    }
    void init()
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                x[i][j] = 0;
        }
        rep(i, 0, n - 1)
            x[i][i] = 1;
    }
    matrix operator*(matrix b)
    {
        matrix ret;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                for (int k = 0; k < n; k++)
                {
                    (ret.x[i][j] += x[i][k] * b.x[k][j]);
                }
            }
        }
        return ret;
    }
    void show()
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cout << x[i][j] << " ";
            }
            cout << endl;
        }
    }
    matrix qkpow(ll p)
    {
        matrix ret;
        ret.init();
        matrix b = *this;
        while (p)
        {
            if (p & 1)
                ret = ret * b;
            b = b * b;
            p >>= 1;
        }
        return ret;
    }
};

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    matrix mat;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        mat.x[u][v] += 1;
        mat.x[v][u] += 1;
        mat.x[u + n][u] -= 1;
        mat.x[v + n][v] -= 1;
    }
    if (k == 1)
    {
        cout << mat.x[0][n - 1] << "\n";
        return;
    }
    for (int i = 0; i < n; i++)
    {
        mat.x[i][i + n] = 1;
        mat.x[i + n][i] += 1;
    }
    matrix a;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if (mat.x[0][i].val && mat.x[i][j].val)
            {
                a.x[0][j] += 1;
            }
        }
        a.x[0][i + n] = mat.x[0][i];
    }
    if (k == 2)
    {
        cout << a.x[0][n - 1] << "\n";
        return;
    }
    // a.show();
    k -= 2;
    // mat.show();
    mat = mat.qkpow(k);
    mat = a * mat;
    // mat.show();
    cout << mat.x[0][n - 1] << endl;
}
int main()
{
    iofast;
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    // cout << endl;
    //  system("pause");
}