测试数据来自 system/1542

背景

为了for beginngers，特设此题，^_^

描述

某人发明了一种跳棋游戏，在一条无限长的直线棋盘上，排列着若干棋子，每个单位上有两种状态：空、或有棋子。一个棋子可以跳过旁边位置的一颗棋子到另一边的空位上并吃掉被跳过的的这颗棋子（例如\(00\_\)可以变成\(\_\_0\)）。
需要使最后变成\(00\)：只有两个棋子且两邻，和\(0\_0\)：只有两个棋子且中间恰有一个空格，这两种目标状态。
问给出n个棋子最多有多少种排法可以让最后得到状态\(00\)或\(0\_0\)。每种排法头尾都视有无数个空，因此\(\_0\_0\_\)与\(0\_0\)视为同一种排法。

格式

输入格式

第一行给出整数1或0，表示目标状态为\(0\_0\)或\(00\);
之后若干行，每行一个数表示n。

输出格式

若干行，对应输入的若干行，依次给出有多少排法；

样例1

样例输入1

0
3

样例输出1

2

限制

各个测试点1s

提示

数据规模：2<n<1000000。

样例解释：以\(0\)表示棋子，以\(\_\)表示空格，只有\(00\_0\)和\(0\_00\)两组合法的排法，才可以通过若干次操作变成\(00\)的样子。

来源

省选第三题