# 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_super_opt(a, S):
  N = len(a)
  tab = [ 1 if s==0 else 0 for s in range(S+1) ]
  n,s = 1,0
  while n!=N+1:
    if s==S+1: n,s = n+1,0
    else:
      if a[n-1]<=s : tab[s] += tab[s-a[n-1]]
      s += 1
  return tab[S]