//#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using pii = pair; using pll = pair; using pli = pair; #define TEST cerr << "TEST" << endl #define AMARI 998244353 //#define AMARI 1000000007 #define el '\n' #define El '\n' ll table[10][10]; struct hs{ size_t operator()(const pair,int> &p)const{ auto h2 = hash{}(p.second); for(int i = 0; i < p.first.size(); i++){ h2 ^= table[p.first[i]][i]; } return h2; } }; int n,m,k; unordered_map,int>,ll,hs> mp; vector> g; ll saiki(vector & a,int v){ /* for(int i = 0; i < n; i++){ cerr << a[i] << ' '; } cerr << el; */ if(mp.find(pair(a,v)) != mp.end())return mp[pair(a,v)]; ll ans = 0; for(int i = 0; i < g[v].size(); i++){ if(a[g[v][i]] >= k)continue; a[g[v][i]]++; ans += saiki(a,g[v][i]); if(ans >= AMARI)ans -= AMARI; a[g[v][i]]--; } /* for(int i = 0; i < n; i++){ cerr << a[i] << ' '; } cerr << ans << el; */ return mp[pair(a,v)] = ans; } #define MULTI_TEST_CASE false void solve(void){ //問題を見たらまず「この問題設定から言えること」をいっぱい言う //一個回答に繋がりそうな解法が見えても、実装や細かい詰めに時間がかかりそうなら別の方針を考えてみる //添え字回りで面倒になりそうなときは楽になる言い換えを実装の前にじっくり考える //ある程度考察しても全然取っ掛かりが見えないときは実験をしてみる //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く //M <= 15 //K == 1 なら bitDP ができる // dp[i][j][S] = (iからスタートして今 j にいて、使った点の集合が S のものが何通りあるか) //K^N が意外と小さいので、 bitDP の (k+1)進 ver が通る cin >> n; cin >> m >> k; g.resize(n); while(m--){ int u,v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } vector b(n,k); for(int i = 0; i < n; i++){ mp[pair(b,i)] = 1; } vector a(n,0); ll ans = 0; for(int i = 0; i < n; i++){ a[i]++; ans += saiki(a,i); a[i]--; } cout << ans % AMARI << el; return; } // 疑似乱数(XorShift) unsigned long xor128(void) { static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned long t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } void calc(void){ for(int i = 0; i < 10; i++){ for(int j = 0; j < 10; j++){ table[i][j] = xor128(); } } return; } signed main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE)cin >> t; while(t--){ solve(); } return 0; }