题目描述
又到了圣诞节，老师准备了n个不同礼物，准备送给小美与小帅，这n个礼物的价值依次是a1、a2、...、an，为了公平起见，老师决定将这些礼物分成2份，每份的礼物价值之和相等，举个例子，如果 n=3，三个礼物的价值分别为{1,2,3}，那么给小美礼物{1,2}，给小帅礼物{3}是一种分法，交换顺序{3}和{1,2}是另一种方案，因此总共有2种方案，如果两个礼物的价值相同，例如有2个礼物a1 = 1， a2 = 1，则有2种方案，分别是给小美a1，小帅a2，或者给小美a2，小帅a1。
老师想知道总共有多少种平分礼物的方案？
输入
第一行，一个正整数n(n <= 20)。
第二行，n个整数，空格隔开，均不超过10。
输出
一个整数，表示所有的方案数。
如果无法平分礼物，则输出0。
样例输入
7
1 2 3 4 5 6 7样例输出
8