Random Elections

내년에 Bearland에서 대통령 선거가 열린다! 모두가 이 일에 무척 들떠 있다!

현재까지 후보는 Alice, Bob, Charlie 세 명이다.

Bearland에는 n명의 시민이 있다. 선거 결과는 앞으로 여러 해 동안 Bearland의 모든 시민의 삶을 결정하게 된다. 이러한 막중한 책임 때문에, n명의 시민 각각은 Alice, Bob and Charlie 사이의 여섯 가지 선호 순서 중 하나를 다른 유권자들과 독립적으로 균등한 확률로 무작위 선택한다.

Bearland 정부는 유권자들의 선호가 주어졌을 때 선거 결과를 결정하는 데 도움이 되는 함수를 고안했다. 더 구체적으로, 이 함수는 이며, n개의 불리언 값을 받아 하나의 불리언 값을 반환한다. 또한 이 함수는 다음 성질을 만족한다: f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn).

각 후보 쌍 사이에서 세 차례의 대결이 진행된다: Alice and Bob, Bob and Charlie, Charlie and Alice. 각 대결에서 i-th번째 시민이 이 대결의 두 번째 후보보다 첫 번째 후보를 더 선호하면 xi는 1이고, 그렇지 않으면 0이다. 그 후 y = f(x1, x2, ..., xn)를 계산한다. y = 1이면 첫 번째 후보가 이 대결의 승자로 선언된다. y = 0이면 그에 따라 두 번째 후보가 승자가 된다.

두 차례의 대결에서 승리한 후보가 존재할 확률을 p라고 정의하자. p·6n은 항상 정수이다. 이 정수를 109 + 7 = 1 000 000 007로 나눈 나머지를 출력한다.

첫 번째 줄에 하나의 정수 n (1 ≤ n ≤ 20)가 주어진다.

다음 줄에는 함수 f를 나타내는, 영과 일로 이루어진 길이 2n의 문자열이 주어진다. bk(x)를 x의 이진 표현에서 k-th번째 비트라고 하자. 이 문자열의 i-th번째(0-based) 문자는 f(b1(i), b2(i), ..., bn(i))의 반환값을 나타낸다.

x1, x2, ldots, xn의 값이 어떠하든 f(1 - x1, 1 - x2, ..., 1 - xn) = 1 - f(x1, x2, ..., xn)임이 보장된다.

문제의 답인 정수 하나를 출력한다.

첫 번째 예제에서 결과는 항상 첫 번째 유권자에 의해 완전히 결정된다. 다시 말해, f(x1, x2, x3) = x1이다. 따라서 무슨 일이 일어나더라도 두 차례의 대결에서 승리한 후보가 존재한다. 더 구체적으로는 유권자 1의 선호 목록 맨 위에 있는 후보이다. 그러므로 p = 1이며, 1·63 = 216을 출력한다.