赤い頂点 \(v\) の内，\(deg_{v} \equiv 1 \ mod \ 2\) のもの全体を \(X\) とおく．
場合分けして数える． \(X\) がら丁度 \(i\) 個 (\(i \in [0,N]\)かつ\(i \equiv 0 \ mod\ 2\)) 選ぶ場合の数の合計が答え．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m,k; cin >> n >> m >> k;
vvll to(n);
vll deg_out(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
deg_out[a]++;
deg_out[b]++;
// to[a].push_back(b);
// to[b].push_back(a);
}
ll c1 = 0;
rep(i,n){
if(deg_out[i] % 2 == 1) c1++;
}
mint ans = 0;
Comb<mint, (ll)(2e5)+10> co;
for(int i = 0; i <= n ; i+=2){
ans += co.nCr(c1, i) * co.nCr(n-c1, k-i);
}
cout << ans.val() << endl;
return 0;
}
