Shared code

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int solve(vector<int>& x, int n, int target, vector<vector<int>>& memo) {
    if (target == 0) return 1;
    if (n == 0 || target < 0) return 0;
    if (memo[n][target] != -1) return memo[n][target];
    
    int ways = (solve(x, n - 1, target, memo) + solve(x, n, target - x[n - 1], memo)) % mod;
    return memo[n][target] = ways;
}

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> x(n);
    for (int& v : x) cin >> v;

    vector<vector<int>> memo(n + 1, vector<int>(target + 1, -1));
    cout << solve(x, n, target, memo) << endl;
    return 0;
}