# Coin Combinations II

Consider a money system consisting of $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$ using the available coins.

For example, if the coins are $\left\{2,3,5\right\}$ and the desired sum is $9$, there are $3$ ways:
• $2+2+5$
• $3+3+3$
• $2+2+2+3$
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:
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 << endlinline 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 = 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;}