Logland

두 명의 도둑(자신들의 이름을 밝히지 말라고 강하게 권고한)이 나라의 현금 준비금이 보관된 Logland의 중앙 은행에 침입했습니다. Logland의 화폐에는 $k$개의 액면가 $1, 2, 4, 8, \ldots, 2^{k - 1}$이 있고, 은행에는 현재 액면가 $2^i$인 동전이 $x_i$개씩 있습니다.

도둑들은 매우 엄격한 명예 규칙을 따르며, 훔친 전리품은 반드시 둘이 똑같이 나눠 가져야 합니다. 안타깝게도 이 때문에 일부 전리품을 두고 가야 할 수도 있습니다. 예를 들어 은행에 액면가 8인 동전 한 개와 액면가 2인 동전 두 개만 있다면, 8짜리 동전은 가져갈 방법이 없습니다. 대신 액면가 2인 동전을 한 개씩 가져가야 하며, 가능한 전리품의 절반 이상을 남기게 됩니다.

전리품을 남기는 것도, NP-난해 문제를 푸는 것도 도둑들이 좋아하는 일은 아닙니다. 그래서 남은 전리품을 똑같이 나눌 수 있도록, 도둑들이 남겨 두어야 하는 전리품 금액의 최솟값을 구해 달라고 요청했습니다.

첫 번째 줄에 Logland의 액면가 종류 수를 나타내는 정수 $k$ ($1 \le k \le 10^6$)가 주어집니다. 두 번째 줄에는 액면가 $2^0, 2^1, \ldots, 2^{k-1}$인 동전의 개수를 나타내는 정수 $x_0, x_1, \ldots, x_{k-1}$ ($0 \le x_i \le 2^{30}$) $k$개가 주어집니다.

도둑들이 남겨 두어야 하는 전리품 금액의 최솟값을 한 줄에 출력합니다. 이 값은 매우 클 수 있으므로, 소수 $10^9+7$로 나눈 나머지를 출력합니다.