Given an amount and the denominations of coins available, determine how many ways change can be made for amount.  There is a limitless supply of each coin type.  

Example 

$n=3$ 

$c=[8,3,1,2]$  

There are $3$ ways to make change for $n=3$: $\{1,1,1\}$, $\{1,2\}$, and $\{3\}$.

Function Description  

Complete the getWays function in the editor below.  

getWays has the following parameter(s):

int n: the amount to make change for  
int c[m]: the available coin denominations   

Returns   

int: the number of ways to make change  

Input Format

The first line contains two space-separated integers $n$ and $m$, where: 

$n$ is the amount to change 

$m$ is the number of coin types 

The second line contains $m$ space-separated integers that describe the values of each coin type.  

Constraints

$1\leq c[i]\leq50$
$1\leq n\leq250$
$1\leq m\leq50$
Each $c[i]$ is guaranteed to be distinct.

Hints

Solve overlapping subproblems using Dynamic Programming (DP): 

    You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
* Consider the degenerate cases: 

    - How many ways can you make change for $0$ cents? 
    - How many ways can you make change for $>0$ cents if you have no coins?
* If you're having trouble defining your solutions store, then think about it in terms of the base case $\left(n=0\right)$.
- The answer may be larger than a $32$-bit integer.

Sample Input 0
4 3
1 2 3

Sample Output 0
4

Explanation 0

There are four ways to make change for $n=4$ using coins with values given by $C=[1,2,3]$:

$\{1,1,1,1\}$
$\{1,1,2\}$
$\{2,2\}$
$\{1,3\}$ 

Sample Input 1
10 4
2 5 3 6

Sample Output 1
5

Explanation 1

There are five ways to make change for $n=10$ units using coins with values given by $C=[2,5,3,6]$:

$\{2,2,2,2,2\}$
$\{2,2,3,3\}$
$\{2,2,6\}$
$\{2,3,5\}$ 
$\{5,5\}$

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import sys
sys.setrecursionlimit(1000)
memo = {}

def n_ways(v, max_c):
	if (v, max_c) in memo:
		return memo[v, max_c]
	if v == 0:
		return 1
	if v < min(C):
		return 0
	sum = 0
	for each in C:
		if each <= max_c:
			sum += n_ways(v - each, each)
	memo[v, max_c] = sum
	return sum
N = list(map(int, input().split(' ')))[0]
C = list(map(int, input().rstrip(' ').split(' ')))
print(n_ways(N, max(C)))


def main():
	import sys
	sys.setrecursionlimit(10000000)

	def recurse(i, s):
		if s > N:
			return 0
		elif dp[i][s] >= 0:
			return dp[i][s]
		elif s == N:
			return 1
		else:
			dp[i][s] = 0
			for x in range(i, M):
				dp[i][s] += recurse(x, s + A[x])
		return dp[i][s]
	(N, M) = map(int, input().split())
	A = [int(x) for x in input().split()]
	dp = [[-1 for s in range(N + 1)] for i in range(M)]
	print(recurse(0, 0))
main()


(N, M) = map(int, input().rstrip().split(' '))
coins = list(map(int, input().rstrip().split(' ')))
dp = [0] * (N + 1)
dp[0] = 1
for c in coins:
	for i in range(c, len(dp)):
		dp[i] += dp[i - c]
print(dp[N])


[n, m] = [int(x) for x in input().split()]
a = [-1] + [int(x) for x in input().split()]
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
	f[i][0] = 1
	for j in range(1, n + 1):
		if j >= a[i]:
			f[i][j] = f[i][j - a[i]] + f[i - 1][j]
		else:
			f[i][j] = f[i - 1][j]
print(f[m][n])


def ways(amt, coins, forbidden, cache):
	if cache[amt][forbidden] is not None:
		return cache[amt][forbidden]
	nways = 0
	for i in range(forbidden, len(coins)):
		coin = coins[i]
		if coin > amt:
			break
		nways += ways(amt - coin, coins, i, cache)
	cache[amt][forbidden] = nways
	return nways

def readints():
	return [int(f) for f in input().split()]
(amt, ncoins) = readints()
coins = sorted(readints())
assert ncoins == len(coins)
cache = [[1] * (ncoins + 1)] + [[None] * ncoins + [0] for _ in range(amt)]
print(ways(amt, coins, 0, cache))


cache = {}

def solve(n, coins, last_coin=None):
	if last_coin is not None and last_coin in cache.get(n, {}):
		return cache[n][last_coin]
	if n == 0:
		result = 1
	else:
		result = 0
		for c in coins:
			if c <= n and (last_coin is None or c <= last_coin):
				result += solve(n - c, coins, c)
	if n not in cache:
		cache[n] = {}
	if last_coin is not None:
		cache[n][last_coin] = result
	return result

def main():
	(n, m) = map(int, input().strip().split())
	coins = sorted(map(int, input().strip().split()), reverse=True)
	print(solve(n, coins))
main()


N = int(input().split()[0])
L = input().split()
L = [int(i) for i in L]

def coin_change(N, coins):
	D = {}
	for i in range(1, len(coins)):
		D[i, 0] = 1
	for k in range(0, N + 1):
		if k % coins[0] == 0:
			D[0, k] = 1
		else:
			D[0, k] = 0
	for i in range(1, len(coins)):
		for j in range(1, N + 1):
			if j >= coins[i]:
				D[i, j] = D[i - 1, j] + D[i, j - coins[i]]
			else:
				D[i, j] = D[i - 1, j]
	return D[len(coins) - 1, N]
print(coin_change(N, L))


(total, coinsCount) = input().split()
(total, coinsCount) = (int(total), int(coinsCount))
coinsArray = input().split()
coinsArray = [int(i) for i in coinsArray]
answers = {}

def numberOfWaysToGetCents(targetValue, coins):
	if (targetValue, tuple(coins)) in answers:
		return answers[targetValue, tuple(coins)]
	if targetValue > 0 and len(coins) <= 0:
		return 0
	elif targetValue == 0:
		return 1
	elif targetValue < 0:
		return 0
	else:
		coin = coins[0]
		removedCoins = coins[:]
		removedCoins.remove(coin)
		result = numberOfWaysToGetCents(targetValue - coin, coins) + numberOfWaysToGetCents(targetValue, removedCoins)
		answers[targetValue, tuple(coins)] = result
		return result
for i in range(0, total + 1):
	numberOfWaysToGetCents(i, coinsArray)
	if i == total:
		print(answers[i, tuple(coinsArray)])


(n, m) = map(int, input().split())
coin = [int(x) for x in input().split()]
li = [0] * (n + 1)
li[0] = 1
for c in coin:
	for i in range(c, n + 1):
		li[i] += li[i - c]
print(li[n])


def count(S, m, n):
	table = [0] * (n + 1)
	table[0] = 1
	for i in range(m):
		for j in range(S[i], n + 1):
			table[j] += table[j - S[i]]
	return table[n]
(N, M) = [int(ns) for ns in str(input()).split()]
C = [int(ns) for ns in str(input()).split()]
print(count(C, M, N))


(n, m) = map(int, input().split())
c = sorted(list(map(int, input().split())))
mem = {}

def solution(b, i=0):
	if b < 0:
		return 0
	elif b == 0:
		return 1
	elif (b, i) in mem:
		return mem[b, i]
	acc = 0
	for (i2, v) in enumerate(c[i:]):
		if v > b:
			break
		acc += solution(b - v, i2 + i)
	mem[b, i] = acc
	return acc
print(solution(n))


(n, m) = input().split()
c = input().split()
a = []
for i in range(int(m) + 1):
	a.append([1])
	for j in range(1, int(n) + 1):
		a[i].append(0)
for i in range(1, int(m) + 1):
	for j in range(1, int(n) + 1):
		if j - int(c[i - 1]) >= 0:
			a[i][j] = a[i - 1][j] + a[i][j - int(c[i - 1])]
		else:
			a[i][j] = a[i - 1][j]
print(a[int(m)][int(n)])


def hashable(target, values):
	return str(target) + ''.join(['{0:02d}'.format(i) for i in values])

def counter(target, values, dp):
	dphelp = hashable(target, values)
	if dphelp in dp:
		return [dp[dphelp], dp]
	if target:
		if len(values) != 1:
			value = 0
			for i in range(target // values[-1] + 1):
				ph = counter(target - i * values[-1], values[:-1], dp)
				value += ph[0]
				dp = ph[1]
			dp[dphelp] = value
			return [value, dp]
		if target % values[0] == 0:
			return [1, dp]
		return [0, dp]
	return [1, dp]
paras = [int(i) for i in input().strip().split()]
values = sorted([int(i) for i in input().strip().split()])
dp = {}
print(counter(paras[0], values, dp)[0])


(N, M) = [int(s) for s in input().split()]
coins = [int(s) for s in input().split()]
coins.sort()
cache = dict()

def give_change(amt, min_coin):
	if amt == 0:
		return 1
	if amt < 0:
		return 0
	if (amt, min_coin) in cache:
		return cache[amt, min_coin]
	results = 0
	new_min = min_coin
	for cval in coins[min_coin:]:
		temp = give_change(amt - cval, new_min)
		results += temp
		new_min += 1
	cache[amt, min_coin] = results
	return results
print(give_change(N, 0))


def coins_topdown(N, M, C):
	table = [0] * (N + 1)
	table[0] = 1
	for i in range(M):
		for j in range(C[i], N + 1):
			table[j] += table[j - C[i]]
	return table
from collections import defaultdict
line1 = input().split()
line2 = input().split()
N = int(line1[0])
M = int(line1[1])
C = [int(x) for x in line2]
C.sort(reverse=True)
ans = coins_topdown(N, M, C)
print(ans[-1])


(target, _) = map(int, input().split())
denominations = [int(x) for x in input().split()]
size = len(denominations) - 1

def solve(k, capacity, memo={}):
	key = (k, capacity)
	if key in memo:
		return memo[key]
	if k > size:
		return 0
	denomination = denominations[k]
	res = 0
	for weight in range(capacity // denomination + 1):
		remaining_capacity = capacity - weight * denomination
		if remaining_capacity > 0:
			res += solve(k + 1, remaining_capacity)
		else:
			res += 1
	memo[key] = res
	return res
print(solve(0, target))


def combs(n, coins):
	a = [0 for x in range(n + 1)]
	a[0] = 1
	for c in coins:
		for i in range(c, n + 1 - c):
			a[i] = a[i] + a[i - c]
		if n >= c:
			a[n] = a[n] + a[n - c]
	return a[n]
tmp = input().split()
N = int(tmp[0])
M = int(tmp[1])
coins = [int(x) for x in input().split()]
coins = sorted(coins)
print(combs(N, coins))


(n, m) = input().split()
(n, m) = (int(n), int(m))
l = list(map(int, input().split()))
l.sort()
l.reverse()
arr = []
for i in range(0, n + 1):
	row = []
	for j in range(0, m):
		row.append(0)
	arr.append(row)
for i in range(1, n + 1):
	for j in range(0, m):
		if i - l[j] < 0:
			arr[i][j] = 0
		if i - l[j] == 0:
			arr[i][j] = 1
		if i - l[j] > 0:
			arr[i][j] = arr[i - l[j]][j]
		if j > 0:
			arr[i][j] += arr[i][j - 1]
print(arr[n][m - 1])


def solve(n, m, c_list):
	memo = [0] * (n + 1)
	memo[0] = 1
	for i in range(m):
		for j in range(c_list[i], n + 1):
			memo[j] += memo[j - c_list[i]]
	return memo[n]
(n, m) = map(int, input().split())
c_list = list(map(int, input().split()))
print(solve(n, m, c_list))


(Price, CoinCount) = [int(x) for x in input().split()]
Coins = [int(x) for x in input().split()]
Combinations = [0] * (Price + 1)
Combinations[0] = 1
for coin in Coins:
	for j in range(coin, Price + 1):
		Combinations[j] += Combinations[j - coin]
print(Combinations[Price])


def solve(n, m, c):
	dp = [[1] * m for _ in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(m):
			x = y = 0
			if i - c[j] >= 0:
				x = dp[i - c[j]][j]
			if j >= 1:
				y = dp[i][j - 1]
			dp[i][j] = x + y
	return dp
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
print(solve(n, m, c)[n][m - 1])


s1 = input()
s2 = input()
W = int(s1.split()[0])
C = [int(x) for x in s2.split()]
C.sort()
WL = list(range(W + 1))
N = len(C)
T = [[1] * (W + 1) for row in range(N)]
for i in range(W + 1):
	if WL[i] % C[0] != 0:
		T[0][i] = 0
for i in range(1, N):
	for j in range(1, W + 1):
		if WL[j] < C[i]:
			T[i][j] = T[i - 1][j]
		else:
			T[i][j] = T[i - 1][j] + T[i][j - C[i]]
print(T[N - 1][W])


def num_change(coins, amount):
	result = [[0 for _ in coins] for _ in range(amount + 1)]
	for (i, _) in enumerate(coins):
		result[0][i] = 1
	for i in range(amount + 1):
		for (j, _) in enumerate(coins):
			if i >= coins[j]:
				result[i][j] = result[i][j - 1] + result[i - coins[j]][j]
			else:
				result[i][j] = result[i][j - 1]
	return result[-1][-1]
(amount, _) = [int(el) for el in input().split()]
coins = [int(el) for el in input().split()]
print(num_change(coins, amount))


import sys

def ways_to_change(n, coins, cache={}):
	if n == 0:
		return 1
	if not coins:
		return 0
	key = (n, coins)
	if key in cache:
		return cache[key]
	coin = coins[0]
	ways_count = 0
	for i in range(n // coin + 1):
		if n - i * coin >= 0:
			ways_count += ways_to_change(n - i * coin, coins[1:])
	cache[key] = ways_count
	return ways_count

def main():
	(n, _) = map(int, sys.stdin.readline().split())
	coins = tuple(map(int, sys.stdin.readline().split()))
	print(ways_to_change(n, coins))
main()


(n, m) = map(int, input().split())
coins = map(int, input().split())
sums = {0: 1}
for coin in coins:
	new_sums = {}
	for somma in sums:
		for new_somma in range(somma + coin, n + 1, coin):
			if new_somma not in new_sums:
				new_sums[new_somma] = 0
			new_sums[new_somma] += sums[somma]
	for new_somma in new_sums:
		if new_somma not in sums:
			sums[new_somma] = 0
		sums[new_somma] += new_sums[new_somma]
print(sums.get(n, 0))


def memo(f):
	cache = {}

	def inner_warp(*args):
		if args not in cache:
			cache[args] = f(*args)
		return cache[args]
	return inner_warp

def coin_change(n, ls):
	ls.sort()
	length = len(ls)

	@memo
	def inner_find(a, i):
		if a <= 0:
			return int(a == 0)
		if i == 0:
			return int(a % ls[0] == 0)
		if a >= ls[i]:
			return inner_find(a - ls[i], i) + inner_find(a, i - 1)
		return inner_find(a, i - 1)
	return inner_find(n, length - 1)
(a, b) = list(map(int, input().split()))
k = input().split()
k = list(map(int, k))
print(coin_change(a, k))


def coin_change(N, M, coin_list):
	d = [0 for x in range(N + 1)]
	d[0] = 1
	for coin in coin_list:
		for i in range(1, N + 1):
			if i - coin >= 0 and d[i - coin] >= 1:
				d[i] = d[i] + d[i - coin]
	return d[-1]
(N, M) = [int(x) for x in input().split()]
coin_list = [int(x) for x in input().split()]
ans = coin_change(N, M, coin_list)
print(ans)


from collections import defaultdict
nested_dict = lambda : defaultdict(nested_dict)
memo = nested_dict()

def coin_change(coins, m, n):
	if memo[m][n]:
		return memo[m][n]
	if n == 0:
		value = 1
	elif n < 0 or (m < 0 and n > 0):
		value = 0
	else:
		value = coin_change(coins, m - 1, n) + coin_change(coins, m, n - coins[m])
	memo[m][n] = value
	return value
(n, _) = list(map(int, input().split()))
coins = sorted(map(int, input().split()))
print(coin_change(coins, len(coins) - 1, n))


(N, M) = map(int, input().split())
C = [int(c) for c in input().split()]
solutions = [0 if x > 0 else 1 for x in range(N + 1)]
for coin in C:
	for n in range(N, 0, -1):
		ways = 0
		for change in range(n - coin, -1, -coin):
			ways += solutions[change]
		solutions[n] += ways
print(solutions[N])


(value, m) = list(map(int, input().split()))
f = list(map(int, input().split()))
f.sort()
memo = [[0 for x in range(m + 1)] for y in range(value + 1)]
for i in range(value // f[0] + 1):
	memo[i * f[0]][0] = 1
for t in range(1, m):
	for i in range(value // f[t] + 1):
		for j in range(value + 1 - i * f[t]):
			memo[j + i * f[t]][t] += memo[j][t - 1]
print(memo[value][m - 1])


n = int(input().split(' ')[0])
coins = [int(i) for i in input().split(' ') if i != '']
coins.sort(reverse=True)
m = {}

def count(index, n):
	if (index, n) in m:
		return m[index, n]
	if n == 0:
		return 1
	if n < 0:
		return 0
	if index >= len(coins) and n >= 1:
		return 0
	temp = count(index, n - coins[index]) + count(index + 1, n)
	m[index, n] = temp
	return temp
print(count(0, n))


(N, M) = str(input()).split()
N = int(N)
M = int(M)
coins = str(input()).split()
coins = [int(c) for c in coins]
change = []
for cents in range(0, N + 1):
	number_of_ways_using_k_coins = []
	for k in range(0, M + 1):
		number_of_ways_using_k_coins.append(0)
	change.append(number_of_ways_using_k_coins)
for i in range(1, M + 1):
	change[0][i] = 1
for cents in range(1, N + 1):
	for j in range(1, M + 1):
		count = change[cents][j - 1]
		if cents >= coins[j - 1]:
			count += change[cents - coins[j - 1]][j]
		change[cents][j] = count
print(change[N][M])


T = input().split()
N = int(T[0])
M = int(T[1])
C = list(map(int, input().split()))
count = 0
dp = [0] * (N + 1)
dp[0] = [1] * M
for i in range(1, N + 1):
	dp[i] = [0] * M
	for j in range(0, M):
		if i - C[j] >= 0:
			x = dp[i - C[j]][j]
		else:
			x = 0
		if j >= 1:
			y = dp[i][j - 1]
		else:
			y = 0
		dp[i][j] = x + y
print(dp[N][M - 1])


memo = {}

def coin_permute(amount, coins, last_c):
	key = (amount, last_c)
	if key in memo:
		return memo[key]
	total = 0
	for c in coins:
		if c > last_c:
			break
		if c < amount:
			total += coin_permute(amount - c, coins, c)
		elif c == amount:
			total += 1
	memo[key] = total
	return total
(n, m) = (int(x) for x in input().split())
coins = sorted([int(x) for x in input().split()])
print(coin_permute(n, coins, coins[-1]))


(n, m) = map(int, input().split())
matrix = [[0] * m for i in range(0, n + 1)]
c = list(map(int, input().split()))
matrix[0][0] = 1
for i in range(0, n + 1):
	for j in range(0, m):
		if i >= c[j]:
			matrix[i][j] += matrix[i - c[j]][j]
		if j >= 1:
			matrix[i][j] += matrix[i][j - 1]
print(matrix[n][m - 1])


import collections
import functools

class memoized(object):

	def __init__(self, func):
		self.func = func
		self.cache = {}

	def __call__(self, *args):
		if not isinstance(args, collections.Hashable):
			return self.func(*args)
		if args in self.cache:
			return self.cache[args]
		else:
			value = self.func(*args)
			self.cache[args] = value
			return value

	def __repr__(self):
		return self.func.__doc__

	def __get__(self, obj, objtype):
		return functools.partial(self.__call__, obj)

@memoized
def count(tot, ar):
	if tot == 0:
		return 1
	if tot < 0 or len(ar) == 0:
		return 0
	return count(tot - ar[0], ar) + count(tot, ar[1:])
(tot, n) = input().strip().split()
(tot, n) = (int(tot), int(n))
ar = []
line = input().strip().split()
for each in range(n):
	ar.append(int(line[each]))
print(count(tot, tuple(ar)))


from functools import lru_cache
(N, M) = [int(x) for x in input().split()]
coins = [int(x) for x in input().split()]

@lru_cache(maxsize=None)
def coinSums(coinSum, lastCoin):
	if coinSum == 0:
		return 1
	elif coinSum < 0 or lastCoin < 0:
		return 0
	return coinSums(coinSum - coins[lastCoin], lastCoin) + coinSums(coinSum, lastCoin - 1)
print(coinSums(N, M - 1))


def changes(amount, coins):
	ways = [0] * (amount + 1)
	ways[0] = 1
	for coin in coins:
		for j in range(coin, amount + 1):
			ways[j] += ways[j - coin]
	return ways[amount]
N = int(input().split()[0])
C = [int(x) for x in input().split()]
print(changes(N, C))


lists = [int(_) for _ in input().split()]
S = lists[0]
N = lists[1]
arr = [0]
grid = [[0 for _ in range(0, S + 1)] for _ in range(0, N + 1)]
lists = [int(_) for _ in input().split()]
lists.sort()
arr = arr + lists
i = 0
while i <= N:
	j = 0
	while j <= S:
		if i != 0 and j == 0:
			grid[i][j] = 1
		j += 1
	i += 1
i = 1
while i <= N:
	j = 1
	while j <= S:
		if j < arr[i]:
			grid[i][j] = grid[i - 1][j]
		else:
			grid[i][j] = grid[i - 1][j] + grid[i][j - arr[i]]
		j += 1
	i += 1
print(grid[N][S])


def get_v(arr, i):
	if i >= 0:
		return arr[i]
	return 0
inp = list(map(int, input().split()))
N = inp[0]
C = inp[1]
coins = list(map(int, input().split()))
coins.sort()
vals = [None for i in range(N + 1)]
for i in range(N + 1):
	vals[i] = [0 for j in range(C + 1)]
for i in range(1, C + 1):
	vals[0][i] = 1
for i in range(1, N + 1):
	vals[i][0] = 0
	for j in range(1, C + 1):
		value = vals[i][j - 1]
		if coins[j - 1] <= i:
			value += vals[i - coins[j - 1]][j]
		vals[i][j] = value
print(vals[N][C])


(n, m) = map(int, input().split())
s = list(map(int, input().split()))
table = [0 for j in range(n + 1)]
table[0] = 1
for i in range(m):
	for j in range(s[i], n + 1):
		table[j] += table[j - s[i]]
print(table[n])


s = input().split()
N = int(s[0])
M = int(s[1])
lis = [int(i) for i in input().split()]

def fun(lis, M, N):
	tab = [0] * (N + 1)
	tab[0] = 1
	for i in range(0, M):
		for j in range(lis[i], N + 1):
			tab[j] = tab[j] + tab[j - lis[i]]
	return tab[N]
ans = fun(lis, M, N)
print(ans)


(n, m) = map(int, input().split())
c = sorted(list(map(int, input().split())))
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(n + 1):
	for j in range(m + 1):
		if i == 0 or j == 0:
			continue
		if i == c[j - 1]:
			dp[i][j] += 1
		if i - c[j - 1] >= 0:
			dp[i][j] += dp[i - c[j - 1]][j]
		dp[i][j] += dp[i][j - 1]
print(dp[n][m])


(N, M) = (int(x) for x in input().split())
C = [int(x) for x in input().split()]
ret = [0 for x in range(N + 1)]
ret[0] = 1
for c in C:
	for i in range(c, N + 1):
		ret[i] += ret[i - c]
print(ret[-1])


def coin_change(n, m, C):
	d = [[0 for x in range(0, m + 1)] for y in range(0, n + 1)]
	d[0] = [1] * (m + 1)
	for i in range(1, n):
		d[i][0] = 0
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			prev = i - C[j - 1]
			if prev >= 0:
				d[i][j] = d[i][j - 1] + d[prev][j]
			else:
				d[i][j] = d[i][j - 1]
	return d[n][m]
(n, m) = input().split()
(n, m) = (int(n), int(m))
C = input().split()
for i in range(m):
	C[i] = int(C[i])
res = coin_change(n, m, C)
print(res)


def solve(coins, n):
	arr = [0 for x in range(n + 1)]
	arr[0] = 1
	for x in range(0, len(coins)):
		for y in range(coins[x], n + 1):
			arr[y] += arr[y - coins[x]]
	return arr[n]
m = int(input().split()[0])
print(solve([int(x) for x in input().split()], m))


(m, n) = input().split()
m = int(m)
n = int(n)
coins = list(map(int, input().split()))
coins.sort()
dp = [0] * (m + 1)
ncoins = len(coins)
dp[0] = 1
count = 0
for x in range(0, n):
	for y in range(coins[x], m + 1):
		dp[y] = dp[y] + dp[y - coins[x]]
print(dp[m])


from functools import lru_cache

def number_of_changes(N, coins):
	M = len(coins)
	S = sorted(coins)

	@lru_cache(maxsize=None)
	def count(n, m):
		if n == 0:
			return 1
		elif n < 0:
			return 0
		elif m <= 0:
			return 0
		else:
			return count(n, m - 1) + count(n - S[m - 1], m)
	return count(N, M)
(N, M) = map(int, input().strip().split())
coins = list(map(int, input().strip().split()))
print(number_of_changes(N, coins))


(n, m) = map(int, input().split(' '))
nums = list(map(int, input().strip().split(' ')))
state = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(m + 1):
	state[0][i] = 1
for i in range(1, n + 1):
	for j in range(1, m + 1):
		state[i][j] = state[i][j - 1]
		if i >= nums[j - 1]:
			state[i][j] += state[i - nums[j - 1]][j]
print(state[-1][-1])


(n, m) = map(int, input().strip().split())
coin = list(map(int, input().strip().split()))
a = [[1] * (n + 1)] * (m + 1)

def ways(n):
	for i in range(m):
		for j in range(1, n + 1):
			x = 0
			if j - coin[i] >= 0:
				x = a[i][j - coin[i]]
			y = 0
			if i >= 1:
				y = a[i - 1][j]
			a[i][j] = x + y
	return a[m - 1][n]
print(ways(n))


def calcWays(f, target, coins, maxCoin):
	count = 0
	if target > 0:
		if maxCoin == 0:
			if target % coins[0] == 0:
				count = 1
		else:
			for i in range(maxCoin + 1):
				if target == coins[i]:
					count += 1
				elif target > coins[i]:
					count += getWays(f, target - coins[i], coins, i)
	f[maxCoin][target] = count
	return count

def getWays(f, target, coins, maxCoin):
	count = f[maxCoin][target]
	if count < 0:
		count = calcWays(f, target, coins, maxCoin)
	return count

def countTheWays(target, coins):
	N = target
	if N < 1 or N > 250:
		raise RuntimeError('N value (N) is out of range: %d' % N)
	M = len(coins)
	if M == 0 or M > 50:
		raise RuntimeError('unacceptable number of coins: %d' % M)
	coins.sort()
	f = []
	for m in range(M):
		row = [-1 for i in range(N + 1)]
		f.append(row)
	maxCoin = M - 1
	for i in range(M - 1, -1, -1):
		if target >= coins[i]:
			maxCoin = i
			break
	count = getWays(f, target, coins, maxCoin)
	return count
ss = input().strip().split()
N = int(ss[0])
M = int(ss[1])
ss = input().strip().split()
if len(ss) != M:
	raise RuntimeError('expected M=%d coins but got %d' % (M, len(ss)))
coins = []
for val in ss:
	coins.append(int(val))
coins.sort()
print(countTheWays(N, coins))


from functools import lru_cache
(N, _) = map(int, input().split())
Ms = tuple(sorted(map(int, input().split()), reverse=True))

@lru_cache(maxsize=None)
def getPossibleChange(N, Ms):
	if len(Ms) == 1:
		if N % Ms[0] == 0:
			return 1
		return 0
	(cm, *rest) = Ms
	count = 0
	solutions = 0
	while True:
		newN = N - count * cm
		count = count + 1
		if newN < 0:
			break
		elif newN == 0:
			solutions += 1
		else:
			solutions += getPossibleChange(newN, tuple(rest))
	return solutions
print(getPossibleChange(N, Ms))


def count(T, S, n, m):
	for i in range(0, n + 1):
		for j in range(0, m + 1):
			if i == 0:
				T[i][j] = 1
			elif j == 0:
				T[i][j] = 0
			elif S[j - 1] > i:
				T[i][j] = T[i][j - 1]
			else:
				T[i][j] = T[i][j - 1] + T[i - S[j - 1]][j]
	return T
line = input().split()
(N, M) = (int(line[0].strip()), int(line[1].strip()))
S = [int(x.strip()) for x in input().split()]
T = [[0 for j in range(0, len(S) + 1)] for i in range(0, N + 1)]
count(T, S, N, M)
print(T[N][M])


def coin_change(coins, n, m):
	table = []
	temp_table = []
	for i in range(0, m):
		temp_table.append(1)
	table.append(temp_table)
	for i in range(1, n + 1):
		temp_table = []
		for j in range(0, m):
			if i - coins[j] >= 0:
				x = table[i - coins[j]][j]
			else:
				x = 0
			if j >= 1:
				y = temp_table[j - 1]
			else:
				y = 0
			temp_table.append(x + y)
		table.append(temp_table)
	return table[n][m - 1]
inp = input().split()
n = int(inp[0])
m = int(inp[1])
coins = input().split()
for i in range(0, m):
	coins[i] = int(coins[i])
coins.sort()
print(coin_change(coins, n, m))


mem = {}

def cc(n, c):
	if n in mem and len(c) in mem[n]:
		return mem[n][len(c)]
	elif n < 0:
		return 0
	elif n == 0:
		return 1
	elif len(c) == 0:
		return 0
	else:
		key = n - c[0]
		x = cc(key, c)
		if key >= 0:
			if key not in mem:
				mem[key] = {}
			mem[key][len(c)] = x
		y = cc(n, c[1:])
		if n not in mem:
			mem[n] = {}
		mem[n][len(c) - 1] = y
		return x + y
(n, m) = list(map(int, input().split()))
c = sorted(list(map(int, input().split())), reverse=True)
print(cc(n, c))


def change(target, coins):
	s = []
	for (i, coin) in enumerate(coins):
		s.append([1])
		for j in range(1, target + 1):
			if i > 0:
				s[i].append(s[i - 1][j])
			else:
				s[i].append(0)
			if j >= coin:
				s[i][j] += s[i][j - coin]
	return s[i][j]
(target, n_coins) = map(int, input().split())
coins = list(map(int, input().split()))
print(change(target, coins))


def ways_for_change(N, a, lo):
	if N < 0:
		return 0
	if N == 0:
		return 1
	if N > 0 and len(a[lo:]) == 0:
		return 0
	count = 0
	for i in range(lo, len(a)):
		value = a[i]
		if my_lookup[N - value][i] != -1:
			count += my_lookup[N - value][i]
		else:
			my_lookup[N - value][i] = ways_for_change(N - value, a, i)
			count += my_lookup[N - value][i]
	return count
[N, M] = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
my_lookup = [[-1 for i in range(51)] for i in range(251)]
print(ways_for_change(N, a, 0))


from collections import defaultdict
readinput = lambda x: [int(y) for y in x.split()]
(N, M) = readinput(input())
coins = readinput(input())
memo = defaultdict(int)

def counts(N, coins):
	if N == 0:
		return 1
	if N < 0 or not coins:
		return 0
	if memo[N, coins[0]]:
		return memo[N, coins[0]]
	count = 0
	for i in range(N // coins[0] + 1):
		count += counts(N - i * coins[0], coins[1:])
	memo[N, coins[0]] = count
	return count
print(counts(N, coins))


M = {}

def coin_change(N, C):
	if (N, C) in M:
		return M[N, C]
	if N == 0:
		return 1
	if N < 0:
		return 0
	if len(C) == 0:
		return 0
	r = coin_change(N - C[0], C) + coin_change(N, C[1:])
	M[N, C] = r
	return r
N = int(input().split()[0])
C = tuple(map(int, input().split()))
print(coin_change(N, C))


def coin_change(C, N, M):
	T = [0 for _ in range(N + 1)]
	T[0] = 1
	for i in range(M):
		for j in range(C[i], N + 1):
			T[j] += T[j - C[i]]
	return T[N]

def main():
	(N, M) = [int(i) for i in input().split()]
	C = [int(i) for i in input().split()]
	print(coin_change(C, N, M))
main()


(a, b) = map(int, input().split(' '))
coin = list(map(int, input().strip().split(' ')))
dp = [[-1] * 1000 for _ in range(1000)]

def f(m, c):
	if m < 0:
		dp[m][c] = 0
		return 0
	if dp[m][c] != -1:
		return dp[m][c]
	if m == 0:
		dp[m][c] = 1
		return 1
	if c < 0:
		dp[m][c] = 0
		return 0
	ans = f(m, c - 1) + f(m - coin[c], c)
	dp[m][c] = ans
	return ans
print(f(a, b - 1))


test = input('')
inlist = list(map(int, test.split()))
test = input('')
arr = list(map(int, test.split()))
table = [0] * (inlist[0] + 1)
table[0] = 1
for i in range(0, inlist[1]):
	for j in range(arr[i], inlist[0] + 1):
		table[j] += table[j - arr[i]]
print(table[inlist[0]])


def cases(p, v, n):
	sol = [[0 for x in range(p + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for j in range(p + 1):
			if j == 0:
				sol[i][j] = 1
	for i in range(1, n + 1):
		for j in range(1, p + 1):
			if j < v[i]:
				sol[i][j] = sol[i - 1][j]
			else:
				sol[i][j] = sol[i][j - v[i]] + sol[i - 1][j]
	print(sol[n][p])
(p, n) = map(int, input().split())
a = input()
v = []
v.append(0)
for x in a.split():
	num = int(x)
	v.append(num)
cases(p, v, n)


def count(X, Y, C):
	table = [[0 for i in range(Y + 1)] for j in range(X + 1)]
	for i in range(X + 1):
		for j in range(Y):
			if i == 0:
				table[i][j] = 1
			elif C[j] > i:
				table[i][j] = table[i][j - 1]
			else:
				table[i][j] = table[i - C[j]][j] + table[i][j - 1]
	return table[X][Y - 1]
(n, m) = input().split()
N = int(n)
M = int(m)
s = input().split()
S = [0 for i in range(M)]
for i in range(M):
	S[i] = int(s[i])
print(count(N, M, S))


[N, M] = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
A = [[0 for i in range(M + 1)] for j in range(N + 1)]
for i in range(N + 1):
	for j in range(M + 1):
		if i == 0:
			A[i][j] = 1
		elif j == 0:
			A[i][j] = 0
		elif C[j - 1] > i:
			A[i][j] = A[i][j - 1]
		else:
			A[i][j] = A[i - C[j - 1]][j] + A[i][j - 1]
print(A[N][M])


def print_matrix(matrix, s, coins):
	print(' '.join([' ', ' '] + [str(x) for x in coins]))
	for (i, row) in enumerate(matrix):
		print(' '.join([str(i)] + [str(x) for x in row]))

def num_ways_to_make_change(s, coins):
	m = s + 1
	n = len(coins) + 1
	matrix = [[0 for _ in range(n)] for _ in range(m)]
	for j in range(n):
		matrix[0][j] = 1
	for i in range(1, m):
		for j in range(1, n):
			coin_value = coins[j - 1]
			matrix[i][j] = matrix[i][j - 1] + (matrix[i - coin_value][j] if i >= coin_value else 0)
	return matrix[-1][-1]
(s, n) = [int(x) for x in input().split()]
coins = [int(x) for x in input().split()]
print(num_ways_to_make_change(s, coins))


def Coin(N, M, C):
	if N == 0:
		return 1
	elif M == 0:
		return 0
	elif N < C[0]:
		return 0
	out = 0
	ind = 0
	out = Coin(N - C[M - 1], M, C) + Coin(N, M - 1, C[:-1])
	return out

def Coin_for(N, M, C):
	T = [[0 for m in range(M)] for n in range(N + 1)]
	for m in range(M):
		T[0][m] = 1
	for n in range(1, N + 1):
		for m in range(M):
			if m > 0:
				T[n][m] += T[n][m - 1]
			if n >= C[m]:
				T[n][m] += T[n - C[m]][m]
	return T[N][M - 1]
(N, M) = tuple(map(int, input().split()))
C = list(map(int, input().split()))
C = sorted(C)
print(Coin_for(N, M, C))


(n, m) = [int(s) for s in input().split()]
coins = [int(s) for s in input().split()]
ways = [[1] * m]
for i in range(n):
	ways += [[0] * m]
for i in range(1, n + 1):
	for j in range(m):
		ways[i][j] = sum((ways[i - coins[k]][k] for k in range(j, m) if i >= coins[k]))
print(ways[n][0])


def count(n, coins):
	ways = [0] * (n + 1)
	ways[0] = 1
	for c in coins:
		for j in range(c, n + 1):
			ways[j] += ways[j - c]
	return ways[n]
(n, m) = map(int, input().split())
coins = list(map(int, input().split()))
print(count(n, coins))


def counter(size, target, s):
	count = [[0 for x in range(target + 1)] for x in range(size)]
	for m in range(0, size):
		count[m][0] = 1
	for m in range(0, size):
		for n in range(1, target + 1):
			a = 0
			b = 0
			if m >= 1:
				a = count[m - 1][n]
			if n - s[m] >= 0:
				b = count[m][n - s[m]]
			count[m][n] = a + b
	return count[size - 1][target]
line = input().strip().split(' ')
target = int(line[0])
size = int(line[1])
s = list(map(int, input().strip().split(' ')))
print(counter(size, target, s))


(n, m) = map(int, input().split())
coins = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 1
for c in coins:
	for i in range(n + 1):
		if dp[i] > 0:
			if i + c <= n:
				dp[i + c] += dp[i]
print(dp[n])


def change(N, M, C):
	buffer = {}
	for j in range(0, M + 2):
		buffer[0, j] = 1
	for i in range(0, N + 1):
		buffer[i, 0] = 0
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			value = buffer[i, j - 1]
			if C[j - 1] <= i:
				value += buffer[i - C[j - 1], j]
			buffer[i, j] = value
	return buffer[N, M]
var = input().split()
(N, M) = (int(var[0]), int(var[1]))
var = input().split()
C = []
for i in range(0, M):
	C.append(int(var[i]))
print(change(N, M, C))


import sys

def memoize(function):
	cache = dict()

	def memoized_function(*args):
		if args in cache:
			return cache[args]
		else:
			result = function(*args)
			cache[args] = result
			return result
	return memoized_function

@memoize
def solve(N, coins):
	if N == 0:
		return 1
	if N < 0 or not coins:
		return 0
	return solve(N - coins[0], coins) + solve(N, coins[1:])
[N, _M] = [int(X) for X in sys.stdin.readline().split()]
coins = tuple([int(X) for X in sys.stdin.readline().split()])
print(solve(N, coins))


(n, m) = list(map(int, input().strip().split(' ')))
coins = list(map(int, input().strip().split(' ')))
ways = [0] * (n + 1)
ways[0] = 1
for coin in coins:
	for i in range(coin, n + 1):
		ways[i] += ways[i - coin]
print(ways[n])


MAX = 256
ans = [[0] * MAX for x in range(MAX)]

def coins(A, n, sum):
	(i, j, a, b) = (0, 0, 0, 0)
	for i in range(n + 1):
		ans[0][i] = 1
	for i in range(1, sum + 1):
		for j in range(n):
			if i - A[j] >= 0:
				a = ans[i - A[j]][j]
			else:
				a = 0
			if j >= 1:
				b = ans[i][j - 1]
			else:
				b = 0
			ans[i][j] = a + b
	return ans[sum][n - 1]
IN = list(map(int, input().split(' ')))
(sum, n) = (IN[0], IN[1])
inp = input()
A = list()
inp = inp.split()
for i in inp:
	A.append(int(i))
print(coins(A, n, sum))


(n, m) = list(map(int, input().split()))
cs = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 1
for c in cs:
	for i in range(c, len(dp)):
		dp[i] += dp[i - c]
print(dp[n])


inp = input()
n = int(inp.split()[0])
m = int(inp.split()[1])
c = input()
coins = [int(i) for i in c.split()]
table = []
l = []
table.append(l)
for i in range(0, m):
	l.append(1)
for i in range(1, n + 1):
	l = []
	for j in range(0, m):
		l.append(-1)
	table.append(l)
for i in range(1, n + 1):
	for j in range(0, m):
		if i - coins[j] >= 0:
			x = table[i - coins[j]][j]
		else:
			x = 0
		if j >= 1:
			y = table[i][j - 1]
		else:
			y = 0
		table[i][j] = x + y
print(table[-1][-1])


(amount, _) = [int(item) for item in input().strip().split()]
coins = [int(item) for item in input().strip().split()]
dp_arr = [1] + [0] * amount
for coin in coins:
	for idx in range(coin, amount + 1):
		dp_arr[idx] += dp_arr[idx - coin]
print(dp_arr[-1])


def numWays(target, coins):
	memoize = dict()

	def nw_rec(cumTotal, coinsLeft):
		if target == cumTotal:
			return 1
		elif target < cumTotal:
			return 0
		elif (cumTotal, len(coinsLeft)) not in memoize:
			memoize[cumTotal, len(coinsLeft)] = sum((nw_rec(cumTotal + c, coinsLeft[i:]) for (i, c) in enumerate(coinsLeft)))
		return memoize[cumTotal, len(coinsLeft)]
	return nw_rec(0, coins)
(target, numCoins) = list(map(int, input().strip().split(' ')))
coins = list(map(int, input().strip().split(' ')))
assert len(coins) == numCoins
print('{:d}'.format(numWays(target, coins)))


(targetValue, m) = [int(x) for x in input().strip().split(' ')]
coins = list([int(x) for x in input().strip().split(' ')])
count = 0
possComb = [1] + [0] * targetValue
for coin in coins:
	for i in range(coin, targetValue + 1):
		possComb[i] += possComb[i - coin]
print(possComb[targetValue] + count)