# input: a[0..N) array of distinct positive integers, N>=0, and S
# output: number of ways that S can be obtained with an unlimited
#         amount of coins with denominations in a[0..N)
#
# exponential (in N) naive solution

def cc_naive(a, S):
  return cc_aux(a, len(a), S)

def cc_aux(a, n, s):
  ans = None
  if n==0: ans = 1 if s==0 else 0
  else:
    ans = cc_aux(a, n-1, s)
    if a[n-1]<=s: ans += cc_aux(a, n, s-a[n-1])
  return ans