UAIC Competitive Programming

Problem 65: Subset Sum Count Modulo Partition

Problem Statement: Given an array of positive integers and an integer S, count the number of subsets that sum exactly to S modulo 10^9+7.

Input

The first line contains n and S. The second line contains n space-separated integers.

Output

Print the number of subsets whose sum equals S modulo 10^9+7.

Examples


Input:
4 5
1 2 3 4

Output:
2
                

Solution Explanation

Use dynamic programming where dp[i][j] counts the number of ways to achieve sum j using first i elements. Optimize space by using a 1D DP array and iterating backwards.

Solution in C++


#include 
#include 
using namespace std;

const int MOD = 1000000007;

int main(){
    int n, S; 
    cin >> n >> S;
    vector a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    vector dp(S + 1, 0);
    dp[0] = 1;
    for(int num : a){
        for(int s = S; s >= num; s--){
            dp[s] = (dp[s] + dp[s - num]) % MOD;
        }
    }
    cout << dp[S] << "\n";
    return 0;
}