I believe everyone has played the game of Minesweeper. It involves an $n \times m$ matrix containing some mines, and you need to find the mines based on certain information. With Halloween approaching, a simple version of Minesweeper has become popular in the "Yu" country. The rules are the same as standard Minesweeper: if a cell does not contain a mine, the number inside it represents the count of mines in the 8 adjacent cells. Now, consider a board of size $n \times 2$, where some cells in the first column contain mines, and the second column contains no mines, as shown in the figure below:

Since there may be multiple ways to place mines in the first column that satisfy the constraints given by the numbers in the second column, your task is to determine the number of possible mine placement configurations for the first column based on the information in the second column.

Input

The first line contains $N$. The second line contains $N$ integers, which are the numbers in the cells of the second column, respectively ($1 \le N \le 10000$).

Output

A single integer, representing the number of possible mine placement configurations in the first column.

Examples

Input 1

2
1 1

Output 1

2