解题思路

先把所有相邻对 $(i,i+1)$ 看成一条边，它的权值为 $s_i=a_i+a_{i+1}$。 题目要求选择若干条边，满足：

1. 选出的边权值都相同；
2. 任意两条边不能相邻（因为每个下标最多出现一次）；
3. 选择条数 $k>0$。

题目内容

一个长度为$n$的数组$a$,下标从$1$开始，任意两个相邻的下标$(p,p+1)$可以组成一个对。

现在可以任意选择$k(k>0)$个对$(p_1,p_1+1),(p_2,p_2+1),...,(p_k,p_k+1)$，要求$a_{p1}+a_{p1+1}=a_{p2}+a_{p2+1}=...=a_{pk}+a_{pk+1}$,并且每个下标最多只能出现在其中一个对中。

问：有几种选择方案？由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

输入描述

第一行输入一个整数$n(2≤n≤10^5)$代表数组中的元素数量。

第二行输入$n$个整数$a_1,a_2,…,a_n(1≤a_i≤10^9)$代表数组元素。

输出描述

在一行上输出一个整数，表示方案数。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

样例1

输入

5
1 2 1 2 1

输出

7

说明

$(1,2)$

$(2,3)$

$(3,4)$

$(4,5)$

$(1,2),(3,4)$

$(1,2),(4,5)$

$(2,3),(4,5)$

共$7$种方案。