博主的 (mathtt{BiBi}) 时间

感觉学到了几个卡常小技巧。~~（这题卡空间又卡时间可还行）~~

话说在 (mathtt{usOJ}) 上只有 (50pts)。（其他都可过）

( ext{Solution})

可以发现，不合法的州就是内部有欧拉回路的州。

因此，我们只需要判断州联通且没有奇数度的点，这个州就不合法。

我们令 (f[S]) 为总集合为 (S) 时的答案，(g[S]) 是 (S) 集合的 (w) 值之和的 (p) 次方。

这里有一个~~在本蒟蒻眼中看起来并不~~显然的 (mathtt{DP})：

[f[S]=frac{1}{g[S]}*sum_{S'subset S}f[S']*g[S-S'] ]

其实就是把 (S-S') 看作新划分的一个州，把前面的分式提进去就是新划分的州的贡献（(frac{g[S-S']}{g[S]})）。那么 (f[S]) 其实是多个划分的乘积之和。

然后可以把式子转化为：

[f[S]=sum f[S_0]g[S_1] ]

其中 (S_0igcup S_1=S,S_0igcap S_1=emptyset)。

这就是子集卷积。所以关于条件二，我们套路地加上一维表示这个集合中 (1) 的个数。

[f[i][S]=sum f[j][S0]*g[i-j][S1] ]

然后就可以用 (mathtt{FWT}) 了。

( ext{Code})

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

const int mod=998244353;

int n,m,p,u[400],v[400],w[25],lim,fa[25],deg[25],cnt,val[(1<<21)+5],f[25][(1<<21)+5],g[25][(1<<21)+5],bit[(1<<21)+5],inv[(1<<21)+5];
bool ok[(1<<21)+5];

inline void inc(int &x,const int y) {
    x=x+y;
    if(x>=mod) x=x-mod;
    if(x<0) x=x+mod;
}

inline int mul(const int x,const int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int Find(int x) {return x==fa[x]?x:fa[x]=Find(fa[x]);}

int qkpow(int x,int y) {
    int r=1;
    while(y) {
        if(y&1) r=mul(r,x);
        x=mul(x,x); y>>=1;
    }
    return r;
}

void FWT_or(int *t,const int op=1) {
    for(int i=2;i<=lim;i<<=1)
        for(int p=(i>>1),j=0;j<lim;j=j+i)
            for(int k=j;k<j+p;++k)
                inc(t[k+p],t[k]*op);
}

int main() {
    int x,y;
    n=read(9),m=read(9),p=read(9); lim=1<<n;
    rep(i,1,m) u[i]=read(9),v[i]=read(9);
    rep(i,1,n) w[i]=read(9);
    rep(S,0,lim-1) {
        cnt=0;
        rep(i,0,n-1) {
            if((S>>i)&1) ++cnt,val[S]+=w[i+1];
            deg[i+1]=0,fa[i+1]=i+1;
        }
        bit[S]=cnt;
        rep(i,1,m)
            if(((S>>u[i]-1)&1)&&((S>>v[i]-1)&1)) {
                x=Find(u[i]),y=Find(v[i]);
                if(x^y) fa[x]=y,--cnt;
                ++deg[u[i]],++deg[v[i]];
            }
        if(cnt>1) ok[S]=1;
        cnt=0;
        rep(i,1,n) cnt+=(deg[i]&1);
        if(cnt) ok[S]=1;
        if(ok[S])
            g[bit[S]][S]=qkpow(val[S],p);
        inv[S]=qkpow(qkpow(val[S],mod-2),p);
        // 注意不是在 S 是合法州时才算 inv，因为 f[S] 可以表示几个州合在一起的方案
    }
    f[0][0]=1;
    FWT_or(f[0]);
    rep(i,0,n) FWT_or(g[i]);
    rep(i,1,n) {
        rep(j,0,i-1)
            rep(k,0,lim-1)
                inc(f[i][k],mul(f[j][k],g[i-j][k]));
        FWT_or(f[i],-1);
        rep(j,0,lim-1) // 因为 f[i] 会在之后做出贡献，需要将不合法的清空，记得除以 g[j]
            if(bit[j]^i) f[i][j]=0;
            else f[i][j]=mul(f[i][j],inv[j]);
        if(i^n) FWT_or(f[i]);
    }
    print(f[n][lim-1],'
');
    return 0;
}