#include <bits/stdc++.h>
using namespace std;

class Int {
private:
	static const int MOD = 1e9 + 9;
	int x;
public:
	Int(int _x = 0) : x(_x) {
		x %= MOD;
		if (x < 0) x += MOD;
	}
	Int(const Int &p) {
		x = p.x;
	}
	Int operator+(Int p) {
		return Int(x + p.x);
	}
	Int operator-(Int p) {
		return Int(x - p.x);
	}
	Int operator*(const Int &p) const {
		return Int(x * 1LL * p.x % MOD);  
	}
	void operator+=(Int p) {
		*this = *this + p;
	}
	void operator*=(Int p) {
		*this = *this * p;
	}
	void operator-=(Int p) {
		*this = *this - p;
	}
	bool operator==(Int p) {
		return x == p.x;
	}
	friend istream &operator>>(istream &in, Int &p) {
		int x;
		in >> x;
		p = x;
		return in;
	}
	friend ostream &operator<<(ostream &out, Int p) {
		out << p.x;
		return out;
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Int> a(1 << n);
	for (int i = 0; i < (1 << n); ++i) {
		cin >> a[i];
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int x = 0; x < (1 << n); x += 2 << i) {
			for (int j = 0; j < (1 << i); ++j) {
				a[x + j] -= a[x + j + (1 << i)];
			}
		}
	}
	Int res = accumulate(a.begin(), a.end(), Int(1), [](const Int &a, const Int &b) { return a * b; });
	cout << res << '\n';
	return 0;
}