#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
using LL=long long;
class Matrix {
 public:
  int n, m;
  int v[210][210];
  Matrix(int _n = 0, int _m = 0) : n(_n), m(_m) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        v[i][j] = 0;
      }
    }
  }
  friend Matrix operator*(const Matrix& a, const Matrix& b) {
    assert(a.m == b.n);
    Matrix res(a.n, b.m);
    for (int i = 1; i <= a.n; i++) {
      for (int k = 1; k <= a.m; k++) {
        for (int j = 1; j <= b.m; j++) {
          res.v[i][j] = (res.v[i][j] + 1LL * a.v[i][k] * b.v[k][j]) % MOD;
        }
      }
    }
    return res;
  }
};

Matrix qpow(Matrix a, int b) {
  Matrix res(a.n, a.m);
  assert(a.n == a.m);
  for (int i = 1; i <= a.n; i++) {
    res.v[i][i] = 1;
  }
  while (b) {
    if (b & 1) {
      res = res * a;
    }
    a = a * a;
    b >>= 1;
  }
  return res;
}

int n, m, k;
vector<int> e[210];
int deg[210];

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    e[u].push_back(v);
    e[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }
  Matrix trans(2 * n, 2 * n);
  for (int i = n + 1; i <= 2 * n; i++) {
    trans.v[i][i - n] = 1;
    trans.v[i-n][i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (auto& t : e[i]) {
      (trans.v[t + n][i + n] += 1)%=MOD;
    }
    (trans.v[i][i + n] +=MOD -deg[i])%=MOD;
  }
  trans = qpow(trans, k - 1);
  Matrix ret(1, 2 * n);
  ret.v[1][1+n] = 1;
  ret = ret * trans;
  int ans=0;
  for(auto&t:e[n])ans=(ans+ret.v[1][t+n])%MOD;
  ans=(ans-LL(ret.v[1][n])*deg[n]%MOD+MOD)%MOD;
  printf("%d\n", ans);
}