#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int MOD = 998244353;
vector<int> G[MAXN];
//struct node{
//	int u, v;
//}e[105];
int n, m, k, id[MAXN];
bool vis[MAXN];
int a[MAXN], sz[MAXN];
mt19937 RP(time(0));
set<pair<int, int> > st;
//unordered_set<long long> st;

int dfs(int u, int x){
	vis[u] = 1;
	sz[u] = 1;
	int cnt = 0;
	shuffle(G[u].begin(), G[u].end(), RP);
	for(int v : G[u]){
		if(vis[v]) continue;
		cnt += dfs(v, x);
		sz[u] += sz[v];
	}
	if(x <= sz[u] && sz[u] <= x + k){
		cnt ++;
		sz[u] = 0;
	}
	return cnt;
}

//void solve(int x){
//	if(n / (x + k) < 2) return;
//	for(int i = 1;i <= 5;i ++){
//		for(int j = 1;j <= n;j ++){
//			vis[j] = 0;
//			sz[j] = 0;
//		}
//		int cnt = dfs(1, x);
//		if((!sz[1] || (sz[1] >= x && sz[1] <= x + k)) && cnt >= 2){
//			st.insert(1ll * x * MAXN + cnt + (sz[1] > 0));
//		}
//	}
//}
int main(){
	freopen("cities.in", "r", stdin);
	freopen("cities.out", "w", stdout);
	
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i ++) a[i] = i;
	for(int i = 1;i <= m;i ++){
		int u, v; cin >> u >> v;
//		e[i] = {u, v};
		G[u].push_back(v);
		G[v].push_back(u);
	}
    for(int x = 1;x <= n;x ++){
//    	if(n / (x + k) < 2) continue;
		for(int i = 1;i <= 10;i ++){
			for(int j = 1;j <= n;j ++){
				vis[j] = 0;
			}
			int cnt = dfs(1, x);
			if(sz[1] == 0 || (sz[1] >= x && sz[1] <= x + k)){
				int bk = cnt + (sz[1] > 0);
				if(bk >= 2) st.insert({x, bk});
			}
		}
		if(k == 0){
			while(x < n && n % (x + 1) != 0) x ++;
		}
	}

    cout << st.size() % MOD << '\n';
	return 0;
}