我太难了

帮帮可怜的被卡常到死的儿童：94 pts

code：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int mod=998244353;
int n,m,p,st[100005],ed[100005],ok[(1<<21)+5],sum[(1<<21)+5],inv[(1<<21)+5];
int popcount[(1<<21)+5],d[25],fa[25],g[23][(1<<21)+5],f[23][(1<<21)+5],w[25];
int Power(int x,int y) {
    register int ret=1;
    while(y) {
        if(y&1)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ret;
}
void Or(int a[],int flag){
    for(register int i=1;i<(1<<n);i<<=1){
        for(register int j=i;j<(1<<n);++j){
            if(i&j){
                a[j]+=flag*a[i^j];
                if(a[j]>=mod)a[j]-=mod;
                else if(a[j]<0)a[j]+=mod;
            }
            else j+=i-1;
        }
    } 
}
int gf(int x){
    return x==fa[x]?x:fa[x]=gf(fa[x]);
}
int main() {
    scanf("%d%d%d",&n,&m,&p);
    int len=(1<<n);
    for(int i=1;i<=m;i++)scanf("%d%d",&st[i],&ed[i]);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int S=0;S<len;S++){
        for(int i=1;i<=n;i++){
            if(S&(1<<(i-1)))sum[S]+=w[i],++popcount[S];
            d[i]=0,fa[i]=i;
        }
        register int tmp=popcount[S];
        for(register int i=1;i<=m;++i){
            if(((1<<(st[i]-1))&S)&&((1<<(ed[i]-1))&S)){
                int fx=gf(st[i]),fy=gf(ed[i]);
                if(fx^fy)fa[fx]=fy,tmp--;
                d[st[i]]++,d[ed[i]]++;
            }
        }
        if(tmp>1)ok[S]=1;
        else {
            int cnt=0;
            for(int i=1;i<=n;i++)cnt+=(d[i]&1);
            if(cnt)ok[S]=1;
        }
        if(ok[S])g[popcount[S]][S]=Power(sum[S],p);
        inv[S]=Power(Power(sum[S],mod-2),p);
    }
    for(int i=0;i<=n;i++)Or(g[i],1);
    f[0][0]=1,Or(f[0],1);
    for(int i=1;i<=n;i++){
        for(register int j=0;j<i;j++){
            for(register int k=0;k<len;k++)f[i][k]=(f[i][k]+1ll*f[j][k]*g[i-j][k])%mod;
        }
        Or(f[i],-1);
        for(int j=0;j<len;j++)f[i][j]=(popcount[j]==i?1ll*f[i][j]*inv[j]%mod:0);
        if(i!=n)Or(f[i],1);
    }
    printf("%d\n",f[n][len-1]);
}