求助卡常

#include <bits/stdc++.h>
using namespace std;
const int maxn = 17, N = (1 << 16) + 5, mod = 1e9 + 7;
inline int add(int x, int y) {
	x += y;
	return (x >= mod ? x % mod : x);
}
struct Poly {
	vector<int> a;
	inline void resize(int N) {
		a.resize(N);
	}
	inline int size() {
		return a.size();
	}
	inline int& operator[](int x) {
		return a[x];
	}
	inline void clear() {
		a.clear();
	}
	inline auto begin() {
		return a.begin();
	}
	inline auto end() {
		return a.end();
	}
	inline void fwt(int f) {
		int n = size();
		for (int h = 2; h <= n; h <<= 1)
			for (int i = 0; i < n; i += h)
				for (int j = i; j < i + h / 2; j++) 
					a[j + h / 2] = add(1ll * a[j] * f % mod, a[j + h / 2]);
	}
	inline friend Poly operator+(Poly f, Poly g) {
		int n = f.size();
		for (int i = 0; i < n; i++)
			f[i] = (f[i] + g[i]) % mod;
		return f;
	}
} tf[maxn], tg[maxn], th[maxn];
int cnt[N];
inline Poly operator*(Poly &f, Poly &g) {
	int n = f.size(), l = 0;
	for (l = 0; (1 << l) <= n; l++) {
		fill(tf[l].begin(), tf[l].end(), 0);
		fill(tg[l].begin(), tg[l].end(), 0);
		fill(th[l].begin(), th[l].end(), 0);
	}
	for (int i = 0; i < n; i++)
		tf[cnt[i]][i] = f[i], tg[cnt[i]][i] = g[i];
	for (int i = 0; i < l; i++)
		tf[i].fwt(1), tg[i].fwt(1);
//	cout << "adsf" << endl;
	for (int i = 0; i < l; i++)
		for (int j = 0; j < l; j++)
			if(i + j < l) {
				for (int k = 0; k < n; k++)
					th[i + j][k] = add(th[i + j][k], 1ll * tf[i][k] * tg[j][k] % mod);
			}
	for (int i = 0; i < l; i++)
		th[i].fwt(mod - 1);
	for (int i = 0; i < n; i++)
		f[i] = th[cnt[i]][i];
	//cout << "adf" << endl;
	return f;
}
int inv[maxn];
Poly get_s_exp(Poly &f) {
	Poly ans; ans.resize(f.size());
	ans[0] = 1;
	for (int i = 1; i < f.size(); i++) {
		for (int j = 1; j <= i; j++)
			ans[i] = add(ans[i], 1ll * j * f[j] % mod * ans[i - j] % mod);
		ans[i] = 1ll * ans[i] * inv[i] % mod;
	}
	return ans;
}
Poly get_exp(Poly &f) {
	int n = f.size(), l = 0;
	for (l = 0; (1 << l) <= n; l++) 
		fill(tf[l].begin(), tf[l].end(), 0);
	//cout << l << "adf" << endl;
	for (int i = 0; i < n; i++)
		tf[cnt[i]][i] = f[i];
	for (int i = 0; i < l; i++)
		tf[i].fwt(1);
	Poly t; t.resize(l);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < l; j++)
			t[j] = tf[j][i];
		t = get_s_exp(t);
		for (int j = 0; j < l; j++)
			tf[j][i] = t[j];
	}
	for (int i = 0; i < l; i++)
		tf[i].fwt(mod - 1);
	for (int i = 0; i < n; i++)
		f[i] = tf[cnt[i]][i];
	return f;
}
int n, msk[maxn], m;
int cal(int S, int T) {
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += ((S >> i - 1) & 1) * cnt[msk[i] & T];
	return ans;
}
Poly tp;
int pw[maxn * maxn], e[N];
#define lowbit(x) (x & (-x))
Poly Trans(Poly f, int coef) {
	tp.resize(1 << n);
	for (int i = n; i >= 1; i--) {
	//	cout << i << endl;
		for (int j = 0; j < (1 << n); j++)
			tp[j] = ((j & (1 << i - 1)) ? 0 : 1ll * f[j] % mod * cal(j & ((1 << i) - 1), 1 << i - 1) % mod * coef % mod);
		tp = get_exp(tp);
		tp = tp * f;
//		for (int j = 0; j < (1 << n); j++)
//			cout << f[j] << " ";
//		cout << endl;
		for (int j = 0; j < (1 << n); j++)
			f[j] = ((j & (1 << i - 1)) ? tp[j] : f[j]);
	}
	return f;
}
int k, a[maxn * 3], b[maxn * 3], edge[maxn][maxn], pw2[maxn * maxn], pw3[maxn * maxn];
signed main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			char c = getchar();
			while(!isdigit(c))
				c = getchar();
			edge[i][j] = c - '0';
			msk[i] |= edge[i][j] << j - 1;
		}
	for (int i = 1; i <= k; i++)
		cin >> a[i] >> b[i];
	for (int i = 1; i < (1 << n); i++)
		cnt[i] = cnt[i >> 1] + (i & 1);
	inv[1] = 1;
	for (int i = 2; i <= n; i++)
		inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
	for (int i = 0; i < (1 << n); i++)
		e[i] = cal(i, i) / 2;
	Poly f, g; g.resize((1 << n)), f.resize((1 << n));
	pw2[0] = pw3[0] = 1;
	for (int i = 1; i <= n * n; i++)
		pw2[i] = pw2[i - 1] * 2 % mod;
	for (int i = 1; i <= n * n; i++)
		pw3[i] = pw3[i - 1] * 3 % mod;
	for (int i = 0; i <= n; i++)
		tf[i].resize((1 << n)), 
		tg[i].resize(1 << n),
		th[i].resize(1 << n);
	for (int i = 0; i < (1 << n); i++) {
		f[i] = pw2[e[i]]; g[i] = pw3[e[i]];
	//	cout << f[i] << endl;
		for (int s = i; s; s = (s - 1) & i)
			if(lowbit(s) == lowbit(i) && s != i)
				f[i] = add(f[i], mod - 1ll * f[s] * pw2[e[s ^ i]] % mod),
				g[i] = add(g[i], mod - 1ll * g[s] * pw3[e[s ^ i]] % mod);
	//	cout << i << " " << f[i] << " " << g[i] << endl;
	}
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 1; j <= k; j++) {
			int cnt = ((i >> a[j] - 1) & 1) + ((i >> b[j] - 1) & 1);
			if(cnt == 1)
				f[i] = 0;
		}
	}
	f = Trans(f, mod - 1); g = Trans(g, mod - 2);
	for (int i = 0; i < (1 << n); i++) {
		int cnt = 0;
		for (int j = 1; j <= k; j++)
			cnt += ((i >> a[j] - 1) & 1) + ((i >> b[j] - 1) & 1);
		if(!cnt)
			f[i] = g[i];
	}
	f = Trans(f, 2);
	cout << f[(1 << n) - 1] << endl;
	return 0;
}
/*
3 0
011
101
110
*/