测试数据来自 system/2472

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) 颗石子，重量分别为 \(w[1]..w[N]\)，请你把它们平分成两堆（即两堆石子重量和相等）。举个例子，如果 \(N=3\)，对于 \(w[1]=1,w[2]=2,w[3]=3\)，能分成两堆： \(\{3\}\) 和 \(\{1,2\}\)，这是唯一一种分法（交换两堆石子的位置被认为是同一种分堆方案）。

【输入格式】

　　第一行是整数 \(N\)。
　　第二行是：\(w[1],w[2],…,w[N]\)。

【输出格式】

　　输出划分方案总数，如果不存在则输出 0。

【输入输出样例】

　Input

7
2 1 3 6 4 7 5

　Output

4

【样例解释】

　　如果 \(N=7\)，7颗石子的重量分别是 2 1 3 6 4 7 5，下面的每一种都是满足要求的:
　　　　\(\{ 1，6，7 \}\) 和 \(\{ 2，3，4，5 \}\)
　　　　\(\{ 2，7，5 \}\) 和 \(\{ 1，3，6，4 \}\)
　　　　\(\{ 3，4，7 \}\) 和 \(\{ 2，1，6，5 \}\)
　　　　\(\{ 2，1，4，7\}\) 和 \(\{ 3，6，5 \}\)

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤40，1≤w[i]≤100\)。

【来源】

　　Mr.he