Covering Sets

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Let's consider a set S of N different elements numbered from 0 to N  1. It's a wellknown fact that there are exactly 2^{N} subsets of S (including the empty subset). Each subset S' of S can be encoded as a bitmask B(S') containing N bits, where the i'th bit of B(S') is equal to 1 if the i'th element of S belongs to S', and 0 otherwise. Each bitmask can also be considered as a nonnegative integer represented in binary.
For example, suppose N is equal to 5. Then S = {0, 1, 2, 3, 4}. Let's assume S' = {0, 3, 4}. Then B(S') = 1 × 2^{0} + 0 × 2^{1} + 0 × 2^{2} + 1 × 2^{3} + 1 × 2^{4} = 11001_{2} = 25_{10}.
Let's say that a triple (A, B, C) of subsets of S covers a subset D of S, if D is a subset of the union of subsets A, B and C. In other words, every element of D is an element of at least one of A, B, or C.
Let's consider four functions F, G, H and R. Each takes a subset of S as the only parameter and returns a nonnegative integer. You are given the values of F(i), G(i), and H(i) for each 0 ≤ i < 2^{N}.
The value of the function R of a subset X of S is equal to the sum of F(A) × G(B) × H(C) for all triples (A, B, C) of subsets of S that cover X.
Your task is to calculate R(0) + R(1) + ... + R(2^{N}  1) modulo 1000000007(10^{9} + 7).
Input
The first line of the input contains one integer N.
The second line of the input contains 2^{N} integers, denoting the values of F(0), F(1), ..., F(2^{N}  1). The third and the fourth lines of the input contains the values of G and H in the same format.
Output
The output should contain one integer: R(0) + R(1) + ... + R(2^{N}  1) modulo 1000000007(10^{9} + 7).
Constraints
1 ≤ N ≤ 20;
0 ≤ F_{i}, G_{i}, H_{i} < 1,000,000,007(10^{9} + 7).
Example
Input: 2 1 3 9 12 0 5 1 2 2 3 4 1 Output: 7680
Explanations
Here's the table of what sets are covered by all the possible triples for N = 1:
A  B  C  D 
0  0  0  {0} 
0  0  1  {0, 1} 
0  1  0  {0, 1} 
0  1  1  {0, 1} 
1  0  0  {0, 1} 
1  0  1  {0, 1} 
1  1  0  {0, 1} 
1  1  1  {0, 1} 
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/COVERING 
Tags  cook52, divideandconq, inclusnexclusn, kostya_by, mediumhard, sets 
Date Added:  24102014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 