def getWaysHelper(target, index, coins, solved):
    if index == len(coins) or target < 0:
        return 0
    if target == 0:
        return 1
    if (target, index) in solved:
        return solved[(target, index)]
    
    curcoin = coins[index]
    p1 = getWaysHelper(target-curcoin, index, coins, solved)
    p2 = getWaysHelper(target, index+1, coins, solved)

    solved[(target, index)] = p1 + p2
    return p1 + p2

def getWays(n, c):
    solutiontable = dict()
    return getWaysHelper(target=n, index=0, coins=c, solved=solutiontable)