动态规划：
f(i,j)表示选择前i种商品构成消费券价值为j的方案数量，price_i表示第i种商品的价格。
状态转移：
f(i,j) = f(i-1,j)+ f(i-1,j-1price_i)...+f(i-1,j-kprice_i), k=(j/price_i)
因为
f(i,j-price_i) = f(i-1,j-price_i)+.....+f(i-1,j-k*price_i)
故状态转移方程：

f(i,j) = f(i-1,j)+f(i,j-price_i) 
str1 = input()
arr = str1.split()
# 购物券的价格
money = int(arr[0])  
# 获取商品的价格列表
price = [int(i) for i in arr[1] if i.isdigit()]
# 商品列表长度
n = len(price)
# 记录状态值
dp = [[0 for i in range(money+1)]for j in range(n+1)]
for i in range(1,n+1):
    dp[i][0] = 1  # 给定初始值
for i in range(1,n+1):
    for j in range(1,money+1):
        dp[i][j] = dp[i-1][j]
        if j>=price[i-1]:
            dp[i][j]+=dp[i][j-price[i-1]]
print(dp[-1][-1])


但是只能通过90%的案例，最后一个结果案例的结果比较大，应该要对其取相应的余数，但是题目没有告诉。