#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
const ll mod=1e9+9;
ll a[4000009];
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	ll i,j,t,x,y,z,last,now;
	cin>>n;
	ll ans=1;
	x=(1ll<<n)-1;
	for(i=0;i<(1ll<<n);i++)cin>>a[i];
	if(n==1){
		ans=((a[0]*a[1]-a[1]*a[1])%mod+mod)%mod;
		cout<<ans;
		return 0;
	}
	y=x;
	for(i=x;i>=0;i-=4){
		for(j=0;j<4;j++){
			k=i-j;
			if(j==0){
				if(i==x)ans=(ans*a[i])%mod;
				else ans=(ans*(a[x]-a[k])%mod+mod)%mod;
			}
			else if(j<3){
				if(i==x)ans=(ans*(a[x]-a[k])%mod+mod)%mod;
				else ans=(ans*(a[x]-a[x-j]-a[y]+a[k])%mod+mod)%mod;
			}
			else {
				if(i==x)ans=(ans*(a[x]+a[k]-a[x-1]-a[x-2])%mod+mod)%mod;
				else ans=(ans*(a[x]+a[x-3]-a[x-1]-a[x-2]-a[y]-a[k]+a[y-1]+a[y-2])%mod+mod)%mod;
			}
		}
		y-=4;
	}
	cout<<ans<<"\n";
	return 0;
}