#include using namespace std; #include using mint = atcoder::modint998244353; #define rep(i, l, r) for (int i = (int)(l); i<(int)(r); i++) #define ll long long //vectorであらわされるn進数を10進数に変換する template T change_base_to_ten(const vector& A, T n) { T ret = 0; T mul = 1; for (int i = (int)A.size()-1; i >= 0; i--) { ret += mul * A[i]; mul *= n; } return ret; } //10進数でxのものをn進数に変換する template vector change_base_from_ten(T x, T n, int siz) { vector ret; while(x != 0) { ret.push_back(x%n); x /= n; } while((int)ret.size() < siz) ret.push_back(0); reverse(ret.begin(), ret.end()); return ret; } //n進法の桁のvectorであるSをm進法に変換する template vector change_base(const vector& S, T n, T m) { T ten = change_base_to_ten(S, n); return change_base_from_ten(ten, m); } int pow(int x, int k) { int ret = 1; rep(_, 0, k) ret *= x; return ret; } int main() { int N, M, K; cin >> N >> M >> K; vector> G(N); rep(i, 0, M) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } vector> dp(pow(K+1, N), vector(N)); rep(i, 0, N) { vector T(N, 0); T[i]++; // cout << change_base_to_ten(T, K+1) << endl; dp[change_base_to_ten(T, K+1)][i] = 1; } rep(S, 0, pow(K+1, N)) { // cout << "S = " << S << endl; vector T = change_base_from_ten(S, K+1, N); // cout << "T = " << endl; // for (auto v : T) cout << v << " "; // cout << endl; rep(i, 0, N) { // cout << "i = " << i << endl; for (int to : G[i]) { // cout << "to = " << to << endl; if (T[to] >= K) continue; auto nT = T; nT[to]++; dp[change_base_to_ten(nT, K+1)][to] += dp[S][i]; } } } mint ans = 0; rep(i, 0, N) ans += dp.back()[i]; cout << ans.val() << endl; }