# 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

`5`

,`1 + 2 + 2`

,`1 + 1 + 1 + 2`

, and`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`

):- We could not use the coin
`ci`

at all →`d[s][ci - 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: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB