Sarthak | Perfect Sum Problem

using namespace std;

int main() {
    //code
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> a(n,0);
        for(int i=0; i<n; i++){
            int x;
            cin>>x;
            a[i] = x;
        }
        int k;
        cin>>k;
        vector<vector<int>> dp(n,vector<int>(k+1,0));
        dp[n-1][0] = 1;
        if(a[n-1]<=k)
        dp[n-1][a[n-1]] += 1;
        for(int i=n-2; i>=0; i--){
            for(int j=0; j<=k; j++){
                dp[i][j] = dp[i+1][j]%(1000000000+7);
                if(j-a[i]>=0){
                    dp[i][j] += (dp[i+1][j-a[i]]%(1000000000+7));
                }
            }
        }

        cout<<dp[0][k]%(1000000000+7)<<endl;
    }
    return 0;
}