题面描述

如果一个非空序列可以将其元素分为两部分，各部分的元素之和相等，则称该序列是可以等分的。

现在给你一个含有 N 个元素的序列 A，问它有多少个子序列是可以等分的。

注：如果两个元素的值相同，但是在序列中的位置不同，则被认为是两个不同的元素。

输入格式

第一行包含一个整数 N

接下来 N 行，每行一个整数 A_i

输出格式

一行，一个整数表示答案

样例输入

4 
1
3
2
3

样例输出

3

样例解释

有 3 个子序列是可以等分的：

子序列 1 3 2 (其中的 3 是原序列中位置靠前的 3)

子序列 1 2 3 (其中的 3 是原序列中位置靠后的 3)

子序列 3 3

数据范围

对于全部数据，保证 $1\le N\le 20$，$1\le A_i\le 10^8$。