Description

Most people have played the game Minesweeper. In an $n \times m$ grid, some cells contain mines. If a cell does not contain a mine, the number in it indicates the number of mines among its $8$-connected neighboring cells. Now the board is $n \times 2$: some cells in the first column contain mines, and the second column contains no mines, as shown in the figure:

Since there may be multiple mine configurations in the first column that satisfy the numbers in the second column, your task is to determine, based on the second column, how many valid configurations there are.

Input Format

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

Output Format

Output a single integer: the number of valid configurations of mines in the first column.

2
1  1

2

Hint

Translated by ChatGPT 5