#include #define MOD 998244353ll using namespace std; using ll = long long; bool can_set_left(vector >& graph, ll s, int i, ll t){ for(int j = 0; j < t; ++j){ if(i == j || ((s >> j) & 1) == 0 || graph[j][i] == 0){ continue; } return false; } return true; } ll calc_dp(vector >& graph, vector& dp, ll s, ll t){ if(dp[s] == -1){ dp[s] = 0; for(int i = 0; i < t; ++i){ if(((s >> i) & 1) == 0){ continue; } if(!can_set_left(graph, s, i, t)){ continue; } dp[s] += calc_dp(graph, dp, s - (1 << i), t); } dp[s] %= MOD; } return dp[s]; } ll nPk(ll n, ll k){ ll ret = 1; for(ll i = n; i > n - k; --i){ ret *= i; ret %= MOD; } return ret; } int main(){ ll N, M, K; cin >> N >> M >> K; vector > edges(K, pair({})); unordered_set st = {}; for(auto& [x, y] : edges){ cin >> x >> y; --x; --y; st.insert(x); st.insert(y); } unordered_map mp = {}; for(auto itr = st.begin(); itr != st.end(); ++itr){ mp[*itr] = mp.size(); } int t = mp.size(); vector > graph(t, vector(t)); for(auto& [x, y] : edges){ graph[mp[x]][mp[y]] = 1; } vector dp(1 << t, -1); dp[0] = 1; ll ans = nPk(N, N - t) * calc_dp(graph, dp, (1 << t) - 1, t) % MOD; ll p1 = nPk(N - 1, N - t); ll p2 = nPk(N - 1, N - t - 1); for(int i = 0; i < M; ++i){ if(st.find(i) != st.end()){ int id = mp[i]; if(!can_set_left(graph, (1 << t) - 1, id, t)){ continue; } ans += MOD - p1 * calc_dp(graph, dp, (1 << t) - 1 - (1 << id), t) % MOD; } else{ ans += MOD - p2 * calc_dp(graph, dp, (1 << t) - 1, t) % MOD; } ans %= MOD; } cout << ans << endl; return 0; }