17933번 - Logland 다국어

문제

Two thieves (who strongly "recommended" us not to reveal their names) has broken into the central bank of Logland, where the country's cash reserve is stored. In Logland, the currency has the $k$ denominations 1,ドル 2, 4, 8, \ldots, 2^{k - 1},ドル and the bank currently stores $x_i$ coins of denominations 2ドル^i$.

Thieves live by a very strict honor code, which stipulates that any loot grabbed must be divided evenly between the theives. Unfortunately (for the thieves), this may mean that some loot must be left behind. For example, if the bank contained a single coin of denomination 8ドル,ドル and two coins of denomination 2ドル,ドル there is no way they could bring the 8ドル$ coin. Instead, they would have to take one coin of value 2ドル$ each, leaving more than half of the possible loot!

Since neither leaving loot nor solving NP-hard problems are things thieves like to do, they have asked you to compute the minimum value of the loot they must leave behind, in order to be able to split the remaining loot evenly.

입력

The first line of input contains the integer 1ドル \le k \le 10^6$ -- the number of denominations in Logland. The next line contains the $k$ integers 0ドル \le x_0, x_1, \dots, x_{k-1} \le 2^{30},ドル the number of coins of the denominations 2ドル^0, 2^1, \dots, 2^{k - 1}$.

출력

Output a single line, the minimum amount of money the thieves must leave behind. Since this number may be very large, output it modulo the prime number 10ドル^9 + 7$.

제한

힌트