Cho số nguyên \(K\). Đặt \(N = 2^K\).

Có một mảng nguyên \(A\) gồm \(N\) phần tử. Ta định nghĩa mảng \(B\) từ \(A\) như sau \(B_i=\sum_{j=0}^{N-1}(-1)^{popcount(i\&j)}A_j\)

Trong đó:

• \(popcount(x)\) là số lượng bit \(1\) trong biểu diễn nhị phân của \(x\).
• \(\&\) là phép AND bit.

Bạn được cho mảng \(B\). Hãy tính \(\sum_{i=0}^{N-1}|A_i|\)

Kết quả lấy modulo \(1000000007\).

Input

• Dòng đầu tiên chứa một số nguyên \(K\).

• Dòng thứ hai chứa \(N=2^K\) số nguyên \(B_0, B_1, ..., B_{N-1}\)

Output

• In ra một số nguyên duy nhất là đáp án.

Constraints

• \(1 \le K \le 20\)
• \(N = 2^K\)
• \(|B_i| \le 10^9\)

Example

2
10 2 4 0

10