<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

239. Minesweeper
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Not so long ago, an International Cell Playing Company (ICPC) decided to organize an Amusing Championship of Minesweeper (ACM). "Minesweeper" is a standard Windows game (you can find it now at Start->Programs->Games->Minesweeper or somewhere like this). The rules of "Minesweeper" are the following: you are to open all the cells of a game field, that don't contain mines, and to mark by flags all the cells, that contain mines. During the game, numbers which are written in the cells help you to solve this task. These numbers appear in the opened cells (it is denied to open a cell with a mine, in this case you will be exploded). A number written in a cell indicates how many mines are situated in 8 neighboring cells (fig.1).



fig. 1


Just for aesthetic reasons "0" is indicated in background color, so you don't see it. In the case of absence of any mines in the cells neighboring with some opened cell, all neighboring cells will be opened automatically (you can see it on the first figure, where only 1 cell was opened by player, and other cells were opened automatically).
Now we can immediately say where the mines are certainly situated (fig. 2).



fig. 2


Very often a following situation takes place. No cell of the first column is opened, while all the cells of second column are opened, and it is guaranteed that second and third columns don't contain mines at all (fig. 3).



fig. 3


In that case the numbers shown in the cells of the second column indicate exactly the number of mines situated in the neighboring cells of the first column. Such situations are very hard for players to solve, and that's why your friend who wants to train for ACM, asked you to write a program that gives him a possibility to check his solutions.
Imagine now, that we are playing Minesweeper on the field, containing N rows and 2 columns. It is guaranteed, that the second column is free of mines and completely opened. The first column is not opened yet, and may contain mines. You are to determine the location of all mines in the first column, when you know all the data of the second column. It is possible to do so if, for example, one of the cells of the second column contains number 3 (fig. 4).



fig. 4


So you can be sure, that all 3 neighboring cells of the first column contain mines. Therefore it is not difficult to find out, which cells are free of mines (fig. 5).



fig. 5


Now, using this information, we can say all about the first column (the remaining cells definitely contain mines). Sometimes it can be impossible to determine surely, where the mines are situated, and where not (fig. 6).



fig. 6


Sometimes the field may be mistaken at all, and there exists no mine distribution that produces such numbers in the second column (fig. 3, pay attention to the upper part of the column). It is not very amazing when you remember who has written this game.
Now you must write a program which, given the data of the second column, outputs how many distributions of the mines in the first column exist, that produce such data in the second column.

Input
The first line of input contains integer N - height of the field (1<=N<=1000). Then N lines follow, each containing an integer ai (0<=ai<=3) - the number, written on the I-th cell of the second column.

Output
You must output the only number - an answer to the problem.

Sample test(s)

Input
Test #1
9
1 1 3 2 1 1 1 2 1

Test #2
2
1 1

Test #3
7
1 2 3 2 2 2 2

Output
Test #1
0

Test #2
2

Test #3
1
Author:	Antony Popovich
Resource:	Leningrad Regional School Programming Olympiad
Date:	January 9, 2004

<|response|>
## 1) Abridged problem statement (concise)

We have a Minesweeper grid of size **N × 2**.

- **Column 2** contains **no mines** and is fully opened.
- **Column 1** is unknown and may contain mines.
- For each row `i` in column 2, we are given a number `a[i]` (0..3) equal to the count of mines in the **neighboring cells** of that column-2 cell.

Since mines can only be in column 1, the neighbors of `(i, col2)` are exactly the cells `(i-1, col1)`, `(i, col1)`, `(i+1, col1)` that exist.

**Task:** Count how many mine configurations in column 1 (each cell is mine/non-mine) produce exactly the given numbers `a[0..N-1]`.

`1 ≤ N ≤ 1000`.

---

## 2) Key observations

1. Let `m[i] ∈ {0,1}` indicate whether row `i` in **column 1** contains a mine.
2. Constraints become a simple linear system over integers:
   - Top: `a[0] = m[0] + m[1]` (if `N > 1`)
   - Middle: `a[i] = m[i-1] + m[i] + m[i+1]` for `1 ≤ i ≤ N-2`
   - Bottom: `a[N-1] = m[N-2] + m[N-1]` (if `N > 1`)
   - Special case `N=1`: `a[0] = m[0]`
3. If `N ≥ 2` and we choose `m[0]`, then:
   - `m[1]` is forced by `m[1] = a[0] - m[0]`
   - and for each `i` (middle rows):  
     `m[i+1] = a[i] - m[i] - m[i-1]`
4. Therefore **the entire configuration is uniquely determined by `m[0]`** (if it remains valid), so the answer is at most **2** (try `m[0]=0` and `m[0]=1`).

---

## 3) Full solution approach

We will test two possible starts:

### Function `check(first)`
Checks whether a valid configuration exists with `m[0] = first` (0 or 1).

- If `N == 1`: valid iff `a[0] == first`.
- Otherwise:
  1. Compute `m[1] = a[0] - m[0]`. If `m[1]` is not `0/1`, fail.
  2. For each `i = 1 .. N-2`, compute:
     - `m[i+1] = a[i] - m[i] - m[i-1]`
     - If not `0/1`, fail.
  3. Check last constraint: `a[N-1] == m[N-2] + m[N-1]`.

If all checks pass, this `first` produces exactly **one** valid configuration.

### Final answer
`ans = check(0) + check(1)`.

### Complexity
- Time: `O(N)` (two passes of length `N`)
- Memory: `O(1)` or `O(N)`; we can do `O(1)` by keeping only the last two `m` values.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

void solve() {
    // This problem is about minesweeper, but we are given a N x 2 grid.
    // Column 1 is hidden and may contain mines. Column 2 is fully visible and
    // mine-free, and each cell shows how many mines are among its neighbors in
    // column 1. Since column 2 has no mines, cell i in column 2 only looks at
    // cells i-1, i, i+1 in column 1 (where they exist):
    //   a[0] = m[0] + m[1]  (top row, 2 neighbors)
    //   a[i] = m[i-1] + m[i] + m[i+1]  (middle rows, 3 neighbors)
    //   a[n-1] = m[n-2] + m[n-1]  (bottom row, 2 neighbors)
    // We need to count how many binary assignments of mines to column 1
    // produce the given numbers. The key insight is that once we fix m[0],
    // every other value is forced by the equations, so the answer is at most
    // 2. We just try both and count the valid ones.

    auto check = [&](int first) -> bool {
        vector<int> m(n);
        m[0] = first;
        if(n == 1) {
            return a[0] == m[0];
        }
        m[1] = a[0] - m[0];
        if(m[1] < 0 || m[1] > 1) {
            return false;
        }
        for(int i = 1; i < n - 1; i++) {
            m[i + 1] = a[i] - m[i] - m[i - 1];
            if(m[i + 1] < 0 || m[i + 1] > 1) {
                return false;
            }
        }
        return a[n - 1] == m[n - 1] + m[n - 2];
    };

    int ans = 0;
    if(check(0)) {
        ans++;
    }
    if(check(1)) {
        ans++;
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def count_configurations(a):
    """
    a[i] is the number shown in row i of column 2 (which has no mines).
    Mines can only be in column 1. Let m[i] in {0,1} be whether row i in column 1 is a mine.

    Constraints:
      N==1: a[0] = m[0]
      else:
        a[0]   = m[0] + m[1]
        a[i]   = m[i-1] + m[i] + m[i+1]   for i=1..N-2
        a[N-1] = m[N-2] + m[N-1]

    If N>=2, fixing m[0] forces everything else, so try m[0]=0 and m[0]=1.
    """
    n = len(a)

    def is01(x):
        return x == 0 or x == 1

    def check(first):
        # N=1: only neighbor in column 1 is itself.
        if n == 1:
            return a[0] == first

        m0 = first
        m1 = a[0] - m0
        if not is01(m1):
            return False

        m_prev, m_cur = m0, m1

        # Build sequentially using:
        # m[i+1] = a[i] - m[i] - m[i-1]
        for i in range(1, n - 1):
            m_next = a[i] - m_cur - m_prev
            if not is01(m_next):
                return False
            m_prev, m_cur = m_cur, m_next

        # Verify last constraint
        return a[n - 1] == m_prev + m_cur

    return int(check(0)) + int(check(1))


def main():
    data = list(map(int, sys.stdin.read().split()))
    n = data[0]
    a = data[1:1+n]
    print(count_configurations(a))

if __name__ == "__main__":
    main()
```

These solutions follow directly from the recurrence induced by the Minesweeper neighbor counts; they are fast enough for `N=1000` and easily fit the tight limits.