Description：

给出一个计算机网络，每个点有权值，病毒 $x$ 会把一些点的权值改成 $c[i]\land x$ ，如果一条边两端点权值相同，那么这条边是危险的，询问有多少种感染方式（感染集合和权值）。

$1\le n \le 500000$

Solution：

首先把边权设成 $c[u]\land c[v]$ ，那么这些边两端点要么都不感染，要么都感染，于是对于每种边权的边用并查集统计一下联通块个数， $2^{联通快个数}$ 就是这个的贡献，由于数据范围很大所以不能暴力清空 $f[]$ 数组，用 $map$ 来搞。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<cstring>

using namespace std;

typedef long long ll;

#define MAXN 500010

#define MOD 1000000007

ll n,m,k;

struct edge

{

	ll u,v;

};

ll ans,c[MAXN];

map<ll,vector<edge> > e;

map<ll,ll> f;

ll find(ll x){return ((!f.count(x) || f[x] == x) ? x : f[x] = find(f[x]));}

inline ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	scanf("%I64d%I64d%I64d",&n,&m,&k);

	for(int i = 1;i <= n;++i)scanf("%I64d",&c[i]);

	ll a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%I64d%I64d",&a,&b);

		e[c[a] ^ c[b]].push_back((edge){a,b});

	}

	for(map<ll,vector<edge> >::iterator i = e.begin();i != e.end();++i)

	{

		f.clear();set<ll> dsu;

		for(vector<edge>::iterator p = (i -> second).begin();p != (i -> second).end();++p)

		{

			ll fx = find(p -> u),fy = find(p -> v);

			if(fx < fy)f[fy] = fx;

			else f[fx] = fy;

			dsu.insert(p -> u);dsu.insert(p -> v);

		}

		ll sum = n - dsu.size();dsu.clear();

		for(vector<edge>::iterator p = (i -> second).begin();p != (i -> second).end();++p)

		{

			dsu.insert(find(min(p -> u,p -> v)));

		}

		ans = (ans + power(2ll,dsu.size() + sum)) % MOD;

	}

	ans = (ans + power(2ll,n) * (power(2ll,k) - e.size() + MOD) % MOD) % MOD;

	cout << ans << endl;

	return 0;

}