Xét tập ~S~ gồm ~N~ số tự nhiên đầu tiên. Dễ dàng chứng minh tập ~S~ có ~2^N~ tập con (tính cả tập rỗng). Mỗi tập con ~S_0~ của ~S~ có thể được mã hóa bằng một dãy bit nhị phân ~B(S_0)~ gồm ~N~ bit, bit thứ ~i~ của ~B(S_0)~ bằng 1 khi và chỉ khi ~i~ thuộc ~S_0~ và bit thứ ~i~ của ~B(S_0)~ bằng 0 khi và chỉ khi ~i~ không thuộc ~S_0~. Mỗi dãy bit nhị phân có thể được biểu diễn bằng một số nguyên không âm trong hệ thập phân. Ví dụ, với ~N=5~, ta có ~S = \{0, 1, 2, 3, 4\}~. Giả sử ~S_0 = \{0, 3, 4\}~. Khi đó ~B(S_0) = 1.2^0+ 0.2^1+ 0.2^2+ 1.2^3+ 1.2^4 = 110012 = 2510~.

Định nghĩa một bộ ba tập con ~(A, B, C)~ của ~S~ bao tập con ~D~ của ~S~ khi và chỉ khi ~D~ là tập con của hợp của ba tập hợp ~A, B~ và ~C~. Nói cách khác, mỗi phần tử của ~D~ là một phần tử của tập ~A, B~ hoặc ~C~.

Xét bốn hàm ~F, G, H~ và ~R~. Mỗi hàm nhận một số nguyên không âm biểu diễn một tập con của ~S~ làm tham số duy nhất và trả về một số nguyên không âm. Bạn được cho giá trị của ~F(i),G(i)~và ~H(i)~ với mọi số nguyên ~i~ thỏa mãn ~0 \le i < 2^N~.

Giá trị của ~R(i)~ với ~i~ là một số nguyên không âm biểu diễn tập con ~X~ của ~S~ là tổng của các ~F(a) \times G(b) \times H(c)~ với ~a, b~ và ~c~ lần lượt là các số nguyên âm biểu diễn tập ~A, B~ và ~C~ của tập ~S~ thỏa mãn ~(A;B;C)~ bao ~X~.

Nhiệm vụ của bạn là tính số dư sau khi chia giá trị của ~R(0) + R(1) + ... + R(2^N - 1)~ cho ~10^9+ 7~.

Input

Dòng đầu tiên chứa một số nguyên ~N~ thỏa ~1 \le N \le 20~.

Dòng thứ hai chứa ~2^N~ sốnguyên ~F(0), F(1),\ldots, F(2^N - 1)~.

Dòng thứ ba chứa ~2^N~ sốnguyên ~G(0), G(1),\ldots, G(2^N - 1)~.

Dòng thứ tư chứa ~2^N~ sốnguyên ~H(0), H(1),\ldots, H(2^N - 1)~.

Output

In kết quả cần tính.

Samples

Sample Input 1

2
1 3 9 12
0 5 1 2
2 3 4 1

Sample Output 1

7680