#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define otto auto
const int MAXN=1e6+10;
const int INF=1ll*1e7*1e9;
const int MOD = 1e9 + 9;

int T,N,M,K,P,Q;
int a[MAXN];

void solve(int l,int r){
	if(l == r) return;
	int mid = (l + r) >> 1;
	int len = mid - l + 1;
	for(int i = l;i <= mid; i++){
		a[i] -= a[i+len];
	}
	solve(l,mid);
	solve(mid+1,r);
}

void prepare(){
	scanf("%lld",&N);
	for(int i = 1;i <= (1<<N);i++){
		scanf("%lld",&a[i]);
	}
	solve(1,1<<N);
	int ans = 1;
	for(int i = 1;i <= (1<<N); i++){
		ans = ans * ((a[i] + MOD) % MOD) % MOD;
	}
	printf("%lld\n",ans);
}

signed main(){
	//ios::sync_with_stdio(0);
	T=1;
	//scanf("%lld",&T);
	while(T--){
	    prepare();
	}
	return 0;
}