この問題は、いわゆるナップサック DP によって解くことができます。

具体的には、\(\mathrm{dp} _ i[j]\coloneqq i\) 番目までの商品を使ってちょうど \(j\) 円分購入する方法の数 とすると、

\[\begin{aligned}\mathrm{dp} _ 0[j]&=\begin{cases}1&(j=0)\\0&(j\ne0)\end{cases}\\\mathrm{dp} _ i[j]&=\begin{cases}\mathrm{dp} _ {i-1}[j]&(0\le j\lt P _ i)\\\mathrm{dp} _ {i-1}[j]+\mathrm{dp} _ {i-1}[j-P _ i]&(P _ i\le j)\end{cases}\ (0\lt i)\end{aligned}\]

と計算することができます。

すべての \(\mathrm{dp} _ i\) を保管すると空間計算量は \(O(NK)\) となりますが、DP テーブルを使いまわすことで空間計算量を \(O(K)\) とすることもできます。 時間計算量は \(O(NK)\) となります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <atcoder/modint>
using namespace std;
using modint = atcoder::static_modint<1000000007>;

int main() {
    int N, K;
    cin >> N >> K;
    vector<modint> dp(K + 1);
    dp[0] = 1;
    for (int i = 0; i < N; ++i) {
        int P;
        cin >> P;
        for (int j = K - P; j >= 0; --j) {
            dp[j + P] += dp[j];
        }
    }
    cout << dp[K].val() << endl;
    return 0;
}

N, K = map(int, input().split())

dp = [0 for i in range(K + 1)]
dp[0] = 1

for P in map(int, input().split()):
    for j in range(K - P, -1, -1):
        dp[j + P] += dp[j]
        dp[j + P] %= 1000000007

print(dp[K])