CSES Problem Set Coin Combinations II Solution

 

CSES Problem Set

Coin Combinations II

Consider a money system consisting of n$n$ coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x$x$ using the available coins.

For example, if the coins are {2,3,5}$\{2,3,5\}$ and the desired sum is 9$9$, there are 3$3$ ways:

• 2+2+5$2+2+5$
  
• 3+3+3$3+3+3$
  
• 2+2+2+3$2+2+2+3$
  

Input

The first input line has two integers n$n$ and x$x$: the number of coins and the desired sum of money.

The second line has n$n$ distinct integers c1,c2,…,cn$c_1,c_2,\dots ,c_n$: the value of each coin.

Output

Print one integer: the number of ways modulo 109+7${10}^9+7$.

Constraints

• 1≤n≤100$1\le n\le 100$
  
• 1≤x≤106$1\le x\le {10}^6$
  
• 1≤ci≤106$1\le c_i\le {10}^6$
  

Example

Input:
3 9
2 3 5

Output:
3







#include <bits/stdc++.h>

using namespace std;

#define int long long int

#define F first

#define S second

#define pb push_back

#define si set<int>

#define vi vector<int>

#define pii pair<int, int>

#define vpi vector<pii>

#define vpp vector<pair<int, pii>>

#define mii map<int, int>

#define mpi map<pii, int>

#define spi set<pii>

#define endl "\n"

#define sz(x) ((int)x.size())

#define all(p) p.begin(), p.end()

#define double long double

#define que_max priority_queue<int>

#define que_min priority_queue<int, vi, greater<int>>

#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)

#define print(a)          \

    for (auto x : a)      \

        cout << x << " "; \

    cout << endl

#define print1(a)    \

    for (auto x : a) \

    cout << x.F << " " << x.S << endl

#define print2(a, x, y)         \

    for (int i = x; i < y; i++) \

        cout << a[i] << " ";    \

    cout << endl

inline int power(int a, int b)

{

    int x = 1;

    while (b)

    {

        if (b & 1)

            x *= a;

        a *= a;

        b >>= 1;

    }

    return x;

}

template <typename Arg1>

void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f(const char *names, Arg1 &&arg1, Args &&...args)

{

    const char *comma = strchr(names + 1, ',');

    cout.write(names, comma - names) << " : " << arg1 << " | ";

    __f(comma + 1, args...);

}

const int N = 1e9 + 7;

void solve()

{

    int n, x;

    cin >> n >> x;

    vi v(n);

    for (int i = 0; i < n; i++)

    {

        cin >> v[i];

    }

    vector<int> dp(x + 1, 0);

    dp[0] = 1;

    for (int i = 0; i < n; i++)

    {

        for (int j = v[i]; j <= x; j++)

        {

            (dp[j] += (dp[j - v[i]]) % N) %= N;

        }

    }

    cout << dp[x];

}

int32_t main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    clock_t z = clock();

    int t = 1;

    //   cin >> t;

    while (t--)

        solve();

    return 0;

}