Coin change - the number of ways

Given a money system that consists of `n` coins, each coin has a positive value . You are asked to find the number of ways to obtain a total amount of `x` by using the coins.
For instance, if the coin values are and we need to obtain `5`, there are 4 different ways to do that: `5`, `1 + 2 + 2`, `1 + 1 + 1 + 2`, and `1 + 1 + 1 + 1 + 1`. Unlike the combination sum, here the order doesnβt matter - weβre only interested in the multiset of coins that we use.

Input

The first line of the input contains two integers `n` (1 β€ n β€ 100) and `x` (1 β€ x β€ ).
The next line contains `n` space-separated integers (1 β€ β€ ).

Output

The program should print the number of ways possible to obtain `x` using the given coins. As the answer can get very large, you are asked to print it modulo .

Examples

 Input Output 3 5 1 2 5 4 3 9 2 3 5 3

Explanation

1. `5`, `1 + 2 + 2`, `1 + 1 + 1 + 2`, and `1 + 1 + 1 + 1 + 1`
1. `3 + 3 + 3`, `2 + 2 + 5`, `2 + 2 + 2 + 3`
Β

Tutorial

Notice that if we store a state with `d[s]` where `d[s]` is the number of different ways to obtain the sum `s` by using the coins, we will have an issue of double counting where we would count the same set of coins several times. So, for the set of `1 + 2 + 2` (which should be counted only once), we would have it counted 3 times for all their combinations: `1 + 2 + 2`, `2 + 1 + 2`, and `2 + 2 + 1`.
To address this issue, we would count the number of ways to obtain the value `s` by processing all the coins up to `ci` (`ci` is the index of the coin in the array `c`). We are allowed to not use `ci` at all or use it multiple times - all of that is captured in the state. So, our state `d[s][ci]` would represent the number of ways to obtain the sum `s` by processing all the coins up to `ci`.
Β
There are 2 transitions that can get us from some of the previous states to the current `d[s][ci]` (the index of the current coin is `ci` and its value is `val`):
1. We could not use the coin `ci` at all β `d[s][ci - 1]`
1. We could use the coin `ci` for 0, 1, 2, β¦ k times β `d[s - val][ci]`
So, the total number of ways to obtain the sum `s` with all the coins up to `ci` would be the sum of all the transitions from the previous states described above.
Β
``````c = [...]
x = ...
# Initialize d with x+1 rows and len(c) columns of 0s
d = [[0] * len(c) for _ in range(x + 1)]``````
We can start by processing the first coin and update the state `d[s][0]` for all possible sums of `s` using the first coin. Then move on to the second coin and update all the states `d[s][1]`. Then to the third one - update `d[s][2]` and so on up until reaching the last coin.
After processing all the coins, we can print the number of possible ways to reach the sum `x` by printing the state of reaching `x` after processing the last coin - `d[x][len(c) - 1]`:
``````for ci, val in enumerate(c):      # Iterate over coins one-by-one
d[0][ci] = 1                  # Possible to obtain sum of 0 with no coins
for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
if ci - 1 >= 0:           # (1) Not use ci at all
d[s][ci] += d[s][ci - 1]
if s - val >= 0:          # (2) Use ci for 0+ times
d[s][ci] += d[s - val][ci]

print(d[x][len(c) - 1])``````
Β
πΒ Can you think of a way to keep a one-dimensional list for `d`?
We process the coins one by one, so, itβs possible to throw away all the computed states for the coin `ci - 2` and before. On each iteration, weβre only interested in the current coin `ci` and the previous coin `ci - 1`. So, we can keep the previous coinβs state in one array and the current coinβs state in another.
πΒ Can you think of a way to not use any auxiliary array and only use a 1-dimensional `d`?
We can notice that the only operation from the previous coinβs state is the addition of `prev[s]` to `d[s]`. So, we can omit keeping the previous array at all:
``````# Initialize d x+1 items
d = [1] + [0] * x                 # Possible to obtain sum of 0 with no coins

for ci, val in enumerate(c):      # Iterate over coins one-by-one
for s in range(1, x + 1):     # Iterate over all the sums 1...x inclusive
if s - val >= 0:          # (2) Use ci for 0+ times
d[s] += d[s - val]
d[s] %= MOD

print(d[x])``````
Β

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB