一个州不合法为其内部有欧拉回路，即图连通且每个点度数都为偶数。
(n) 很小，考虑用状压 (DP) 解决本题，设 (f_S) 为集合 (S) 的答案，$ g_S $ 为集合 (S) 的 (w) 和的 (p) 次方。
得转移方程为：
[ f_S= frac{1}{g_S} sum_{ T subset S } f_T g_{S-T}
]
其中 (S,T,S-T) 都为合法的集合。直接枚举子集转移是 (O(n^3))，复杂度无法接受，观察式子后，发现用子集卷积优化即可，
(code:)
#include<bits/stdc++.h>
#define maxn 25
#define maxm 510
#define maxs 2400010
#define p 998244353
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,m,k,all;
ll v[maxn],fa[maxn],d[maxn];
ll f[maxn][maxs],g[maxn][maxs],sum[maxs],inv[maxs],cnt[maxs];
struct edge
{
int x,y;
}e[maxm];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void FWT(ll *a,int type)
{
for(int len=1;len<all;len<<=1)
for(int i=0;i<all;i+=len<<1)
for(int j=i;j<i+len;++j)
a[j+len]=(a[j+len]+a[j]*type+p)%p;
}
ll qp(ll x,ll y)
{
ll v=1;
while(y)
{
if(y&1) v=v*x%p;
x=x*x%p,y>>=1;
}
return v;
}
bool check(int s)
{
if(cnt[s]<=1) return false;
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i) fa[i]=i;
int num=0;
for(int i=1;i<=m;++i)
{
int x=e[i].x,y=e[i].y;
if(!(s&(1<<(x-1)))||!(s&(1<<(y-1)))) continue;
if(find(x)!=find(y)) fa[find(x)]=find(y),num++;
d[x]++,d[y]++;
}
if(num!=cnt[s]-1) return true;
for(int i=1;i<=n;++i)
if(d[i]&1)
return true;
return false;
}
int main()
{
read(n),read(m),read(k),all=1<<n;
for(int i=1;i<all;++i) cnt[i]=cnt[i-lowbit(i)]+1;
for(int i=1;i<=m;++i) read(e[i].x),read(e[i].y);
for(int i=1;i<=n;++i) read(v[i]);
for(int s=0;s<all;++s)
{
for(int i=1;i<=n;++i)
if(s&(1<<(i-1)))
sum[s]+=v[i];
sum[s]=qp(sum[s],k),inv[s]=qp(sum[s],p-2);
if(check(s)) g[cnt[s]][s]=sum[s];
}
f[0][0]=1,FWT(f[0],1);
for(int i=0;i<=n;++i) FWT(g[i],1);
for(int i=1;i<=n;++i)
{
for(int j=0;j<i;++j)
for(int s=0;s<all;++s)
f[i][s]=(f[i][s]+f[j][s]*g[i-j][s]%p)%p;
FWT(f[i],-1);
for(int s=0;s<all;++s) f[i][s]=f[i][s]*inv[s]%p;
FWT(f[i],1);
}
FWT(f[n],-1),printf("%lld",f[n][all-1]);
return 0;
}