Almost everyone who comes up with a great business idea thinks primarily about potential huge profits. However, that is not the most important thing. Bitomir realizes that the key to success is minimizing and estimating costs. He plans to trade in shoelaces, for which demand has suddenly increased in Cajtocja. The shoelaces are produced in Aajtocja, so they must be transported through the intermediate land of Bajtocja.

Bajtocja consists of $n$ regions, numbered from 1 to $n$, each with two cities. For every $i$ ($1 \le i \le n - 1$), from each city in region $i$ to each city in region $i + 1$, there exists a directed road with a toll, the value of which is an integer in the interval $[1, a_i]$, where $a_i$ is the upper limit set by the regional administration of region $i$. Bitomir has not been to Bajtocja for a long time and does not know the exact toll values for individual roads, but he knows the values of $a_i$.

Bitomir will have to enter one of the cities in the first region of Bajtocja, reach the $n$-th region, and leave Bajtocja there to sell his goods in Cajtocja. While traveling through Bajtocja, Bitomir will naturally choose the sequence of roads with the smallest sum of toll values, which is the transport cost.

Lying in bed in the evening, Bitomir considered each of the $a_1^4 \cdot a_2^4 \cdot \dots \cdot a_{n-1}^4$ possible scenarios of what the toll for each road might be. To calculate the average expected transport cost, Bitomir began to calculate the sum of transport costs across all scenarios. Unfortunately, fatigue won, and Bitomir fell asleep. Can you calculate this sum for him? Output the result modulo $2^{32}$.

Input

The first line of input contains an integer $n$ ($2 \le n \le 8$) — the number of regions in Bajtocja.

The second line contains $n - 1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 3000$) — the maximum possible toll for each region.

Output

Output a single integer — the sum of transport costs across all scenarios, modulo $2^{32}$.

Examples

Input 1

2
2

Output 1

17

Note 1

In the first test, Bajtocja has $n = 2$ regions. Bitomir wants to get from the first to the second region and has four directed roads at his disposal, each with a toll of 1 or 2 (since $a_1 = 2$). If all roads have a toll of 2, Bitomir will choose any road and the transport cost will be 2. In the remaining 15 scenarios, there exists a road with a toll of 1, and that will be the transport cost. The result is $1 \cdot 2 + 15 \cdot 1 = 17$.

Input 2

4
3 4 1

Output 2

78784

Note 2

In the second test, we have $n = 4$ regions. The figure below shows the layout of Bajtocja. Circles with the number $i$ represent cities in the $i$-th region. Aajtocja (from which we enter the first region) and Cajtocja are also marked, but only the roads between the regions of Bajtocja have tolls. An example distribution of tolls on the roads is also shown, for which the optimal route is bolded, giving a transport cost of $1 + 2 + 1 = 4$.

Layout of Bajtocja for the second example