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

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