{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK52/mandarin/COVERING.pdf\"\u003eMandarin Chinese\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK52/russian/COVERING.pdf\"\u003eRussian\u003c/a\u003e as well.\u003c/h3\u003e\n\u003cp\u003e\n\tLet\u0027s consider a set \u003cb\u003eS\u003c/b\u003e of \u003cb\u003eN\u003c/b\u003e different elements numbered from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003eN - 1\u003c/b\u003e. It\u0027s a well-known fact that there are exactly 2\u003csup\u003e\u003cb\u003eN\u003c/b\u003e\u003c/sup\u003e subsets of \u003cb\u003eS\u003c/b\u003e (including the empty subset). Each subset \u003cb\u003eS\u0027\u003c/b\u003e of \u003cb\u003eS\u003c/b\u003e can be encoded as a bitmask \u003cb\u003eB(S\u0027)\u003c/b\u003e containing \u003cb\u003eN\u003c/b\u003e bits, where the \u003cb\u003ei\u003c/b\u003e\u0027th bit of \u003cb\u003eB(S\u0027)\u003c/b\u003e is equal to 1 if the \u003cb\u003ei\u003c/b\u003e\u0027th element of \u003cb\u003eS\u003c/b\u003e belongs to \u003cb\u003eS\u0027\u003c/b\u003e, and 0 otherwise. Each bitmask can also be considered as a non-negative integer represented in binary.\n\u003c/p\u003e\n\u003cp\u003e\n\tFor example, suppose \u003cb\u003eN\u003c/b\u003e is equal to 5. Then \u003cb\u003eS\u003c/b\u003e \u003d {0, 1, 2, 3, 4}. Let\u0027s assume \u003cb\u003eS\u0027\u003c/b\u003e \u003d {0, 3, 4}. Then \u003cb\u003eB(S\u0027)\u003c/b\u003e \u003d 1 × 2\u003csup\u003e0\u003c/sup\u003e + 0 × 2\u003csup\u003e1\u003c/sup\u003e + 0 × 2\u003csup\u003e2\u003c/sup\u003e + 1 × 2\u003csup\u003e3\u003c/sup\u003e + 1 × 2\u003csup\u003e4\u003c/sup\u003e \u003d 11001\u003csub\u003e2\u003c/sub\u003e \u003d 25\u003csub\u003e10\u003c/sub\u003e.\n\u003c/p\u003e\n\u003cp\u003e\n\tLet\u0027s say that a triple (\u003cb\u003eA\u003c/b\u003e, \u003cb\u003eB\u003c/b\u003e, \u003cb\u003eC\u003c/b\u003e) of subsets of \u003cb\u003eS\u003c/b\u003e \u003ci\u003ecovers\u003c/i\u003e a subset \u003cb\u003eD\u003c/b\u003e of \u003cb\u003eS\u003c/b\u003e, if \u003cb\u003eD\u003c/b\u003e is a subset of the union of subsets \u003cb\u003eA\u003c/b\u003e, \u003cb\u003eB\u003c/b\u003e and \u003cb\u003eC\u003c/b\u003e. In other words, every element of \u003cb\u003eD\u003c/b\u003e is an element of at least one of \u003cb\u003eA\u003c/b\u003e, \u003cb\u003eB\u003c/b\u003e, or \u003cb\u003eC\u003c/b\u003e.\n\u003c/p\u003e\n\u003cp\u003e\n\tLet\u0027s consider four functions \u003cb\u003eF\u003c/b\u003e, \u003cb\u003eG\u003c/b\u003e, \u003cb\u003eH\u003c/b\u003e and \u003cb\u003eR\u003c/b\u003e. Each takes a subset of \u003cb\u003eS\u003c/b\u003e as the only parameter and returns a non-negative integer. You are given the values of \u003cb\u003eF(i)\u003c/b\u003e, \u003cb\u003eG(i)\u003c/b\u003e, and \u003cb\u003eH(i)\u003c/b\u003e for each 0 ≤ \u003cb\u003ei\u003c/b\u003e \u003c 2\u003csup\u003e\u003cb\u003eN\u003c/b\u003e\u003c/sup\u003e.\n\u003c/p\u003e\n\u003cp\u003e\n\tThe value of the function \u003cb\u003eR\u003c/b\u003e of a subset \u003cb\u003eX\u003c/b\u003e of \u003cb\u003eS\u003c/b\u003e is equal to the sum of \u003cb\u003eF(A)\u003c/b\u003e × \u003cb\u003eG(B)\u003c/b\u003e × \u003cb\u003eH(C)\u003c/b\u003e for all triples (\u003cb\u003eA\u003c/b\u003e, \u003cb\u003eB\u003c/b\u003e, \u003cb\u003eC\u003c/b\u003e) of subsets of \u003cb\u003eS\u003c/b\u003e that cover \u003cb\u003eX\u003c/b\u003e.\n\u003c/p\u003e\n\u003cp\u003e\n\tYour task is to calculate \u003cb\u003eR(0)\u003c/b\u003e + \u003cb\u003eR(1)\u003c/b\u003e + ... + \u003cb\u003eR(2\u003csup\u003eN\u003c/sup\u003e - 1)\u003c/b\u003e modulo 1000000007(10\u003csup\u003e9\u003c/sup\u003e + 7).\n\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\n\tThe first line of the input contains one integer \u003cb\u003eN\u003c/b\u003e.\n\u003c/p\u003e\n\u003cp\u003e\n\tThe second line of the input contains 2\u003csup\u003e\u003cb\u003eN\u003c/b\u003e\u003c/sup\u003e integers, denoting the values of \u003cb\u003eF(0)\u003c/b\u003e, \u003cb\u003eF(1)\u003c/b\u003e, ..., \u003cb\u003eF(2\u003csup\u003eN\u003c/sup\u003e - 1)\u003c/b\u003e. The third and the fourth lines of the input contains the values of \u003cb\u003eG\u003c/b\u003e and \u003cb\u003eH\u003c/b\u003e in the same format.\n\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\n\tThe output should contain one integer: \u003cb\u003eR(0)\u003c/b\u003e + \u003cb\u003eR(1)\u003c/b\u003e + ... + \u003cb\u003eR(2\u003csup\u003eN\u003c/sup\u003e - 1)\u003c/b\u003e modulo 1000000007(10\u003csup\u003e9\u003c/sup\u003e + 7).\n\u003c/p\u003e\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cp\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 20;\u003c/p\u003e\n\u003cp\u003e0 ≤ \u003cb\u003eF\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eG\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eH\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c 1,000,000,007(10\u003csup\u003e9\u003c/sup\u003e + 7).\u003c/p\u003e\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n2\n1 3 9 12\n0 5 1 2\n2 3 4 1\n\n\u003cb\u003eOutput:\u003c/b\u003e\n7680\n\n\u003c/pre\u003e\u003ch3\u003eExplanations\u003c/h3\u003e\n\u003cp\u003e\nHere\u0027s the table of what sets are covered by all the possible triples for \u003cb\u003eN\u003c/b\u003e \u003d 1:\u003c/p\u003e\n\u003ctable\u003e\n\u003ctr\u003e\n\u003ctd\u003eA\u003c/td\u003e\n\u003ctd\u003eB\u003c/td\u003e\n\u003ctd\u003eC\u003c/td\u003e\n\u003ctd\u003eD\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e{0}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e0\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e1\u003c/td\u003e\n\u003ctd\u003e{0, 1}\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/table\u003e\n\n"}}]}