Problem B: PIPI玩扫雷

Problem B: PIPI玩扫雷

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 217  Solved: 95
[Submit] [Status] [Web Board] [Creator:]

Description

现在PIPI在玩一个简单版的扫雷游戏,地图为一个N行2列的矩阵,左边列的格子都未打开,且格子只有两种情况:有地雷,无地雷(即空格子)。右边列的格子已经全部打开,且都为数字(只包含0,1,2,3),数字表示和它8连通的格子里面雷的数目,如下图例子所示。

请你帮PIPI计算出左边列的雷可能有多种方案满足第二列的数的限制。

Input

第一行为一个整数N,N<=100000.
接下来N个数字,表示右边列格子中的数字。

Output

输出左边列合法的方案数。

Sample Input

2
1  1

Sample Output

2