你要举行一个生日聚会，你有n个朋友，如果你邀请第i个朋友过来参加生日会，那么他会带来a[i] 颗糖果。

你的目标是：所有参加生日会的朋友带来的糖果总和能够平均分给参加生日会的所有人（包括你自己）。

有多少种不同的邀请朋友方案？

输入格式

第一行，一个整数n。1<=n<=50。

第二行，n个整数，第i个整数是a[i]。0<=a[i]<=2500。

输出格式

一个整数。数据保证答案不会超出long long。

8

1 1 1 1 1 1 1 1 

1

样例一解释：不邀请任何朋友