换钱的方法数

# -*- coding: utf-8 -*-
# !/usr/bin/python3

import sys

while True:
    s = sys.stdin.readline().strip()
    if s == '':
        break
    else:
        n, t = s.split()
        n = int(n)
        t = int(t)

        arr = list(map(int, input().split()))
        arr = sorted(arr)

        res = [0 for i in range(t + 1)]
        res[0] = 1

        for i in arr:
            if i > t:
                break
            for j in range(i, t + 1):
                res[j] = res[j] + res[j - i]

        # 输出一个整数，表示换钱的方法数对10 ^ 9 +7取模后的答案。
        print(res[t] % (pow(10, 9) + 7))
        
'''
解题思路：
动态规划核心状态转移方程式
f（n） = f(n - arr[0]) + f(n - arr[1]) + f(n - arr[2]) + ... + f(n - arr[i]) i为arr的长度
对于组成n的情况，每个arr[i]元与f（n - arr[i]）都可以组成一个n，所以把每种f（n - arr[i]）的种类数
相加，就找出了arr能组成n的种类。递归计算会重复计算f（n - arr[i]），运用斐波那契数列类似的方法，
从0开始遍历，重复利用计算过的f（n - arr[i]）。结果数值会过大，题目要求输出对10 ^ 9 +7取模后的答案。
'''

def count_way(arr, n):
    # 第0位是辅助位，代表面额数刚好等于金钱数的一种情况
    dp = [1] + [0]*n               # 不用任意面额的组合数
    for num in arr:
        for j in range(num, n+1):
            dp[j] += dp[j-num]
    return dp[-1]%(1000000007)
_,n = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
print(count_way(arr, n))