题目内容

在一维道路上依次排列着 $n$ 个信号塔，编号依次为 $1$ 到 $n$。对于相邻的两个信号塔 $i$ 和 $i+1$，它们之间存在一条通信链路。定义这条链路的品质因子为两座信号塔的强度之和，即 $c_i = b_i + b_{i+1}$，其中 $b_i$ 表示第 $i$ 座塔的强度。

管理员计划选择若干条链路进行升级维护，必须同时满足以下条件：

1. 所有被选链路的品质因子必须完全相同；
2. 任意两座信号塔不能被重复使用，即每条链路覆盖两座信号塔，这些信号塔之间不能重叠（每个塔号最多出现在一条被选链路中）；
3. 至少选择一条链路。

请你计算共有多少种不同的选择方案。由于答案可能很大，请输出对 $10^9+7$ 取模后的结果。

本题中，$n$ 满足 $2 \le n \le 10^5$，每个信号塔的强度 $b_i$ 满足 $1 \le b_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示信号塔的数量。第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，依次表示每个信号塔的强度。

输出描述

输出一行一个整数，表示方案数对 $10^9+7$ 取模后的结果。

样例1

输入

2
5 3

输出

1

说明

只有 2 座信号塔，存在唯一一条相邻链路，其品质因子为 $c_1 = b_1 + b_2 = 5 + 3 = 8$。由于只有一条链路且至少选择一条，只能选择这一条链路，方案数为 1。这是一个最小的边界情况。

样例2

输入

3
1 1 1

输出

2

说明

三条链路的品质因子均为 2，对应的位置分别是 $i=1$ 和 $i=2$。这两个位置相邻（$i=2 = i=1+1$），因此它们构成一个长度为 2 的连续块。 根据斐波那契递推，不选任何链路的方案数为 $f_2 = 3$，要求至少选一条链路，故需要减去空方案，得到该品质因子下的方案数 $f_2 - 1 = 2$。这两种方案分别是：只选择链路 $(1,2)$ 或只选择链路 $(2,3)$。总答案即为 2。

样例3

输入

4
1 3 2 1

输出

3

说明

三条链路的品质因子分别为 $c_1 = 4$、$c_2 = 5$ 和 $c_3 = 3$，互不相同。每个品质因子都只出现一次，对应的连续块长度均为 1。 长度为 1 的连续块贡献为 $f_1 - 1 = 2 - 1 = 1$，即只能选择该条链路。三个不同的品质因子各自产生 1 种方案，因此总方案数为 3。

样例4

输入

6
1 2 1 2 1 2

输出

12

说明

所有相邻链路的品质因子都是 3，位置编号 $1$ 到 $5$ 全部连续，构成一个长度为 5 的连续块。 斐波那契数列为 $f_0 = 1$，$f_1 = 2$，$f_2 = 3$，$f_3 = 5$，$f_4 = 8$，$f_5 = 13$。该品质因子下所有合法选择方案（允许空选）共 $f_5 = 13$ 种，去掉一个都不选的空方案，得到 $13 - 1 = 12$ 种方案。总答案即为 12。