给定一个长度为 的整数数组 。需要进行恰好 次操作，数组最终只剩下一个数字。 每次操作只能针对当前数组的最后两个数 （ 在前， 在后）执行下述二选一： 将 删除，并将 插入到数组末尾； 将 删除，并将 插入到数组末尾。 请统计，在所有可能的操作序列下，最终结果为 的方案数各有多少。答案对 取模。

输入描述:

第一行输入整数 ——数组长度。第二行输入 个整数 ——初始数组。

输出描述:

输出一行 个整数，第 个数表示最终结果为 的方案数（按 ）。