# Coin Combinations I

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

For example, if the coins are $\left\{2,3,5\right\}$ and the desired sum is $9$, there are $8$ ways:
• $2+2+5$
• $2+5+2$
• $5+2+2$
• $3+3+3$
• $2+2+2+3$
• $2+2+3+2$
• $2+3+2+2$
• $3+2+2+2$
Input

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

The second line has $n$ distinct integers ${c}_{1},{c}_{2},\dots ,{c}_{n}$: the value of each coin.

Output

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

Constraints
• $1\le n\le 100$
• $1\le x\le {10}^{6}$
• $1\le {c}_{i}\le {10}^{6}$
Example

Input:
3 92 3 5

Output:
8

Solution To the Above problem

#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 << endlconst 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];}vi dp(x+1,0);for(int i=0; i<=x; i++){    for(int j=0; j<n; j++){        if(v[j]==i)dp[i]++;        if(i-v[j]>=0) dp[i]+=(dp[i-v[j]])%N;        dp[i]%=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;}