题目描述

你要举行一个生日聚会，你有 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

4
0 0 0 0

16

7
1 2 3 4 5 6 7

31