#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=1e9+9;
const LL INF=1e9;
void rd(LL &x)
{
    x=0; LL fl=1; char c=getchar();
    while (!isdigit(c)) { if (c=='-') fl=-1;c=getchar(); }
    while (isdigit(c)) { x=(x<<1)+(x<<3)+(c^48);c=getchar(); }
    x*=fl;
    return;
}
int Cnt(int x)
{
    int ret=0;
    for (;x;x>>=1) ret+=x&1;
    return ret;
}
int n;
LL a[2000005];
signed main()
{
    scanf("%d",&n);
    for (int i=0;i<(1<<n);i++) rd(a[i]);
    for (int i=0;i<(1<<n);i++)
        for (int j=i+1;j<(1<<n);j++)
            if ((i|j)==j)
                if ((Cnt(i)-Cnt(j))&1) a[i]=(a[i]-a[j]+MOD)%MOD;
                    else a[i]=(a[i]+a[j])%MOD;
    LL ans=1;
    for (int i=0;i<(1<<n);i++)
        ans=ans*a[i]%MOD;
    printf("%lld\n",ans);
    return 0;
}