本题属于集合划分容斥，更多关于集合划分容斥的信息可观看 详细揭秘：集合划分容斥的容斥系数。
题意
给定一个 \(n\) 个点 \(m\) 条边的图以及一个长为 \(n\) 的序列 \(a_{1\dots n}\)，有一常数 \(C\)，你需要求出有多少序列 \(b_{1\dots n}\) 满足 \(0\le b_i\le a_i\)，\(\forall (u,v)\in E,b_u\ne b_v\)，\(\text{xor}_{i=1}^nb_i=C\)。
\(n\le 15\)。
思路
考虑 \(m=0\) 怎么做，从高至低枚举第一个不全顶到上界的位 \(d\)，则低 \(d-1\) 位只需要一个在第 \(d\) 位不顶到上界的数进行调整，其余数任选即可。
令等价类为相等的数的集合，则令集合幂级数 \([x^S]F(x)\) 等于 \(1\) 当且仅当 \(S\) 内点在图上为独立集。容斥系数 \(H(x)=\ln (F(x)+1)\) 可以直接求出。
考虑一个状态的答案，我们只关注每个等价类内部的最小值。每个大小为偶数的等价类均可随便取，大小为奇数的等价类的最小值（称为关键点）构成 \(m=0\) 的子问题。
设 \(f_{S,T}\) 表示当前已经考虑了 \(S\) 内的点，其中关键点的集合为 \(T\) 的方案数，时间复杂度为 \(O(4^n)\)。
此时记录了大量无用信息，我们将 \(a\) 从小到大排序，逐个尝试加入关键点。设当前加入到 \(i\)，则 \([1,i)\) 的点已经必然在考虑的点集中，只需要记录它们是否在关键点集中；\([i,n]\) 的点必然不在当前关键点集中，只需要记录它们是否在已考虑点集中。这样状态数就减小至 \(2^n\)，再加上枚举子集，时间复杂度为 \(O(3^nn+2^n(m+n\log V))\)。
参考代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int S=1<<15,N=15+2,M=N*N,mod=998244353;
namespace Init{
inline int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
return x>=y?x-y:x-y+mod;
}
int pc[S],inv[N],fac[N];
inline void Prefix(int n){
int m=__lg(n);
for(int i=0;i<n;i++)
pc[i]=pc[i/2]+(i&1);
inv[1]=1;
for(int i=2;i<=m;i++)
inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
fac[0]=1;
for(int i=1;i<=m;i++)
fac[i]=1ll*fac[i-1]*i%mod;
}
}
using namespace Init;
namespace Poly{
int n,m;
inline void init(int N){
n=N,m=__lg(n);
}
inline void FWT(int *c){
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(j>>i&1)
c[j]=add(c[j],c[j^(1<<i)]);
}
inline void IFWT(int *c){
for(int i=0;i<m;i++)
for(int j=n-1;j>=0;j--)
if(j>>i&1)
c[j]=dec(c[j],c[j^(1<<i)]);
}
int F[N][S],G[N][S],H[N][S];
inline void mul(int *a,int *b,int *c){
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
F[i][j]=G[i][j]=H[i][j]=0;
for(int i=0;i<n;i++)
F[pc[i]][i]=a[i],G[pc[i]][i]=b[i];
for(int i=0;i<=m;i++)
FWT(F[i]),FWT(G[i]);
for(int k=0;k<=m;k++){
for(int i=0;i<=k;i++)
for(int j=0;j<n;j++)
H[k][j]=(H[k][j]+1ll*F[i][j]*G[k-i][j])%mod;
IFWT(H[k]);
}
for(int i=0;i<n;i++)
c[i]=H[pc[i]][i];
}
inline void ln(int *a,int *b){
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
F[i][j]=G[i][j]=0;
for(int i=0;i<n;i++)
F[pc[i]][i]=a[i];
for(int i=0;i<=m;i++)
FWT(F[i]);
for(int p=0;p<n;p++)
for(int i=1;i<=m;i++){
int s=0;
for(int j=1;j<i;j++)
s=(s+1ll*(i-j)*F[j][p]%mod*G[i-j][p])%mod;
s=dec(1ll*i*F[i][p]%mod,s);
G[i][p]=1ll*s*inv[i]%mod;
}
for(int i=0;i<=m;i++)
IFWT(G[i]);
for(int i=0;i<n;i++)
b[i]=G[pc[i]][i];
}
}
using Poly::init;
using Poly::ln;
int n,m,p[N],r[N],F[S],H[S],dp[N][2][2],f[S],g[S];
ll a[N],b[N],C;
struct node{
int u,v;
}e[M];
inline int solve(int s){
int ct=0;
for(int i=0;i<n;i++)
if(s>>i&1)
b[++ct]=a[p[i]];
int ans=0,fl=0;
for(int d=59;d>=0;d--){
ll w=1ll<<d;
int c=0,v=C>>d&1,wc=w%mod;
dp[0][0][0]=1;
for(int i=1;i<=ct;i++){
if(b[i]&w){
b[i]^=w,c++;
int v=(b[i]+1)%mod;
dp[i][0][0]=1ll*dp[i-1][0][1]*v%mod;
dp[i][0][1]=1ll*dp[i-1][0][0]*v%mod;
dp[i][1][0]=(1ll*dp[i-1][1][1]*v+1ll*dp[i-1][1][0]*wc+dp[i-1][0][0])%mod;
dp[i][1][1]=(1ll*dp[i-1][1][0]*v+1ll*dp[i-1][1][1]*wc+dp[i-1][0][1])%mod;
}else{
int v=(b[i]+1)%mod;
dp[i][0][0]=1ll*dp[i-1][0][0]*v%mod;
dp[i][0][1]=1ll*dp[i-1][0][1]*v%mod;
dp[i][1][0]=1ll*dp[i-1][1][0]*v%mod;
dp[i][1][1]=1ll*dp[i-1][1][1]*v%mod;
}
}
ans=(ans+dp[ct][1][v])%mod;
if((c&1)!=v){ fl=1;break; }
}
if(!fl) ans++;
return ans;
}
inline bool cmp(int i,int j){
return a[i]<a[j];
}
inline int get(int s,int l,int r){
return s&(((1<<r+1)-1)^((1<<l)-1));
}
int main(){
n=read(),m=read(),C=read();
for(int i=0;i<n;i++)
a[i]=read(),p[i]=i;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
r[p[i]]=i;
for(int i=1;i<=m;i++)
e[i].u=r[read()-1],e[i].v=r[read()-1];
int u=1<<n;
Prefix(u),init(u);
for(int s=0;s<u;s++){
bool fl=1;
for(int i=1;i<=m;i++)
if((s>>e[i].u&1)&&(s>>e[i].v&1)){
fl=0;
break;
}
F[s]=fl;
}
ln(F,H);
f[0]=1;
for(int i=0;i<n;i++){
for(int s=0;s<u;s++){
int v=f[s];
if(!v) continue;
int cur=((1<<i)-1)|get(s,i,n-1);
if(cur>>i&1){
int t=s^(1<<i);
g[t]=add(g[t],v);
continue;
}
for(int T=(u-1)^cur^(1<<i),t=T;;t=(t-1)&T){
if(pc[t]&1) g[s|t]=(g[s|t]+1ll*v*H[t|(1<<i)]%mod*(a[p[i]]%mod+1))%mod;
else g[s|t|(1<<i)]=(g[s|t|(1<<i)]+1ll*v*H[t|(1<<i)])%mod;
if(!t) break;
}
}
for(int s=0;s<u;s++)
f[s]=g[s],g[s]=0;
}
int ans=0;
for(int s=0;s<u;s++)
ans=(ans+1ll*f[s]*solve(s))%mod;
write(ans);
flush();
}