#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;	
	
	vector<LL> A((1 << n) * 2 + 1, 0), F((1 << n) * 2 + 1, 0);
	cin >> n;
	int mo = 1e9 + 9;
	for(int i = 0; i < (1 << n); ++i)
		cin >> F[i];
	
	for(int i = n - 1; i >= 0; --i){
		for(int mask = 0; mask < (1 << n); ++mask){
//			cerr << i << " " << mask << endl;
			if(!((mask >> i) & 1)){
//				cerr << (mask | (1 << i)) << " " << mask << " " << F[mask | (1 << i)] << " " << F[mask] << endl;
				F[mask] = (1LL * F[mask] - F[mask | (1 << i)] + mo) % mo;
//				cerr << F[mask] << endl;
				
			}
//			cerr << i << " " << mask << " " << F[mask] << endl;
		}
	}
	
	LL ans = 1;
	for(int i = 0; i < (1 << n); ++i)
		ans = F[i] * ans % mo;
	cout << ans;
	return 0;
}