Submission #9609186

---

Source Code Expand

#include <bits/stdc++.h>

const int mod = 1'000'000'007;
typedef long long LL;
void reduce(int & x) { x += x >> 31 & mod; }
int mul(int a, int b) { return (LL) a * b % mod; }
int pow(int a, int b, int res = 1) {
	for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a);
	return res;
}
int dp[1 << 16];
int A[17], n, m;
const int MAXS = 1 << 16 | 10;
int fac[MAXS], inv[MAXS];
int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(0);
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for (int i = 2; i != MAXS; ++i) {
		fac[i] = mul(fac[i - 1], i);
		inv[i] = mul(inv[mod % i], mod - mod / i);
	}
	for (int i = 2; i != MAXS; ++i) inv[i] = mul(inv[i], inv[i - 1]);
	std::cin >> n >> m;
	for (int i = 1; i <= m; ++i) std::cin >> A[i];
	std::sort(A + 1, A + 1 + m, std::greater<int> ());
	const int U = 1 << n;
	dp[0] = 1;
	for (int i = 1; i <= m; ++i) {
		for (int j = U - 1; ~j; --j) if (int t = dp[j]) {
			int rest = U - A[i] + 1 - j;
			for (int k = 0; k < n; ++k) if ((~j >> k & 1) && rest >= (1 << k))
				reduce(dp[j | 1 << k] += (LL) t * fac[rest - 1] % mod * inv[rest - (1 << k)] % mod * (1 << k) % mod - mod);
		}
	}
	int ans = 0;
	for (int i = 0; i != U; ++i)
		reduce(ans += (LL) fac[U - i - 1] * dp[i] % mod * (__builtin_parity(i) ? mod - 1 : 1) % mod - mod);
	ans = mul(ans, U);
	std::cout << ans << std::endl;
	// Sorry column limit
	return 0;
}

Submission Info

Judge Result