P1030鹧鸪天（skycall）

【题目背景】

在许多个无人知晓的夜晚，Ehundategh 曾把未能说出的等待写进词中：

《鹧鸪天·夜行莫》

皑尘悠自天穹碎，庭树曳枝星芒坠。万籁寂去孤人步，翼鸟栖木琉璃瀑。

羽光尽，风凌渡，东篱有恨心难诉。秉灯长守待一晴，只影梧桐映月明。

如今，词中的只影已经成为很久以前的旧梦。每天暮色落下时，ESC 都会陪 Ehundategh 收好庭中的花枝，再与他并肩坐在梧桐树下，看檐前的琉璃灯一盏盏亮起。

【题目描述】

晚饭以后，二人常会用这些灯玩一个小小的猜谜游戏。ESC 将 $n$ 盏琉璃灯从左到右排开，依次编号为 $1\sim n$，再决定每盏灯处于点亮还是熄灭状态。随后，ESC 会为所有灯罩上遮光，使 Ehundategh 无法直接看见其中的星芒。

为了给他留下线索，ESC 在第 $i$ 盏灯的灯罩上写下一个整数 $a_i$，并将它称为这盏灯的邻辉数。第 $i$ 盏灯的邻辉数等于第 $i-1$、第 $i$、第 $i+1$ 盏灯中实际点亮的灯数。编号不在 $1\sim n$ 内的灯不存在，也不会被统计。

Ehundategh 想知道这些线索是否足以确定 ESC 藏在灯罩后的安排。给定所有灯的邻辉数，请你求出共有多少种点亮方案与这些数字相符。两个方案不同，当且仅当至少有一盏灯在两个方案中的状态不同。

【输入格式】

从文件 $\textbf{\textit{skycall.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行一个正整数 $n$，表示琉璃灯的数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示第 $i$ 盏灯的邻辉数。

【输出格式】

输出到文件 $\textbf{\textit{skycall.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示符合条件的点亮方案数。

【样例 1 输入】

10 32331 1 14251 16470 1 2 1

【样例 1 输出】

112230

【说明/提示】

【样例 1 解释】

对于第一组测试数据，只有中间一盏灯点亮时，三盏灯的邻辉数均为 $1$。

对于第二组测试数据，恰好点亮两盏灯中的任意一盏均符合要求，因此答案为 $2$。

【样例 2】

见选手目录下的 $\textbf{\textit{skycall/skycall2.in}}$ 和 $\textbf{\textit{skycall/skycall2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{skycall/skycall3.in}}$ 和 $\textbf{\textit{skycall/skycall3.ans}}$。

该组样例符合测试点 $5\sim 12$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{skycall/skycall4.in}}$ 和 $\textbf{\textit{skycall/skycall4.ans}}$。

该组样例符合测试点 $13\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10^5$，$1\leq n\leq 2\times 10^5$，$0\leq a_i\leq 3$，且单个测试点内所有测试数据的 $n$ 之和不超过 $2\times 10^5$。