题目描述

给定长度为$n$的序列$a_1,...,a_n$， dash 想知道有多少个子序列是等差数列。答案对$10^9+7$取模

子序列：由原序列选出若干个位置（至少选出一个位置）构成的序列。

我们认为仅包含一个数的子序列也是等差数列。

两个子序列不同，当且仅当至少有一个下标在一个子序列中被选出，在另一个子序列中未被选出。

输入格式

第一行一个正整数$n$表示序列的长度。

接下来一行$n$个正整数$a_1,...,a_n$

输出格式

输出一行一个正整数表示等差子序列的个数，答案对$10^9+7$取模。

样例

3
1 2 1

6

解释 #1

长度为$1$的等差子序列有$\{1\},\{2\},\{1\}$。

长度为$2$的等差子序列有$\{1,2\},\{2,1\},\{1,1\}$

没有长度为$3$的等差子序列

3
2 3 1

6

数据范围

对于$100\%$的数据，$1\le n\le 5\times 10^5,1\le a_i\le 100$