# 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)
#
# O(NS) time and space solution using DP with tabulation (bottom-up)

def cc_tab(a, S):
  N = len(a)
  tab = [ [ None for s in range(S+1) ] for n in range(N+1) ]
  for s in range(S+1): tab[0][s] = 1 if s==0 else 0
  n,s = 1,0
  while n!=N+1:
    if s==S+1: n,s = n+1,0
    else:
      tab[n][s] = tab[n-1][s]
      if a[n-1]<=s: tab[n][s] += tab[n][s-a[n-1]]
      s += 1
  return tab[N][S]