该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

Windows从神奇的森林中取得了三根神奇的棍子
并想在刀战中获胜

题目描述

Windows有三根神奇的棍子，它们的长度是由上面的数字之和决定的（长度只能为正整数）

Whitecarrot有一组数字$a_1$~$a_n$，他愿意把这些数字分为三部分$a_1$~$a_i$，$a_{i+1}$~$a_{j}$，$a_{j+1}$~$a_n$。（$1 \leqslant i < j < n$）

ferver_w想把三根木棍组成等边三角形，但是它不会分配数字，现在请你来告诉它，有多少种[i，j]的选择方法（对${10^3+7}$取模）

输入格式

输入共两行

第一行为一个正整数$n$（$3\leqslant n \leqslant2\cdot10^5$ ）

第二行为n个正整数 $a_1,a_2,\ldots,a_n$（$-10^9\leqslant a_i \leqslant 10^9$）

输出格式

输出共一行

为满足题意的方案数量（对$10^3+7$取模）

样例

5
1 2 3 0 3

2

3
1 4 1

0

提示

对于样例1 可以选择$i=2,j=3$，也可以选择$i=2,j=4$ 故方案数为2

对于样例2，无论怎么选，都不能满足题意