题目描述

给定 $N$ 个正整数 $A_1, A_2,\dots,A_N$，请问有几种方法可以将它们分成两个小组，使得每个小组的数字之和相等？

由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

输入格式

• 第一行：单个整数表示 $N$
• 第二行到第 $N+1$ 行：每行一个整数表示 $A_i$

输出格式

3
10
20
30

1

2
10
11

0

4
10
10
10
10

3

数据范围

• $30\%$ 的数据，$1\leq N\leq 20$
• $50\%$ 的数据，$1\leq N\leq 40$
• $100\%$ 的数据，$1\leq N\leq 200$
• $1\leq A_i\leq 2000$