import sys from collections import defaultdict def main(): N, *rest = map(int, sys.stdin.read().split()) A = rest[:N] # Initialize DP: dp[m] is a dictionary where keys are (sum, max) and values are counts dp = [defaultdict(int) for _ in range(N+1)] dp[0][(0, 0)] = 1 # Base case: empty subsequence for a in A: # Iterate m in reverse to avoid using the same a multiple times in the same step for m in range(N-1, -1, -1): # Make a copy of the current state to iterate over current = list(dp[m].items()) for (s, x), cnt in current: new_m = m + 1 new_s = s + a new_x = max(x, a) if new_m > N: continue dp[new_m][(new_s, new_x)] += cnt ans = 0 for m in range(2, N+1): divisor = m - 1 if divisor == 0: continue for (s, x), cnt in dp[m].items(): if s % divisor != 0: continue k = s // divisor if x <= k: ans += cnt print(ans) if __name__ == "__main__": main()